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

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

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

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


Примеры

  • 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) \ge 0
  • ~d(x,x)=0
  • ~d(x,y)=d(y,x)
  • ~d(x,z) \le d(x,y) + d(y,z)

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

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

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

См. также

Примечания

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

Литература

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



Wikimedia Foundation. 2010.

Нужно решить контрольную?

Полезное


Смотреть что такое "Расстояние Хэмминга" в других словарях:

  • расстояние Хэмминга — Число позиций, в которых два слова одинаковой длины отличаются друг от друга. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической терминологии. 1979 г.] Тематики теория передачи… …   Справочник технического переводчика

  • Расстояние Хемминга — Расстояние Хэмминга мера (точнее, метрика) различия объектов одинаковой размерности. Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными …   Википедия

  • Расстояние Левенштейна — (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике  это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на… …   Википедия

  • Расстояние кода — в теории кодирования метрики отличий кодов. Наиболее используемыми расстояниями являются: Расстояние Хэмминга Расстояние Левенштейна Расстояние Йенцена Шаннона См. также Объём кода Граница кода …   Википедия

  • Код Хэмминга — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей …   Википедия

  • Медаль Ричарда Хэмминга — (англ. Richard W. Hamming Medal)  награда, присуждаемая ежегодно институтом инженеров электротехники и электроники (англ. IEEE) за исключительный вклад в науку об информации, информационные системы и технологии. К награде могут… …   Википедия

  • Хэмминг, Ричард Уэсли — Ричард Уэсли Хэмминг Richard Wesley Hamming Дата рождения: 11 февраля 1915(1915 02 11) Место рождения: Чикаго, Иллинойс Дата смерти …   Википедия

  • Неравенство Гильберта-Варшамова — Неравенство Гильберта  Варшамова определяет предельные значения для параметров кодов (не обязательно линейных). Иногда употребляется название неравенство Гильберта  Шеннона  Варшамова, а в русскоязычной научной литературе  неравенство Варшамова … …   Википедия

  • Неравенство Гильберта — Варшамова — Неравенство Гильберта  Варшамова определяет предельные значения для параметров кодов (не обязательно линейных). Иногда употребляется название неравенство Гильберта  Шеннона  Варшамова, а в русскоязычной научной литературе … …   Википедия

  • Неравенство Варшамова-Гильберта — Неравенство Гильберта  Варшамова определяет предельные значения для параметров кодов (не обязательно линейных). Иногда употребляется название неравенство Гильберта  Шеннона  Варшамова, а в русскоязычной научной литературе  неравенство Варшамова … …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»