Расстояние Хэмминга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 20: Строка 20:
 
{{Утверждение
 
{{Утверждение
 
|statement=<tex>~d(x,y) \le d(x,z) + d(z,y)</tex>
 
|statement=<tex>~d(x,y) \le d(x,z) + d(z,y)</tex>
|proof=Пусть слова '''x''' и '''y''' отличаются в некоторой позиции '''t'''. Тогда какое бы слово '''z''' мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''x''' и '''y'''. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''x''' и '''y'''.}}  
+
|proof=I. Все позиции независимы.
 +
 
 +
II. Рассмотрим два варианта, когда '''x = y''' (1) и '''x != y''' (2):
 +
#Пусть '''x = y''', тогда '''d = 0''' (по свойству №1), так как <tex>d(x,z)</tex> и <tex>d(z,y)</tex> не могут быть меньше нуля, то неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняется.
 +
#Пусть слова '''x''' и '''y''' отличаются в некоторой позиции '''t'''. Тогда какое бы слово '''z''' мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''x''' и '''y'''. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''x''' и '''y'''.
 +
 
 +
Все неравенства выполняются, значит, их сумма тоже, ч.т.д.}}
 +
 
  
 
== См. также ==
 
== См. также ==

Версия 07:59, 1 ноября 2011

Определение:
Расстояние Хэмминга (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]

Свойства

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

  1. [math]~d(x, y) = 0 \iff x = y[/math] (Если расстояние от x до y равно нулю, то x и y совпадают (x равно y))
  2. [math]~d(x,y)=d(y,x)[/math] (Объект x удален от объекта y так же, как объект y удален от объекта x)
  3. [math]~d(x,y) \le d(x,z) + d(z,y)[/math] (Расстояние от x до y всегда меньше или равно расстоянию от x до y через точку z (равенство достигается только в том случае, если точка z принадлежит отрезку xy). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)

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

Утверждение:
[math]~d(x,y) \le d(x,z) + d(z,y)[/math]
[math]\triangleright[/math]

I. Все позиции независимы.

II. Рассмотрим два варианта, когда x = y (1) и x != y (2):

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


См. также

Ссылки