Расстояние Хэмминга — различия между версиями

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

Версия 10:42, 20 января 2016

Определение:
Расстояние Хэмминга (англ. Hamming distance) — число позиций, в которых различаются соответствующие символы двух строк одинаковой длины.

В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

Пример

  • d(1011101, 1001001)=2
  • d(1538124, 1523156)=4
  • d(hill, holl)=1

Свойства

Расстояние Хэмминга обладает свойствами метрики, так как удовлетворяет ее определению.

  1. [math]~d(x, y) = 0 \iff x = y[/math] (Если расстояние от [math]x[/math] до [math]y[/math] равно нулю, то [math]x[/math] и [math]y[/math] совпадают ([math]x = y[/math]))
  2. [math]~d(x,y)=d(y,x)[/math] (Объект [math]x[/math] удален от объекта [math]y[/math] так же, как объект [math]y[/math] удален от объекта [math]x[/math])
  3. [math]~d(x,y) \leqslant d(x,z) + d(z,y)[/math] (Расстояние от [math]x[/math] до [math]y[/math] всегда меньше или равно расстоянию от [math]x[/math] до [math]y[/math] через точку [math]z[/math]. Это свойство обычно называют неравенством треугольника за его естественную геометрическую аналогию: сумма двух сторон треугольника всегда больше третьей стороны.)

Доказательство неравенства треугольника

Утверждение:
[math]~d(x,y) \leqslant d(x,z) + d(z,y)[/math]
[math]\triangleright[/math]
Пусть слова [math]x[/math] и [math]y[/math] отличаются в некоторых позициях. Тогда какое бы слово [math]z[/math] мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов [math]x[/math] и [math]y[/math]. Следовательно, суммируя в правой части [math]d(x, z)[/math] и [math]d(z, y)[/math], мы обязательно учтем все позиции, в которых различались слова [math]x[/math] и [math]y[/math]. Т.е. получается, что [math]~d(x,y) \leqslant d(x,z) + d(z,y)[/math].
[math]\triangleleft[/math]

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Расстояние_Хэмминга&oldid=51525»