Відстань Геммінга

Відстань Геммінга (англ. Hamming distance) — число позицій, у яких відповідні цифри двох двійкових слів однакової довжини різні^[1]. У загальнішому випадку відстань Геммінга застосовується для рядків однакової довжини будь-яких абеток, що складаються з q символів, і служить метрикою відмінності (функцією, що визначає відстань в метричному просторі) об'єктів однакової вимірності.

Іншими словами, відстань Геммінга вимірює мінімальну кількість замін, необхідних для зміни одного рядка в інший, або мінімальну кількість помилок, які могли перетворити одну стрічку в іншу. У більш загальному контексті відстань Хеммінга є однією з метрик рядків^[en] для вимірювання відстані редагування^[en] між двома послідовностями.

Спочатку метрика була сформульована Річардом Геммінгом під час його роботи в Bell Labs для визначення міри відмінності між кодовими комбінаціями (двійковими векторами) у векторному просторі кодових послідовностей, в цьому випадку відстанню Геммінга $d(x,y)$ між двома двійковими послідовностями (векторами) $x$ і $y$ довжини $n$ називається кількість позицій, в яких вони різні — в такому формулюванні відстань Геммінга увійшла в словник алгоритмів і структур даних^[en] національного інституту стандартів і технологій США.

Приклади

$d(10{\color {Blue}1}1{\color {Blue}1}01,10{\color {Red}0}1{\color {Red}0}01)=2$
$d(2{\color {Blue}17}3{\color {Blue}8}96,2{\color {Red}23}3{\color {Red}7}96)=3$
$d({\color {Blue}t}o{\color {Blue}n}e{\color {Blue}d},{\color {Red}r}o{\color {Red}s}e{\color {Red}s})=3$

Властивості

Відстань Геммінга має властивості метрики, задовольняючи таким умовам:

$~d(x,y)\geq 0$
$~d(x,x)=0$
$~d(x,y)=d(y,x)$
$~d(x,z)\leq d(x,y)+d(y,z)$

Відстань Геммінга в біоінформатиці та геноміці

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

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

Див. також

Примітки

↑ 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 с.
Hamming, Richard W. (1950), Error detecting and error correcting codes (PDF), Bell System Technical Journal, 29 (2): 147—160, MR 0035935, архів оригіналу (PDF) за 25 травня 2006, процитовано 25 листопада 2012.

[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]

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