1632
правки
Изменения
м
[[Файл:Hamming.JPG|thumb|180px|3-битный бинарный куб для нахождения расстояния Хэмминга]]
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Расстояние Хэмминга ''' (англ. ''Hamming distance)''' — ) {{---}} число позиций, в которых различаются соответствующие цифры символы двух двоичных слов строк одинаковой длины различны. }}
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
==Пример==
*<math>d(10{\<font color{Blue}="blue">1}</font>1{\<font color{Blue}="blue">1}</font>01, 10{\<font color{Red}="red">0}</font>1{\<font color{Red}="red">0}</font>01)=2</math>*<math>d(15{\<font color{Blue}="blue">38}</font>1{\<font color{Blue}="blue">24}</font>, 15{\<font color{Red}="red">23}</font>1{\<font color{Red}="red">56}</font>)=4</math>*<math>d(h{\<font color{Blue}="blue">i}</font>ll, h{\<font color{Red}="red">o}</font>ll)=1</math>
==Свойства==
''Расстояние Хэмминга'' обладает свойствами метрики, так как удовлетворяет ее [[Метрическое пространство#def1 | определению]].
#<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) \le leqslant d(x,z) + d(z,y)</tex> ''(Расстояние от '''<tex>x''' </tex> до '''<tex>y''' </tex> всегда меньше или равно расстоянию от '''<tex>x''' </tex> до '''<tex>y''' </tex> через точку '''<tex>z''' (равенство достигается только в том случае, если точка '''z''' принадлежит отрезку '''xy''')</tex>. Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''
== Доказательство неравенства треугольника ==
{{Утверждение
|statement=<tex>~d(x,y) \le leqslant d(x,z) + d(z,y)</tex>|proof=I. Все позиции независимы. II. Рассмотрим два варианта, когда <tex>x = y</tex> (1) и <tex>x \ne y</tex> (2):#Пусть '''x <tex>=</tex> y''', тогда '''d = 0''' (по свойству №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> выполняется.#Пусть слова '''x''' и '''y''' отличаются в некоторой позиции '''t'''. Тогда какое бы слово '''z''' мы ни взяли, оно в этой позиции будет отличаться по крайней мере от одного из слов '''x''' и '''y'''. Следовательно, суммируя в правой части <tex>~d(x, z)</tex> и <tex>~d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова '''x''' и '''y'''. Все неравенства выполняются, значит, их сумма тоже, ч.т.д.}}
Пусть слова <tex>x</tex> и <tex>y</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>~d(x,y) \leqslant d(x,z) + d(z,y)</tex>.
}}
== См. также ==
*[[Избыточное кодирование, код Хэмминга]]
== Ссылки Источники информации ==
*[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия]
*[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia]
*[http://inf.1september.ru/article.php?ID=200701701 Математические основы информатики]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]
