http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.197.2.214&*Викиконспекты - Вклад участника [ru]2026-04-14T20:15:41ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%A5%D1%8D%D0%BC%D0%BC%D0%B8%D0%BD%D0%B3%D0%B0&diff=26936Расстояние Хэмминга2012-06-25T16:21:50Z<p>217.197.2.214: Привет с матмеха :)</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Расстояние Хэмминга (Hamming distance)''' {{---}} число позиций, в которых различаются соответствующие символы двух строк одинаковой длины. }}<br />
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.<br />
[[Файл:Hamming.JPG|thumb|180px|3-битный бинарный куб для нахождения расстояния Хэмминга]]<br />
<br />
==Пример== <br />
*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<br />
*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<br />
*d(h<font color="blue">i</font>ll, h<font color="red">o</font>ll)=1<br />
<br />
==Свойства==<br />
''Расстояние Хэмминга'' обладает свойствами метрики, так как удовлетворяет ее [[Метрическое пространство#def1 | определению]].<br />
<br />
#<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>))''<br />
#<tex>~d(x,y)=d(y,x)</tex> ''(Объект <tex>x</tex> удален от объекта <tex>y</tex> так же, как объект <tex>y</tex> удален от объекта <tex>x</tex>)''<br />
#<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>. Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)''<br />
<br />
== Доказательство неравенства треугольника ==<br />
{{Утверждение<br />
|statement=<tex>~d(x,y) \le d(x,z) + d(z,y)</tex><br />
|proof=<br />
<br />
Пусть слова <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) \le d(x,z) + d(z,y)</tex>.<br />
}}<br />
<br />
== См. также ==<br />
*[[Избыточное кодирование, код Хэмминга]]<br />
<br />
== Ссылки ==<br />
*[http://ru.wikipedia.org/wiki/Расстояние_Хэмминга Расстояние Хэмминга — Википедия]<br />
*[http://en.wikipedia.org/wiki/Hamming_distance Hamming distance - Wikipedia]<br />
*[http://inf.1september.ru/article.php?ID=200701701 Математические основы информатики]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Алгоритмы сжатия]]</div>217.197.2.214