Расстояние Хэмминга — различия между версиями
Whiplash (обсуждение | вклад) |
Whiplash (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
*<math>d(15{\color{Blue}38}1{\color{Blue}24}, 15{\color{Red}23}1{\color{Red}56})=4</math> | *<math>d(15{\color{Blue}38}1{\color{Blue}24}, 15{\color{Red}23}1{\color{Red}56})=4</math> | ||
*<math>d(h{\color{Blue}i}ll, h{\color{Red}o}ll)=1</math> | *<math>d(h{\color{Blue}i}ll, h{\color{Red}o}ll)=1</math> | ||
| − | |||
==Свойства== | ==Свойства== | ||
| Строка 24: | Строка 23: | ||
Третье свойство говорит, что дорога через третий объект с всегда длиннее, нежели прямой путь. Его обычно называют ''неравенством треугольника'' за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны. | Третье свойство говорит, что дорога через третий объект с всегда длиннее, нежели прямой путь. Его обычно называют ''неравенством треугольника'' за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны. | ||
| − | + | Математики договорились любую функцию, обладающую указанными тремя свойствами, называть расстоянием. | |
| − | |||
| − | + | == Доказательство неравенства треугольника == | |
| + | {{Утверждение | ||
| + | |statement=Пусть слова '''x''' и '''y''' отличаются в некоторой позиции '''t'''. | ||
| + | |proof=Тогда какое бы слово '''z''' мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''x''' и '''y'''. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''x''' и '''y'''.}} | ||
== См. также == | == См. также == | ||
Версия 04:43, 25 октября 2011
| Определение: |
| Расстояние Хэмминга (Hamming distance) — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. |
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Пример
Свойства
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
Объект x удален от объекта y так же, как объект y удален от объекта x.
Третье свойство говорит, что дорога через третий объект с всегда длиннее, нежели прямой путь. Его обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.
Математики договорились любую функцию, обладающую указанными тремя свойствами, называть расстоянием.
Доказательство неравенства треугольника
| Утверждение: |
Пусть слова x и y отличаются в некоторой позиции t. |
| Тогда какое бы слово z мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов x и y. Следовательно, суммируя в правой части и , мы обязательно учтем все позиции, в которых различались слова x и y. |
См. также
Избыточное кодирование, код Хэмминга
