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

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

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

Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в 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$

Свойства

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

$d(x,\;y)=0\Leftrightarrow x=y$ (аксиома тождества).
$d(x,\;y)=d(y,\;x)$ (аксиома симметрии).
$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

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

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

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

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

См. также

Примечания

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).

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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).

Строки
Меры схожести строк	Расстояние Дамерау — Левенштейна Расстояние Левенштейна Расстояние Хэмминга Сходство Джаро — Винклера
Поиск подстроки	Алгоритм Бойера — Мура Алгоритм Бойера — Мура — Хорспула Алгоритм Кнута — Морриса — Пратта Алгоритм Рабина — Карпа Префикс-функция Z-функция Алгоритм Ахо — Корасик
Палиндромы	Дерево палиндромов Алгоритм Манакера
Выравнивание последовательностей	Алгоритм Нидлмана — Вунша Алгоритм Смита — Ватермана
Суффиксные структуры	Суффиксный массив Суффиксный автомат Суффиксное дерево Префиксное дерево
Другое	Синтаксический анализ Сопоставление с образцом Наибольшая общая подпоследовательность Наибольшая общая подстрока