Расстояние Хэмминга

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

Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей: в этом случае расстоянием Хэмминга d ( x , y ) {displaystyle d(x,y)} между двумя двоичными последовательностями (векторами) x {displaystyle x} и y {displaystyle y} длины n {displaystyle n} называется число позиций, в которых они различны. В такой формулировке расстояние Хэмминга вошло в словарь алгоритмов и структур данных национального института стандартов и технологий США (англ. NIST Dictionary of Algorithms and Data Structures). Расстояние Хэмминга является частным случаем метрики Минковского (при соответствующем определении вычитания):

d i j = ∑ k = 1 p | x i k − x j k | {displaystyle d_{ij}=sum _{k=1}^{p}left|x_{ik}-x_{jk} ight|} .

Два слова, расстояние Хэмминга между которыми равно 1, называют соседними.

В некоторых системах счисления, например, в коде Грея, целые кодированные числа, различающиеся на 1, имеют расстояние Хэмминга равное 1. Говорят, что такие числа являются «соседними».

Соседнее кодирование важно при проектировании логических устройств, где необходимо исключить логические гонки.

Примеры

• d ( 10 1 1 1 01 , 10 0 1 0 01 ) = 2 {displaystyle d(10{color {SkyBlue}1}1{color {SkyBlue}1}01,10{color {Red}0}1{color {Red}0}01)=2}
• d ( 2 17 3 8 96 , 2 23 3 7 96 ) = 3 {displaystyle d(2{color {SkyBlue}17}3{color {SkyBlue}8}96,2{color {Red}23}3{color {Red}7}96)=3}
• d ( t o n e d , r o s e s ) = 3 {displaystyle d(mathrm {{color {SkyBlue}t}o{color {SkyBlue}n}e{color {SkyBlue}d}} ,mathrm {{color {Red}r}o{color {Red}s}e{color {Red}s}} )=3}

Свойства

Множество слов равной длины образуют метрическое пространство, где для каждой пары элементов пространства определено число — расстояние Хэмминга d ( x , y ) {displaystyle d(x,y)} удовлетворяющее аксиомам метрики:

d ( x , y ) = 0 ⇔ x = y {displaystyle d(x,;y)=0Leftrightarrow x=y} (аксиома тождества).

d ( x , y ) = d ( y , x ) {displaystyle d(x,;y)=d(y,;x)} (аксиома симметрии).

d ( x , z ) ⩽ d ( x , y ) + d ( y , z ) {displaystyle d(x,;z)leqslant d(x,;y)+d(y,;z)} (аксиома треугольника или неравенство треугольника).

• Из аксиом следует неотрицательность расстояния, поскольку 0 = d ( x , x ) ⩽ d ( x , y ) + d ( y , x ) = 2 ⋅ d ( x , y ) {displaystyle 0=d(x,x)leqslant d(x,y)+d(y,x)=2cdot d(x,y)} .
• Если неравенство треугольника представить в виде d ( x , y ) ⩽ d ( x , z ) + d ( y , z ) {displaystyle d(x,y)leqslant d(x,z)+d(y,z)} для всех x , y {displaystyle x,y} и z {displaystyle z} ,

тогда из аксиомы тождества и неравенства треугольника следует аксиома симметрии.

Расстояние Хэмминга всегда:

d ( x , y ) ⩽ n , {displaystyle d(x,;y)leqslant n,} где n {displaystyle n} — длина слов в символах.

Расстояние Хэмминга в биоинформатике и геномике

Для нуклеиновых кислот (ДНК и РНК) возможность гибридизации двух полинуклеотидных цепей с образованием вторичной структуры — двойной спирали — зависит от степени комплементарности нуклеотидных последовательностей обеих цепей. При увеличении расстояния Хэмминга количество водородных связей, образованных комплементарными парами оснований уменьшается и, соответственно, уменьшается стабильность двойной цепи. Начиная с некоторого граничного расстояния Хэмминга гибридизация становится невозможной.

При эволюционном расхождении гомологичных ДНК-последовательностей расстояние Хэмминга является мерой, по которой можно судить о времени, прошедшем с момента расхождения гомологов, например, о длительности эволюционного отрезка, разделяющего гены-гомологи и ген-предшественник.