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

3-битовый двоичный куб; все вершины, соединённые ребром имеют расстояние 1	пример расстояний: расстояние 3 100 → 011, расстояние 2 010 → 111
4-битовый двоичный тессеракт (четырёхмерный куб)
примеры расстояний в двоичном тессеракте: расстояние 1 0110 → 1110, расстояние 3 0100 → 1001

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

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

$d_{ij}=\sum _{k=1}^{p}\left|x_{ik}-x_{jk}\right|$.

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

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

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

Примеры

• $d(10{\color {SkyBlue}1}1{\color {SkyBlue}1}01,10{\color {Red}0}1{\color {Red}0}01)=2$
• $d(2{\color {SkyBlue}17}3{\color {SkyBlue}8}96,2{\color {Red}23}3{\color {Red}7}96)=3$
• $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$

Алгоритм

def hamming_distance(string1, string2):

   if (len(string1) != len(string2)):

       raise Exception('Strings must be of equal length.')

   dist_counter = 0

   for n in range(len(string1)):

       if string1[n] != string2[n]:

           dist_counter += 1

   return dist_counter

Свойства

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

1. $d(x,\;y)=0\Leftrightarrow x=y$ (аксиома тождества).
2. $d(x,\;y)=d(y,\;x)$ (аксиома симметрии).
3. $d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ (аксиома треугольника или неравенство треугольника).

• Из аксиом следует неотрицательность расстояния, поскольку

  $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$.

• Если неравенство треугольника представить в виде

  $d(x,y)\leqslant d(x,z)+d(y,z)$ для всех $x,y$ и $z$,

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

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

$d(x,\;y)\leqslant n,$

где $n$ — длина слов в символах.

Применения

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

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

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

Телекоммуникации

Алгоритм используется в телекоммуникациях для подсчета количества неправильных бит в слове фиксированной длины для оценки ошибки и поэтому иногда называется расстоянием сигналов (англ. signal distance).

См. также

• Расстояние Левенштейна
• Обнаружение и исправление ошибок
• Матрица расстояний

Литература

• Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.