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

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

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

Пусть заданы две строки \( s \) и \( t \) длины \( n \). Тогда расстояние Хэмминга \( D_H(s, t) \) определяется формулой:

$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$

Здесь \( s_i \) и \( t_i \) обозначают символы, расположенные в позиции \( i \) строк \( s \) и \( t \), а функция \( \delta(s_i, t_i) \) принимает значение 1, если \( s_i \neq t_i \), и 0 в противном случае.

Расстояние Хэмминга определено только для строк одинаковой длины \( n \).

Практический пример

Рассмотрим две строки:

$$ s = \text{"karbon"} $$

$$ t = \text{"carbon"} $$

Расстояние Хэмминга между \( s \) и \( t \) равно 1, поскольку строки отличаются только первым символом: k и c.

Пример 2

Рассмотрим ещё одну пару слов, для которых расстояние Хэмминга равно 2:

$$ s = \text{"thing"} $$

$$ t = \text{"thank"} $$

Эти слова различаются в двух позициях.

В третьей позиции находятся буквы «i» и «a», а в пятой - «g» и «k».

Метрическая топология, порождённая расстоянием Хэмминга

Расстояние Хэмминга задаёт метрическое пространство, поскольку для любых строк одинаковой длины \( x \), \( y \) и \( z \) выполняются следующие свойства:

1. Неотрицательность

   $$ D_H(x, y) \geq 0 \quad \text{и} \quad D_H(x, y) = 0 \ \text{тогда и только тогда, когда} \ x = y $$

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

   $$ D_H(x, y) = D_H(y, x) $$

   Порядок сравнения не имеет значения: расстояние от \( x \) до \( y \) всегда совпадает с расстоянием от \( y \) до \( x \).
3. Неравенство треугольника

   $$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$

   Для любых трёх строк прямое расстояние между \( x \) и \( z \) не может быть больше суммы расстояний через промежуточную строку \( y \). Каждое различие между \( x \) и \( z \) обязательно проявляется хотя бы в одном из двух промежуточных сравнений.

Поскольку расстояние Хэмминга удовлетворяет всем аксиомам метрики, оно определяет метрическое пространство на множестве всех строк фиксированной длины.

Любое метрическое пространство естественным образом порождает топологию, основанную на понятии расстояния.

Следовательно, расстояние Хэмминга также задаёт метрическую топологию.

Для любой строки \( x \) длины \( n \) и радиуса \( r \) определяется открытый шар (окрестность) \( B \), состоящий из всех строк, расстояние Хэмминга от которых до \( x \) меньше \( r \).

$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$

Именно такие открытые шары образуют базу метрической топологии, поскольку любое открытое множество можно представить как объединение открытых шаров.

Примечание. Множество всех двоичных строк или, более общо, строк над конечным алфавитом фиксированной длины \( n \) является конечным. Поэтому топология, индуцированная расстоянием Хэмминга, представляет собой дискретную топологию. Это означает, что каждое одноэлементное множество является одновременно открытым и замкнутым. Достаточно выбрать достаточно малый радиус, например \( r = 1 \), чтобы открытый шар содержал только одну строку.

Таким образом, для любого конечного множества строк одинаковой длины расстояние Хэмминга порождает дискретную метрическую топологию.

Пример

Рассмотрим множество двоичных строк длины три:

$$ X = \{000, 001, 011, 110, 111 \} $$

Построим открытые шары радиуса \( r = 2 \):

$$ B(x, r) = \{y \mid D_H(x, y) < 2 \} $$

Поскольку расстояние должно быть меньше 2, в каждый шар входят строки, отличающиеся от центральной ровно в одной позиции.

• Шар с центром в \( 000 \): $$ B(000, 2) = \{000, 001\} $$ Строка \( 001 \) отличается от \( 000 \) только одним символом.
• Шар с центром в \( 001 \): $$ B(001, 2) = \{001, 000, 011\} $$ Строки \( 000 \) и \( 011 \) находятся на расстоянии 1 от \( 001 \).
• Шар с центром в \( 011 \): $$ B(011, 2) = \{011, 001, 111\} $$ Строки \( 001 \) и \( 111 \) отличаются от центральной строки только в одной позиции.
• Шар с центром в \( 110 \): $$ B(110, 2) = \{110, 111\} $$ Единственная соседняя строка - \( 111 \).
• Шар с центром в \( 111 \): $$ B(111, 2) = \{111, 011, 110\} $$ Строки \( 011 \) и \( 110 \) находятся на расстоянии 1 от центральной строки.

Эти открытые шары образуют базу индуцированной топологии, поскольку из их объединений можно получить все остальные открытые множества.

Примечание. При радиусе \( r = 2 \) используется строгое неравенство, поэтому в открытый шар входят только строки, расстояние до которых меньше двух: $$ B(x, r) = \{ y \mid D_H(x, y) < 2 \}. $$ Если же требуется определить замкнутый шар, используется нестрогое неравенство: $$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \}. $$

Например, объединение шаров \( B(000, 2) \) и \( B(110, 2) \) имеет вид:

$$ B(000, 2) \cup B(110, 2) $$

Так как $ B(000, 2) = \{000, 001\} $ и $ B(110, 2) = \{110, 111\} $, получаем:

$$ B(000, 2) \cup B(110, 2) = \{000,001\} \cup \{110,111\} $$

$$ B(000, 2) \cup B(110, 2) = \{000,001,110,111\} $$

Следовательно, множество \( \{000,001,110,111\} \) также является открытым в данной топологии.

Итак, расстояние Хэмминга задаёт метрическую топологию, в которой любое открытое множество получается как объединение открытых шаров.

И так далее.