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