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>
==Свойства==
#<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</tex> (равенство достигается только в том случае, если точка <tex>z</tex> принадлежит отрезку <tex>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):#Пусть <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>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> выполняется.}}
Пусть слова <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 Математические основы информатики]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]
