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

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

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

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

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

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

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

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

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

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

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

Расстояния Хэмминга между двумя словами всегда ограничено значением их длины, то есть верно ${\displaystyle d(x,\;y)\leqslant n,}$ где ${\displaystyle n}$ — длина слов в символах.

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

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

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

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

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