Расстояние Хэмминга

Определение:

Расстояние Хэмминга (англ. Hamming distance) — число позиций, в которых различаются соответствующие символы двух строк одинаковой длины.

В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

Пример

• d(1011101, 1001001)=2
• d(1538124, 1523156)=4
• d(hill, holl)=1

Свойства

Расстояние Хэмминга обладает свойствами метрики, так как удовлетворяет ее определению.

1. [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]))
2. [math]~d(x,y)=d(y,x)[/math] (Объект [math]x[/math] удален от объекта [math]y[/math] так же, как объект [math]y[/math] удален от объекта [math]x[/math])
3. [math]~d(x,y) \leqslant d(x,z) + d(z,y)[/math] (Расстояние от [math]x[/math] до [math]y[/math] всегда меньше или равно расстоянию от [math]x[/math] до [math]y[/math] через точку [math]z[/math]. Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)

Доказательство неравенства треугольника

Утверждение:

[math]~d(x,y) \leqslant d(x,z) + d(z,y)[/math]

[math]\triangleright[/math]

Пусть слова [math]x[/math] и [math]y[/math] отличаются в некоторых позициях. Тогда какое бы слово [math]z[/math] мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов [math]x[/math] и [math]y[/math]. Следовательно, суммируя в правой части [math]d(x, z)[/math] и [math]d(z, y)[/math], мы обязательно учтем все позиции, в которых различались слова [math]x[/math] и [math]y[/math]. Т.е. получается, что [math]~d(x,y) \leqslant d(x,z) + d(z,y)[/math].

[math]\triangleleft[/math]

См. также

• Избыточное кодирование, код Хэмминга

Источники информации

• Расстояние Хэмминга — Википедия
• Hamming distance - Wikipedia
• Математические основы информатики