Odległość Hamminga

Odległość Hamminga między dwoma łańcuchami o tej samej długości określa liczbę pozycji, na których odpowiadające sobie symbole są różne.

Można ją interpretować jako minimalną liczbę podstawień symboli potrzebnych do przekształcenia jednego łańcucha w drugi.

Jest to jedno z podstawowych pojęć wykorzystywanych w teorii kodowania, informatyce, transmisji danych i analizie błędów.

Jeżeli rozważamy dwa łańcuchy \( s \) i \( t \) o długości \( n \), odległość Hamminga \( D_H(s, t) \) definiuje się wzorem:

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

gdzie \( s_i \) oraz \( t_i \) oznaczają symbole znajdujące się na pozycji \( i \) odpowiednio w łańcuchach \( s \) i \( t \), natomiast funkcja \( \delta(s_i, t_i) \) przyjmuje wartość 1, gdy \( s_i \neq t_i \), oraz 0 w przeciwnym przypadku.

Odległość Hamminga jest zdefiniowana wyłącznie dla łańcuchów o identycznej długości.

Jak działa odległość Hamminga?

Idea jest bardzo prosta. Porównujemy dwa łańcuchy znak po znaku i zliczamy wszystkie pozycje, na których występują różnice.

Im większa liczba różniących się symboli, tym większa odległość Hamminga między analizowanymi łańcuchami.

Przykład

Rozważmy następujące dwa łańcuchy:

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

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

Odległość Hamminga między \( s \) i \( t \) wynosi 1, ponieważ oba łańcuchy różnią się wyłącznie pierwszą literą (k zamiast c).

Przykład 2

Rozważmy teraz dwa angielskie słowa, których odległość Hamminga wynosi 2:

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

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

Łańcuchy te różnią się w dwóch pozycjach:

w trzeciej literze („i" w „thing" oraz „a" w „thank") oraz w piątej („g" oraz „k").

W tym przypadku:

$$ D_H(s,t)=2 $$

Własności odległości Hamminga

Odległość Hamminga definiuje przestrzeń metryczną, ponieważ spełnia podstawowe aksjomaty metryki.

Dla dowolnych trzech łańcuchów \( x \), \( y \) i \( z \) o tej samej długości zachodzą następujące własności:

1. Nieujemność

   $$ D_H(x, y) \geq 0 \quad \text{oraz} \quad D_H(x, y) = 0 \ \text{wtedy i tylko wtedy, gdy} \ x = y $$

   Odległość Hamminga jest zawsze nieujemna, ponieważ zlicza liczbę różniących się symboli. Wartość zero otrzymujemy wyłącznie wtedy, gdy oba łańcuchy są identyczne.
2. Symetria

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

   Kolejność porównywania łańcuchów nie ma znaczenia. Wynik jest zawsze taki sam.
3. Nierówność trójkąta

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

   Bezpośrednia odległość między \( x \) i \( z \) nie może być większa niż suma odległości pośrednich.

Ponieważ odległość Hamminga spełnia wszystkie te własności, definiuje ona przestrzeń metryczną.

Topologia metryczna indukowana przez odległość Hamminga

Każda metryka pozwala zdefiniować pojęcie bliskości między elementami zbioru, a tym samym także topologię.

W przypadku odległości Hamminga otrzymujemy topologię metryczną opartą na kulach otwartych.

Dla dowolnego łańcucha \( x \) oraz promienia \( r \) kula otwarta o środku w \( x \) jest definiowana jako:

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

Oznacza to, że kula zawiera wszystkie łańcuchy znajdujące się w odległości mniejszej niż \( r \) od łańcucha centralnego.

Kule otwarte tworzą bazę topologii, ponieważ każdy zbiór otwarty można skonstruować jako sumę takich kul.

Uwaga. Jeżeli rozważamy skończony zbiór binarnych łańcuchów o ustalonej długości, topologia indukowana przez odległość Hamminga jest topologią dyskretną. Każdy element zbioru jest wtedy jednocześnie zbiorem otwartym i domkniętym.

Przykład topologii Hamminga

Rozważmy zbiór binarnych łańcuchów długości trzy:

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

Dla promienia \( r = 2 \) kule otwarte mają postać:

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

W praktyce oznacza to, że do kuli należą wszystkie łańcuchy różniące się od elementu centralnego dokładnie w jednej pozycji.

• Kula otwarta o środku w \( 000 \): $$ B(000, 2) = \{000, 001\} $$ Łańcuch \( 001 \) różni się od \( 000 \) tylko w jednej pozycji.
• Kula otwarta o środku w \( 001 \): $$ B(001, 2) = \{001, 000, 011 \} $$ Zarówno \( 000 \), jak i \( 011 \), znajdują się w odległości 1 od \( 001 \).
• Kula otwarta o środku w \( 011 \): $$ B(011, 2) = \{011, 001, 111\} $$
• Kula otwarta o środku w \( 110 \): $$ B(110, 2) = \{110, 111\} $$
• Kula otwarta o środku w \( 111 \): $$ B(111, 2) = \{111, 011, 110\} $$

Kule te tworzą bazę topologii indukowanej przez odległość Hamminga.

Uwaga. Warunek $$ D_H(x,y) < 2 $$ oznacza, że kula otwarta nie zawiera punktów leżących dokładnie na brzegu.

Dla zbioru domkniętego stosuje się natomiast nierówność:

$$ C(x,r)=\{y \mid D_H(x,y)\le 2\} $$

Możemy również tworzyć nowe zbiory otwarte poprzez sumy kul.

Na przykład:

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

Ponieważ:

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

oraz:

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

otrzymujemy:

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

Zbiór ten również jest otwarty w topologii indukowanej przez odległość Hamminga.

W ten sposób odległość Hamminga prowadzi do naturalnej struktury topologicznej opartej na pojęciu podobieństwa między łańcuchami symboli.