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

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

Версия 07:05, 4 ноября 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] (Если расстояние от [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) \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):

  1. Пусть [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] выполняется.
  2. Пусть слова [math]x[/math] и [math]y[/math] отличаются в некоторой позиции [math]t[/math], т.е [math]d(x,y) = 1[/math]. Тогда какое бы слово [math]z[/math] мы ни взяли, оно в этой позиции будет отличаться хотя бы от одного из слов [math]x[/math] и [math]y[/math] [math]( 1 \le d(x,z) + d(z,y)[/math], когда [math]z[/math] равно одному из слов [math]x[/math] или [math]y[/math]; [math]2 \le d(x,z) + d(z,y)[/math], когда [math]z[/math] не равно ни одному из слов [math]x[/math] и [math]y)[/math]. Следовательно, неравенство [math]~d(x,y) \le d(x,z) + d(z,y)[/math] выполняется.
[math]\triangleleft[/math]


См. также

Ссылки