Что такое расстояние Хэмминга?
Расстояние Хэмминга между двумя строками одинаковой длины — это количество позиций, в которых соответствующие символы не совпадают. Понятие названо в честь Ричарда Хэмминга и стало одним из ключевых в теории информации, теории кодирования и информатике. Оно показывает минимальное число замен символов, необходимое, чтобы превратить одну строку в другую, и широко применяется в кодах обнаружения и исправления ошибок.
Как пользоваться калькулятором
Введите две строки — это могут быть двоичные последовательности (например, 1011101), нуклеотиды ДНК или любой произвольный текст. Калькулятор сравнивает их посимвольно и подсчитывает, сколько позиций отличается. Если строки имеют разную длину, каждый «лишний» символ более длинной строки также засчитывается как расхождение.
Разбор формулы
Для двух строк a и b расстояние Хэмминга равно сумме по всем позициям \(i\) индикатора, который равен 1, когда \(a_i \neq b_i\), и 0 в противном случае:
$$d(a, b) = \sum_{i=1}^{\min(|a|,|b|)} \left[\, \text{A}_i \neq \text{B}_i \,\right] + \Big|\; |\text{A}| - |\text{B}| \;\Big|$$
Результат — всегда неотрицательное целое число в диапазоне от 0 (строки совпадают) до длины строки (различаются все позиции).
Пример с разбором
Сравним 1011101 и 1001001. Расположим их друг под другом:
10111011001001
Различия — в позиции 3 (1 против 0) и в позиции 5 (1 против 0). Итого расстояние Хэмминга равно 2.
Частые вопросы
Обязательно ли строки должны быть одной длины? Классическое расстояние Хэмминга определено только для строк равной длины. Тем не менее этот инструмент даёт полезный результат и для строк разной длины, засчитывая каждый лишний символ как несовпадение.
Работает ли он с небинарным текстом? Да. Сравнивать можно любые символы — буквы, цифры или знаки.
Чем расстояние Хэмминга отличается от расстояния Левенштейна? Расстояние Хэмминга учитывает только замены символов на фиксированных позициях, тогда как расстояние Левенштейна допускает ещё и вставки и удаления.
