Изменения

{{Определение|definition='''Расстояние Хэмминга''' — (англ. ''Hamming distance'') {{---}} число позиций, в которых различаются соответствующие цифры символы двух двоичных слов строк одинаковой длины различны. }}В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых qk-ичных алфавитов и служит [[Метрическое пространство#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*d(15<font color="blue">38</font>1<font color="blue">24</mathfont>, 15<font color="red">23</font>1<font color="red">56</font>)=4*d(h<font color="blue">i</font>ll, h<font color="red">o</font>ll)=1

==Свойства==''Расстояние Хэмминга '' обладает свойствами метрики, удовлетворяя следующим условиям:так как удовлетворяет ее [[Метрическое пространство#def1 | определению]]. * #<mathtex>~d(x,y) = 0 \ge 0iff x = y</tex> ''(Если расстояние от <tex>x</tex> до <tex>y</tex> равно нулю, то <tex>x</tex> и <tex>y</tex> совпадают (<tex>x = y</mathtex>))''* #<mathtex>~d(x,y)=d(y,x)=0</mathtex> ''(Объект <tex>x</tex> удален от объекта <tex>y</tex> так же, как объект <tex>y</tex> удален от объекта <tex>x</tex>)''* #<mathtex>~d(x,y)\leqslant d(x,z) + d(z,y)</tex> ''(Расстояние от <tex>x</tex> до <tex>y</tex> всегда меньше или равно расстоянию от <tex>x</tex> до <tex>y</tex> через точку <tex>z</tex>. Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)'' == Доказательство неравенства треугольника =={{Утверждение|statement=<tex>~d(x,y) \leqslant d(x,z) + d(z,y)</tex>|proof= Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторых позициях. Тогда какое бы слово <tex>z</tex> мы ни взяли,оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов <tex>x</tex> и <tex>y</tex>. Следовательно, суммируя в правой части <tex>d(x, z)</mathtex> и <tex>* d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова <tex>x</tex> и <tex>y</tex>. Т.е. получается, что <mathtex>~d(x,zy) \le leqslant d(x,yz) + d(z,y,z)</mathtex>.}} == См. также ==*[[Избыточное кодирование, код Хэмминга]] == Источники информации ==*[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия]*[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia]*[http://inf.1september.ru/article.php?ID=200701701 Математические основы информатики] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Алгоритмы сжатия]]