La distanza di Hamming

La distanza di Hamming tra due stringhe di uguale lunghezza è il numero di posizioni in cui i caratteri corrispondenti nelle due stringhe sono diversi.

In altre parole, la distanza di Hamming misura il numero di sostituzioni necessarie per trasformare una stringa nell'altra.

Data due stringhe $ s $ e $ t $ di lunghezza $ n $, la distanza di Hamming $ D_H(s, t) $ è data da:

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

Dove $ s_i $ e $ t_i $ sono i caratteri nelle posizioni $ i $ delle stringhe $ s $ e $ t $, $ \delta(s_i, t_i) $ è una funzione che restituisce 1 se $ s_i \neq t_i $ e 0 altrimenti.

La distanza di Hamming è definita solo per stringhe di uguale lunghezza $ n $.

Un esempio pratico
Topologia metrica basata sulla distanza di Hamming

Un esempio pratico

Ad esempio, se considero le stringhe:

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

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

La distanza di Hamming tra $ s $ e $ t $ è 1, poiché differiscono solo nella prima posizione (k vs c).

Esempio 2

Un esempio di due parole in lingua inglese con distanza di Hamming uguale a 2 sono

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

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

Queste parole differiscono in due posizioni:

Alla terza lettera "i" in "thing" e "a" in "thank", mentre alla quinta lettera: "g" in "thing" e "k" in "thank".

Topologia metrica basata sulla distanza di Hamming

La distanza di Hamming può generare uno spazio metrico perché una funzione di distanza in una metrica deve soddisfare i seguenti assiomi per tutte le stringhe $ x $, $ y $, e $ z $ di uguale lunghezza:

Non negatività
$$ D_H(x, y) \geq 0 \ e \ D_H(x, y) = 0 \ \ \ se \ e \ solo \ se \ \ x = y $$
La distanza di Hamming conta il numero di posizioni diverse tra due stringhe, quindi è sempre un numero non negativo. Inoltre, se $ x $ e $ y $ sono identiche, $ D_H(x, y) = 0 $.
Simmetria
$$ D_H(x, y) = D_H(y, x) $$
La distanza di Hamming tra $ x $ e $ y $ è uguale alla distanza tra $ y $ e $ x $ perché conta solo le differenze di posizione, indipendentemente dall'ordine.
Disuguaglianza triangolare
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
Se considero tre stringhe $ x $, $ y $, e $ z $, la distanza diretta $ D_H(x, z) $ non può superare la somma delle distanze $ D_H(x, y) + D_H(y, z) $. Questo accade perché ogni differenza tra $ x $ e $ z $ deve apparire in almeno una delle distanze parziali tra $ x $ e $ y $ o tra $ y $ e $ z $.

La distanza di Hamming soddisfa tutte queste proprietà, quindi definisce uno spazio metrico (o sistema metrico) sull'insieme di tutte le stringhe di una certa lunghezza.

In un sistema metrico, posso costruire una topologia in base ai concetti di vicinanza definiti dalla distanza.

Pertanto, la distanza di Hamming può anche definire una topologia metrica.

Per ogni stringa $ x $ di lunghezza $ n $ e raggio $ r $, posso definire una "open ball" (intorno) $ B $ centrata in $ x $ come l'insieme di tutte le stringhe che hanno una distanza di Hamming inferiore a $ r $ da $ x $.

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

Le open ball definite dalla distanza di Hamming formano una base per la topologia metrica, in quanto gli insiemi aperti in una topologia metrica sono ottenuti tramite le unioni arbitrarie di queste "palle aperte".

Nota. Poiché l’insieme di tutte le stringhe binarie (o stringhe di simboli) di una data lunghezza $ n $ è finito, la topologia indotta dalla distanza di Hamming su questo insieme è la topologia discreta. Questo significa che ogni singola stringa rappresenta un insieme aperto (e anche chiuso) in questa topologia. Questo accade perché posso scegliere un raggio molto piccolo (ad esempio, $ r = 1 $) per fare in modo che ogni stringa sia contenuta in una palla aperta che non include altre stringhe.

Quindi, la distanza di Hamming genera una topologia metrica che, per insiemi finiti di stringhe di uguale lunghezza, è la topologia discreta.

Un esempio

Considero l'insieme composto da alcune stringhe binarie di lunghezza tre

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

La topologia indotta dalla distanza di Hamming con raggio $ r = 2 $ è costruita considerando le open ball di raggio 2 attorno a ciascuna stringa.

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

In altre parole, ogni insieme aperto è formato dalle stringhe che differiscono in una sola posizione dalla stringa centrale.

Palla aperta centrata in $ 000 $: $$ B(000, 2) = \{000, 001\} $$ Qui $ 000 $ è la stringa centrale, e solo la stringa $ 001 $ differisce da $ 000 $ in una sola posizione.
Palla aperta centrata in $ 001 $ $$ B(001, 2) = \{001, 000, 011 \} $$ In questo caso $ 001 $ è la stringa centrale, e le stringhe $ 000 $ e $ 011 $ differiscono da $ 001 $ in una sola posizione.
Palla aperta centrata in $ 011 $ $$ B(011, 2) = \{011, 001, 111\} $$ In questo caso $ 011 $ è la stringa centrale, e le stringhe $ 001 $ e $ 111 $ differiscono da $ 011 $ in una sola posizione.
Palla aperta centrata in $ 110 $ $$ B(110, 2) = \{110, 111\} $$ In questo caso $ 110 $ è la stringa centrale, e solo la stringa $ 111 $ differisce da $ 110 $ in una sola posizione.
Palla aperta centrata in $ 111 $ $$ B(111, 2) = \{111, 011, 110\} $$ In questo caso $ 111 $ è la stringa centrale e le stringhe $ 011 $ e $ 110 $ differiscono da $ 111 $ in una sola posizione.

Queste open ball definiscono la base della topologia indotta dalla distanza con raggio $ r = 2 $ perché mi permettono di individuare altri insiemi aperti nella topologia tramite la loro unione.

Nota. Il raggio $ r = 2 $ implica una sola posizione differente tra le stringhe, poiché la definizione di "insieme aperto" esclude il bordo. Pertanto, la relazione d'ordine è "minore di 2": $$ B(x, r) = \{ y \mid D_H(x, y) < 2 \} $$ Per ottenere invece "insiemi chiusi", occorre utilizzare la relazione d'ordine "minore o uguale a 2": $$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \} $$

Ad esempio, l'unione degli insiemi $ B(000, 2) $ e $ B(110, 2) $ è data da:

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

Sapendo che $ B(000, 2) = \{000, 001\} $ e $ B(110, 2) = \{110, 111\} $ la loro unione è

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

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

Quindi, in questa topologia anche l'insieme $ \{000,001,110, 111 \} $ è un insieme aperto.

In conclusione, questa costruzione definisce una topologia metrica basata sulla distanza di Hamming con raggio $ r=2 $, in cui ogni insieme aperto è ottenuto come unione delle palle aperte di raggio 1.

E così via.