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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Расстояние Хэмминга (Hamming distance)''' {{---}} число позиций, в которых соответствующие символы двух строк одинаковой длины различны. }}
+
'''Расстояние Хэмминга (Hamming distance)''' {{---}} число позиций, в которых различаются соответствующие символы двух строк одинаковой длины. }}
 
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
 
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
 
[[Файл:Hamming.JPG|thumb|180px|3-битный бинарный куб для нахождения расстояния Хэмминга]]
 
[[Файл:Hamming.JPG|thumb|180px|3-битный бинарный куб для нахождения расстояния Хэмминга]]
Строка 15: Строка 15:
 
#<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от <tex>x</tex> до <tex>y</tex> равно нулю, то <tex>x</tex> и <tex>y</tex> совпадают (<tex>x = y</tex>))''
 
#<tex>~d(x, y) = 0 \iff x = y</tex> ''(Если расстояние от <tex>x</tex> до <tex>y</tex> равно нулю, то <tex>x</tex> и <tex>y</tex> совпадают (<tex>x = y</tex>))''
 
#<tex>~d(x,y)=d(y,x)</tex> ''(Объект <tex>x</tex> удален от объекта <tex>y</tex> так же, как объект <tex>y</tex> удален от объекта <tex>x</tex>)''
 
#<tex>~d(x,y)=d(y,x)</tex> ''(Объект <tex>x</tex> удален от объекта <tex>y</tex> так же, как объект <tex>y</tex> удален от объекта <tex>x</tex>)''
#<tex>~d(x,y) \le d(x,z) + d(z,y)</tex> ''(Расстояние от <tex>x</tex> до <tex>y</tex> всегда меньше или равно расстоянию от <tex>x</tex> до <tex>y</tex> через точку <tex>z</tex> (равенство достигается только в том случае, если точка <tex>z</tex> принадлежит отрезку <tex>xy</tex>). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''
+
#<tex>~d(x,y) \le d(x,z) + d(z,y)</tex> ''(Расстояние от <tex>x</tex> до <tex>y</tex> всегда меньше или равно расстоянию от <tex>x</tex> до <tex>y</tex> через третий объект <tex>z</tex> (равенство достигается только в том случае, если объект <tex>z</tex> лежит между объектами <tex>x</tex> и <tex>y</tex> на прямой, которая их соединяет). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''
  
 
== Доказательство неравенства треугольника ==
 
== Доказательство неравенства треугольника ==

Версия 04:40, 15 декабря 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]x[/math] и [math]y[/math] на прямой, которая их соединяет). Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)

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

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

Доказательство №1

Пусть слова [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) \le d(x,z) + d(z,y)[/math].


Доказательство №2 (с помощью математической индукции)

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 \ne y[/math].

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

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

Индуктивное предположение верно, значит, неравенство [math]~d(x,y) \le d(x,z) + d(z,y)[/math] выполняется для любого натурального [math]k[/math] ([math]k[/math] — количество отличий слова [math]x[/math] от [math]y[/math]).
[math]\triangleleft[/math]


См. также

Ссылки