Расстояние Хэмминга
В теории информации расстояние Хэмминга между двумя строками одинаковой длины — это количество позиций, в которых соответствующие символы различны. Другими словами, он измеряет минимальное количество замен , необходимых для замены одной строки на другую, или минимальное количество ошибок , которые могли преобразовать одну строку в другую. В более общем контексте расстояние Хэмминга — это одна из нескольких строковых метрик для измерения расстояния редактирования между двумя последовательностями. Он назван в честь американского математика Ричарда Хэмминга .
Основное применение находится в теории кодирования , в частности, в блочных кодах , в которых строки одинаковой длины являются векторами над конечным полем .
Расстояние Хэмминга между двумя строками символов равной длины — это количество позиций, в которых соответствующие символы различны. [1]
Символы могут быть буквами, битами или десятичными цифрами, среди других возможностей. Например, расстояние Хэмминга между:
Для фиксированной длины n расстояние Хэмминга является метрикой на множестве слов длины n (также известном как пространство Хэмминга ), поскольку оно удовлетворяет условиям неотрицательности, симметрии, расстояние Хэмминга двух слов равно 0 тогда и только тогда, когда два слова идентичны, а также удовлетворяет неравенству треугольника : [2] В самом деле, если мы зафиксируем три слова a , b и c , то всякий раз, когда есть различие между i -й буквой a и я буква с, то должна быть разница между i -й буквой a и i -й буквой b или между i -й буквой b и i -й буквой c . Следовательно, расстояние Хэмминга между a и c не больше суммы расстояний Хэмминга между a и b и между b и c . Расстояние Хэмминга между двумя словами a и b также можно рассматривать как вес Хэмминга слова a − b .для соответствующего выбора оператора - так же, как разницу между двумя целыми числами можно рассматривать как расстояние от нуля на числовой прямой. [ требуется уточнение ]
Для двоичных строк a и b расстояние Хэмминга равно количеству единиц ( число популяций ) в XOR b . [3] Метрическое пространство двоичных строк длины n с расстоянием Хэмминга известно как куб Хэмминга ; это эквивалентно как метрическое пространство набору расстояний между вершинами в графе гиперкуба . Можно также рассматривать двоичную строку длины n как вектор , рассматривая каждый символ в строке как реальную координату; при таком вложении строки образуют вершины n -мерного гиперкуба, а расстояние Хэмминга строк эквивалентно манхэттенскому расстоянию между вершинами.
