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

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

4-битный двоичный тессеракт для нахождения расстояния Хэмминга. Два примера расстояний: 0100 → 1001 имеет расстояние 3; 0110 → 1110 имеет расстояние 1
Класс	Сходство строк
Структура данных	нить
Наихудшая производительность	${\ Displaystyle О (п)}$
Лучшая производительность	${\ displaystyle O (1)}$
Средняя производительность	${\ Displaystyle О (п)}$
Сложность пространства в наихудшем случае	${\ Displaystyle О (п)}$

3-битный двоичный куб для нахождения расстояния Хэмминга

Два примера расстояний: 100 → 011 имеет расстояние 3; 010 → 111 имеет расстояние 2

Минимальное расстояние между любыми двумя вершинами - это расстояние Хэмминга между двумя двоичными строками.

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

Основное приложение - теория кодирования , в частности, блочные коды , в которых строки одинаковой длины являются векторами над конечным полем .

Определение

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

Примеры

Символы могут быть, среди прочего, буквами, битами или десятичными цифрами. Например, расстояние Хэмминга между:

• « Ка рол в » и « ка втро в » - 3.
• « k a r ol in » и « k e r st in » равны 3.
• « k athr in » и « k erst in » - 4.
• 0000 и 1111 равно 4.
• 2 17 3 8 96 и 2 23 3 7 96 равно 3.

Характеристики

Для фиксированной длины n расстояние Хэмминга является метрикой на множестве слов длины n (также известное как пространство Хэмминга ), поскольку оно удовлетворяет условиям неотрицательности, симметрии, расстояние Хэмминга двух слов равно 0 тогда и только тогда, когда два слова идентичны, и это также удовлетворяет неравенству треугольника : Действительно, если мы зафиксируем три слова a , b и c , то всякий раз, когда есть разница между i- й буквой a и i- й буквой of c , то должна быть разница между i- й буквой a и i- й буквой b , или между i- й буквой b и i- й буквой c . Следовательно, расстояние Хэмминга между a и c не больше суммы расстояний Хэмминга между a и b и между b и c . Расстояние Хэмминга между двумя словами через и Ь также можно рассматривать как вес Хэмминга из в - б для соответствующего выбора оператора -, так же как разность двух целых чисел можно рассматривать как расстояние от нуля на числовой прямой.

Для двоичных строк и б расстояние Хэмминга равно числу единиц ( количества населения ) в виде XOR б . Метрическое пространство двоичных строк длиной n с расстоянием Хэмминга известно как куб Хэмминга ; как метрическое пространство оно эквивалентно набору расстояний между вершинами в графе гиперкуба . Можно также рассматривать двоичную строку длины n как вектор в , рассматривая каждый символ в строке как действительную координату; при таком вложении струны образуют вершины n- мерного гиперкуба , а расстояние Хэмминга струн эквивалентно манхэттенскому расстоянию между вершинами. ${\ Displaystyle \ mathbb {R} ^ {п}}$

Обнаружение и исправление ошибок

Минимальное расстояние Хэмминга используется для определения некоторых существенных понятий в теории кодирования , такие как ошибки обнаружения и коды с исправлением ошибок . В частности, код C называется обнаруживающим k ошибок тогда и только тогда, когда минимальное расстояние Хэмминга между любыми двумя его кодовыми словами составляет не менее k +1.

Например, рассмотрим код, состоящий из двух кодовых слов «000» и «111». Расстояние Хэмминга между этими двумя словами равно 3, и, следовательно, это k = 2 обнаружения ошибок. Это означает, что если один или два бита перевернуты, ошибка может быть обнаружена. Если три бита перевернуты, то «000» становится «111», и ошибка не может быть обнаружена.

Код C называется исправляющим k ошибок, если для каждого слова w в базовом пространстве Хэмминга H существует не более одного кодового слова c (из C ) такое, что расстояние Хэмминга между w и c не превышает k . Другими словами, код исправляет k- ошибки тогда и только тогда, когда минимальное расстояние Хэмминга между любыми двумя его кодовыми словами составляет не менее 2 k +1. Это легче понять геометрически, поскольку любые замкнутые шары радиуса k с центрами на различных кодовых словах не пересекаются. В этом контексте эти шары также называют сферами Хэмминга .

Например, рассмотрим тот же 3-битный код, состоящий из двух кодовых слов «000» и «111». Пространство Хэмминга состоит из 8 слов 000, 001, 010, 011, 100, 101, 110 и 111. Кодовое слово «000» и слова однобитовой ошибки «001», «010», «100» меньше или равно расстоянию Хэмминга от 1 до «000». Точно так же кодовое слово «111» и его слова с одиночной битовой ошибкой «110», «101» и «011» находятся в пределах 1 расстояния Хэмминга от исходного «111». В этом коде ошибка в одном бите всегда находится в пределах 1 расстояния Хэмминга от исходных кодов, и код может исправлять 1 ошибку , то есть k = 1 . Минимальное расстояние Хэмминга между «000» и «111» равно 3, что удовлетворяет 2k + 1 = 3 .

Таким образом, код с минимальным расстоянием Хэмминга d между своими кодовыми словами может обнаруживать не более d -1 ошибок и может исправлять ошибки ( d -1) / 2⌋. Последнее число также называется радиусом упаковки или способностью кода исправлять ошибки .

История и приложения

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

Он используется в телекоммуникациях для подсчета количества перевернутых битов в двоичном слове фиксированной длины в качестве оценки ошибки, и поэтому иногда его называют расстоянием до сигнала . Для q- мерных строк в алфавите размера q  ≥ 2 расстояние Хэмминга применяется в случае q-арного симметричного канала , в то время как расстояние Ли используется для фазовой манипуляции или, в более общем случае, каналов, подверженных ошибкам синхронизации, поскольку расстояние составляет ошибку ± 1. Если или оба расстояния совпадают, потому что любая пара элементов от или отличается на 1, но расстояния разные для больших . ${\ displaystyle q = 2}$${\ displaystyle q = 3}$${\ textstyle \ mathbb {Z} / 2 \ mathbb {Z}}$${\ textstyle \ mathbb {Z} / 3 \ mathbb {Z}}$${\ displaystyle q}$

Расстояние Хэмминга также используется в систематике как мера генетического расстояния.

Однако для сравнения строк разной длины или строк, в которых следует ожидать не только замен, но также вставок или удалений, более подходящей метрикой является расстояние Левенштейна .

Пример алгоритма

Следующая функция, написанная на Python 3, возвращает расстояние Хэмминга между двумя строками:

def hamming_distance(string1, string2):
	dist_counter = 0
	for n in range(len(string1)):
		if string1[n] != string2[n]:
			dist_counter += 1
	return dist_counter

Или, короче:

sum(xi != yi for xi, yi in zip(x, y))

Функция hamming_distance(), реализованная в Python 2.3+ , вычисляет расстояние Хэмминга между двумя строками (или другими повторяемыми объектами) равной длины, создавая последовательность логических значений, указывающих несоответствия и совпадения между соответствующими позициями в двух входах, а затем суммируя последовательность с False и Истинные значения интерпретируются как ноль и единица.

def hamming_distance(s1, s2) -> int:
    """Return the Hamming distance between equal-length sequences."""
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length.")
    return sum(el1 != el2 for el1, el2 in zip(s1, s2))

где функция zip () объединяет две коллекции одинаковой длины попарно.

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

int hamming_distance(unsigned x, unsigned y)
{
    int dist = 0;

    // The ^ operators sets to 1 only the bits that are different
    for (unsigned val = x ^ y; val > 0; ++dist)
    {
        // We then count the bit set to 1 using the Peter Wegner way
        val = val & (val - 1); // Set to zero val's lowest-order 1
    }

    // Return the number of differing bits
    return dist;
}

Более быстрой альтернативой является использование инструкции по сборке подсчета населения ( popcount ). Некоторые компиляторы, такие как GCC и Clang, делают его доступным через встроенную функцию:

// Hamming distance for 32-bit integers
int hamming_distance32(unsigned int x, unsigned int y)
{
    return __builtin_popcount(x ^ y);
}

// Hamming distance for 64-bit integers
int hamming_distance64(unsigned long long x, unsigned long long y)
{
    return __builtin_popcountll(x ^ y);
}

Смотрите также

• Ближайшая строка
• Расстояние Дамерау – Левенштейна
• Евклидово расстояние
• Проблема Гэпа-Хэмминга
• Код Грея
• Индекс Жаккара
• Расстояние Левенштейна
• Расстояние Махаланобиса
• Мангеймское расстояние
• Индекс сходства Соренсена
• Редкая распределенная память
• Лестница слов

использованная литература

дальнейшее чтение

•  Эта статья включает  материалы, являющиеся общественным достоянием, из документа Управления общих служб : «Федеральный стандарт 1037C» .
• Вегнер, Питер (1960). «Методика счета единиц в двоичном компьютере». Коммуникации ACM . 3 (5): 322. DOI : 10,1145 / 367236,367286 . S2CID  31683715 .
• Маккей, Дэвид JC (2003). Теория информации, выводы и алгоритмы обучения . Кембридж: Издательство Кембриджского университета . ISBN 0-521-64298-1.