Расстояние Хэмминга — различия между версиями
Whiplash (обсуждение | вклад) |
Whiplash (обсуждение | вклад) |
||
Строка 34: | Строка 34: | ||
*[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия] | *[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия] | ||
*[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia] | *[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia] | ||
+ | [http://inf.1september.ru/article.php?ID=200701701 Математические основы информатики] |
Версия 04:35, 25 октября 2011
Определение: |
Расстояние Хэмминга (Hamming distance) — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности. |
Содержание
Пример
Свойства
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
Объект x удален от объекта y так же, как объект y удален от объекта x.
Третье свойство говорит, что дорога через третий объект с всегда длиннее, нежели прямой путь. Его обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.
Доказательство: Пусть слова x и y отличаются в некоторой позиции t. Тогда какое бы слово z мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов x и y. Следовательно, суммируя в правой части
и , мы обязательно учтем все позиции, в которых различались слова x и y.Математики договорились любую функцию, обладающую указанными тремя свойствами, называть расстоянием.
См. также
Избыточное кодирование, код Хэмминга