| Определение: |
| Расстояние Хэмминга (Hamming distance) — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. |
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
3-битный бинарный куб для нахождения расстояния Хэмминга
Пример
- [math]d(10{\color{Blue}1}1{\color{Blue}1}01, 10{\color{Red}0}1{\color{Red}0}01)=2[/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(x, y) = 0 \iff x = y[/math] (Если расстояние от [math]x[/math] до [math]y[/math] равно нулю, то [math]x[/math] и [math]y[/math] совпадают ([math]x = y[/math]))
- [math]~d(x,y)=d(y,x)[/math] (Объект [math]x[/math] удален от объекта [math]y[/math] так же, как объект [math]y[/math] удален от объекта [math]x[/math])
- [math]~d(x,y) \le d(x,z) + d(z,y)[/math] (Расстояние от [math]x[/math] до [math]y[/math] всегда меньше или равно расстоянию от [math]x[/math] до [math]y[/math] через точку [math]z[/math] (равенство достигается только в том случае, если точка [math]z[/math] принадлежит отрезку [math]xy[/math]). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)
Доказательство неравенства треугольника
| Утверждение: |
[math]~d(x,y) \le d(x,z) + d(z,y)[/math] |
| [math]\triangleright[/math] |
|
I. Все позиции независимы.
II. Рассмотрим два варианта, когда [math]x = y[/math] (1) и [math]x \ne y[/math] (2):
- Пусть [math]x = y[/math], тогда [math]d = 0[/math] (по свойству №1), так как [math]d(x,z)[/math] и [math]d(z,y)[/math] не могут быть меньше нуля, значит их сумма также неотрицательна [math](0 \le d(x,z) + d(z,y))[/math], следовательно, неравенство [math]~d(x,y) \le d(x,z) + d(z,y)[/math] выполняется.
- Пусть слова [math]x \ne y[/math]. Тогда какое бы слово [math]z[/math] мы ни взяли, в какой-то конкретной позиции (в которой было расхождение у слов [math]x[/math] и [math]y[/math]) оно будет отличаться хотя бы от одного из них. Перебрав все такие позиции получим то, что количество различий между словами [math]x[/math] и [math]y[/math] не превосходит общее количество различий между словами [math]x[/math] и [math]z[/math] и словами [math]z[/math] и [math]y[/math]. А это означает, что неравенство [math]~d(x,y) \le d(x,z) + d(z,y)[/math] выполняется.
|
| [math]\triangleleft[/math] |
См. также
Ссылки
