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

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

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

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

\text{[math]}

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

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

.

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

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

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

ПримерыПравить

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

СвойстваПравить

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

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

Из аксиом следует неотрицательность расстояния, поскольку
$\text{[math]}$ $\text{[math]}$ $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Если неравенство треугольника представить в виде
$\text{[math]}$ $\text{[math]}$ $d(x,y)\leqslant d(x,z)+d(y,z)$ для всех $\text{[math]}$ $\text{[math]}$ $x, y$ и $\text{[math]}$ $\text{[math]}$ $z$ ,

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

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

\text{[math]}

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

где

\text{[math]}

n

— длина слов в символах.

ПримененияПравить

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

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

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

ТелекоммуникацииПравить

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

См. такжеПравить

ПримечанияПравить

↑ Hamming distance: The number of digit positions in which the corresponding digits of two binary words of the same length are different (Federal Standard 1037C Архивная копия от 2 марта 2009 на Wayback Machine).

ЛитератураПравить

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

[1] Hamming distance: The number of digit positions in which the corresponding digits of two binary words of the same length are different (Federal Standard 1037C Архивная копия от 2 марта 2009 на Wayback Machine).

[1]