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

Расстояние Хэмминга — это метрика, используемая в теории информации, комбинаторике и теории кодирования, которая определяет минимальное количество позиций, в которых различаются две последовательности (строки, векторы, кодовые слова) одинаковой длины. Иными словами, для двух строк равной длины расстояние Хэмминга равно числу символов, которые необходимо заменить, чтобы преобразовать одну строку в другую. Понятие введено американским математиком Ричардом Хэммингом в 1950 году.

Определение

Пусть даны две строки (или вектора) \(A\) и \(B\) одинаковой длины \(n\) над некоторым алфавитом \(\Sigma\). Расстояние Хэмминга \(d(A, B)\) определяется как количество позиций \(i\), для которых \(A_i \neq B_i\), где \(i\) принимает значения от 1 до \(n\). Формально:

\[ d(A, B) = |\{i : A_i \neq B_i, 1 \leq i \leq n\}| \]

Для двоичных векторов (алфавит \(\{0, 1\}\)) расстояние Хэмминга совпадает с весом Хэмминга (количеством единиц) результата их поразрядного сложения по модулю 2 (XOR). Например, для векторов \(A = 10110\) и \(B = 10011\) поразрядное XOR даёт \(00101\), вес которого равен 2, следовательно, \(d(A, B) = 2\).

Свойства

Расстояние Хэмминга является метрикой, то есть удовлетворяет аксиомам метрического пространства для любых строк \(A, B, C\) одинаковой длины:

1. Неотрицательность: \(d(A, B) \geq 0\), причём \(d(A, B) = 0\) тогда и только тогда, когда \(A = B\).
2. Симметричность: \(d(A, B) = d(B, A)\).
3. Неравенство треугольника: \(d(A, C) \leq d(A, B) + d(B, C)\).

Кроме того, для двоичных векторов выполняется свойство аддитивности относительно операции XOR: \(d(A, B) = w(A \oplus B)\), где \(w(x)\) — вес Хэмминга вектора \(x\).

История

Понятие расстояния Хэмминга было впервые опубликовано Ричардом Хэммингом в 1950 году в статье «Error detecting and error correcting codes» (Обнаружение и исправление ошибок в кодах). Работая в Bell Telephone Laboratories, Хэмминг решал задачу повышения надёжности передачи данных по зашумлённым каналам. Он предложил использовать коды, в которых кодовые слова разделены минимальным расстоянием, что позволяет обнаруживать и исправлять ошибки, возникшие при передаче. До Хэмминга аналогичные идеи высказывались Клодом Шенноном, но именно Хэмминг ввёл формальную метрику и построил первые практические коды, исправляющие ошибки (коды Хэмминга).

Применение

Теория кодирования

Основное применение расстояния Хэмминга — в теории помехоустойчивого кодирования. Минимальное расстояние Хэмминга \(d_{\min}\) между любыми двумя различными кодовыми словами кода определяет его корректирующую способность:

• Если \(d_{\min} \geq 2t + 1\), код может исправить до \(t\) ошибок в одном кодовом слове.
• Если \(d_{\min} \geq t + 1\), код может обнаружить до \(t\) ошибок.

Например, код с \(d_{\min} = 3\) (как в коде Хэмминга) может исправить одну ошибку или обнаружить две ошибки.

Криптография и хеширование

В криптографии расстояние Хэмминга используется для оценки лавинного эффекта — свойства хеш-функций и шифров, при котором изменение одного бита входных данных приводит к изменению примерно половины битов выходных данных. Близость расстояния Хэмминга к \(n/2\) для случайных входных данных считается показателем криптостойкости.

Биоинформатика

В биоинформатике расстояние Хэмминга применяется для сравнения генетических последовательностей (ДНК, РНК) одинаковой длины. Оно позволяет подсчитать количество точечных мутаций (замен нуклеотидов) между двумя последовательностями. Например, последовательности ATGC и ATCC различаются в одной позиции (G → C), поэтому расстояние Хэмминга между ними равно 1.

Обработка сигналов и изображений

В задачах распознавания образов и компьютерного зрения расстояние Хэмминга используется для сравнения бинарных дескрипторов изображений (например, BRIEF, ORB). Быстрое вычисление расстояния через операцию XOR делает его эффективным для поиска похожих изображений в больших базах данных.

Информационный поиск

В системах нечёткого поиска (fuzzy search) расстояние Хэмминга применяется для нахождения строк, отличающихся на заданное число символов. Например, в текстовых редакторах функция проверки орфографии может предлагать исправления, для которых расстояние Хэмминга до ошибочного слова минимально.

Примеры

Ограничения и критика

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

Связанные понятия

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

Источники

• Hamming, R. W. (1950). Error detecting and error correcting codes. The Bell System Technical Journal, 29(2), 147–160.
• MacWilliams, F. J., & Sloane, N. J. A. (1977). The Theory of Error-Correcting Codes. North-Holland Publishing Company.
• Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley-Interscience.
• Шеннон, К. (1963). Работы по теории информации и кибернетике. Издательство иностранной литературы.