Расстоя́ние Хэ́мминга (кодовое расстояние) — число позиций, в которых соответствующие символы двух слов одинаковой длины различны . В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых 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 0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)}$ .

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

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

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

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

${\displaystyle d(x,\;y)\leqslant n,}$

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

Применения

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

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

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

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

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

См. также

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

Примечания

Литература

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