Distanța Hamming

Distanța Hamming dintre două șiruri de aceeași lungime este numărul pozițiilor în care caracterele corespunzătoare diferă.

Este o măsură simplă, dar extrem de utilă, care indică direct cât de diferite sunt două șiruri. Practic, ea spune de câte modificări minime este nevoie pentru a transforma un șir în celălalt.

Fie două șiruri \( s \) și \( t \) de lungime \( n \). Distanța Hamming \( D_H(s, t) \) se definește prin:

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

unde \( s_i \) și \( t_i \) sunt caracterele aflate pe poziția \( i \), iar funcția \( \delta(s_i, t_i) \) este egală cu 1 dacă cele două caractere sunt diferite și 0 dacă sunt identice.

Distanța Hamming este definită doar pentru șiruri de aceeași lungime.

Exemple

Să analizăm un prim caz:

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

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

Șirurile diferă doar la prima literă. Prin urmare, distanța Hamming este 1.

Exemplul 2

Considerăm acum:

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

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

Diferențele apar în două poziții:

• la a treia literă, „i" devine „a"
• la a cincea literă, „g" devine „k"

Distanța Hamming este, așadar, 2.

De ce este importantă

Distanța Hamming nu este doar o definiție abstractă. Ea stă la baza multor aplicații concrete, cum ar fi:

• detectarea și corectarea erorilor în codurile de transmisie
• compararea secvențelor în bioinformatică
• analiza diferențelor între șiruri în informatică

Proprietăți fundamentale

Distanța Hamming definește un spațiu metric, deoarece respectă trei proprietăți esențiale:

1. Non-negativitate

   $$ D_H(x, y) \geq 0 \quad \text{și} \quad D_H(x, y) = 0 \ \text{dacă și numai dacă} \ x = y $$

   Distanța este întotdeauna nenegativă și devine zero doar atunci când șirurile sunt identice.
2. Simetrie

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

   Ordinea șirurilor nu influențează rezultatul.
3. Inegalitatea triunghiulară

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

   Distanța directă dintre două șiruri nu depășește suma distanțelor intermediare.

Aceste proprietăți garantează că ne aflăm într-un spațiu metric.

Topologia indusă

Pe baza acestei distanțe se poate construi o topologie metrică, adică o structură care descrie noțiunea de apropiere între șiruri.

Pentru un șir \( x \) și o rază \( r > 0 \), definim bila deschisă:

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

Aceasta conține toate șirurile suficient de „apropiate" de \( x \).

Mulțimea tuturor acestor bile deschise formează baza topologiei, deoarece orice mulțime deschisă poate fi obținută ca reuniune de astfel de bile.

Observație. Dacă lucrăm cu un număr finit de șiruri (de exemplu, toate șirurile binare de lungime \( n \)), topologia obținută este discretă. Fiecare element este simultan deschis și închis, deoarece putem construi o bilă care conține doar acel element.

Exemplu de topologie

Considerăm mulțimea:

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

Pentru \( r = 2 \), bilele deschise sunt:

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

Acestea conțin toate șirurile care diferă de cel central în cel mult o poziție.

• În jurul lui \( 000 \): $$ \{000, 001\} $$
• În jurul lui \( 001 \): $$ \{001, 000, 011\} $$
• În jurul lui \( 011 \): $$ \{011, 001, 111\} $$
• În jurul lui \( 110 \): $$ \{110, 111\} $$
• În jurul lui \( 111 \): $$ \{111, 011, 110\} $$

Aceste mulțimi constituie o bază a topologiei, deoarece prin reuniuni putem obține orice altă mulțime deschisă.

Observație. Condiția \( D_H(x, y) < 2 \) exclude punctele aflate la distanță exact 2. Pentru a le include, se folosește inegalitatea largă: $$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \} $$

De exemplu:

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

Această mulțime este deschisă în topologia indusă.

În concluzie, distanța Hamming nu doar măsoară diferența dintre șiruri, ci oferă și un cadru matematic coerent pentru a studia apropierea dintre ele.