Distance de Hamming

La distance de Hamming entre deux chaînes de même longueur correspond au nombre de positions où leurs caractères diffèrent.

En d’autres termes, elle mesure le nombre minimal de substitutions nécessaires pour transformer une chaîne en l’autre.

Si l’on considère deux chaînes $ s $ et $ t $ de longueur $ n $, la distance de Hamming $ D_H(s, t) $ est définie par :

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

où $ s_i $ et $ t_i $ désignent les caractères situés à la position $ i $ dans $ s $ et $ t $, et où $ \delta(s_i, t_i) $ vaut 1 si $ s_i \neq t_i $, et 0 sinon.

La distance de Hamming n’est définie que pour des chaînes de même longueur $ n $.

Un exemple concret
Topologie métrique induite par la distance de Hamming

Un exemple concret

Considérons les deux chaînes suivantes :

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

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

La distance de Hamming entre $ s $ et $ t $ est égale à 1, car elles ne diffèrent que par la première lettre (k au lieu de c).

Exemple 2

Autre exemple, avec deux mots anglais présentant une distance de Hamming égale à 2 :

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

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

Ces chaînes diffèrent en deux positions :

à la troisième lettre (« i » dans « thing » contre « a » dans « thank »), et à la cinquième (« g » contre « k »).

Topologie métrique induite par la distance de Hamming

La distance de Hamming définit un espace métrique, car elle satisfait les propriétés suivantes pour tout triplet de chaînes $ x $, $ y $ et $ z $ de même longueur :

Non-négativité
$$ D_H(x, y) \geq 0 \quad \text{et} \quad D_H(x, y) = 0 \ \text{si et seulement si} \ x = y $$
La distance de Hamming est toujours positive ou nulle, puisqu’elle compte des différences. Elle vaut zéro uniquement lorsque les deux chaînes sont identiques.
Symétrie
$$ D_H(x, y) = D_H(y, x) $$
La distance est symétrique, car comparer $ x $ à $ y $ donne le même résultat que comparer $ y $ à $ x $.
Inégalité triangulaire
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
Pour tout triplet de chaînes, la distance directe entre $ x $ et $ z $ ne dépasse jamais la somme $ D_H(x, y) + D_H(y, z) $, car toute différence entre $ x $ et $ z $ doit apparaître dans au moins l’un des deux segments intermédiaires.

Comme elle vérifie ces propriétés, la distance de Hamming définit un espace métrique sur l’ensemble des chaînes de longueur fixe.

Dans un tel espace, on peut construire une topologie à partir de la notion de proximité induite par la métrique.

En particulier, la distance de Hamming permet de définir une topologie métrique.

Pour toute chaîne $ x $ de longueur $ n $ et tout rayon $ r $, on définit une « balle ouverte » (ou voisinage) $ B $ centrée en $ x $ comme l’ensemble des chaînes dont la distance de Hamming à $ x $ est strictement inférieure à $ r $ :

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

Ces balles ouvertes constituent une base de la topologie métrique, puisqu’elles permettent de reconstruire tout ouvert comme union arbitraire de telles balles.

Remarque. Comme l’ensemble de toutes les chaînes binaires (ou chaînes de symboles) de longueur $ n $ est fini, la topologie induite par la distance de Hamming sur cet ensemble est la topologie discrète. En effet, chaque chaîne peut être considérée simultanément comme un ouvert et un fermé : il suffit de choisir un rayon très petit (par exemple $ r = 1 $) pour obtenir une balle ouverte ne contenant que cette chaîne.

Ainsi, la distance de Hamming engendre une topologie métrique qui, sur un ensemble fini de chaînes de même longueur, est nécessairement discrète.

Exemple

Considérons l’ensemble suivant de chaînes binaires de longueur trois :

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

La topologie induite par la distance de Hamming avec un rayon $ r = 2 $ s’obtient en examinant les balles ouvertes de rayon 2 centrées sur chaque élément :

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

Autrement dit, chaque ensemble ouvert est constitué des chaînes qui diffèrent de la chaîne centrale en exactement une position.

Balle ouverte centrée en $ 000 $ : $$ B(000, 2) = \{000, 001\} $$ Seule la chaîne $ 001 $ diffère de $ 000 $ en une position.
Balle ouverte centrée en $ 001 $ : $$ B(001, 2) = \{001, 000, 011 \} $$ Les chaînes $ 000 $ et $ 011 $ diffèrent de $ 001 $ d’une seule position.
Balle ouverte centrée en $ 011 $ : $$ B(011, 2) = \{011, 001, 111\} $$ Les chaînes $ 001 $ et $ 111 $ sont à une distance de 1 de $ 011 $.
Balle ouverte centrée en $ 110 $ : $$ B(110, 2) = \{110, 111\} $$ Seule la chaîne $ 111 $ diffère de $ 110 $ en une position.
Balle ouverte centrée en $ 111 $ : $$ B(111, 2) = \{111, 011, 110\} $$ Les chaînes $ 011 $ et $ 110 $ sont les plus proches de $ 111 $.

Ces balles forment la base de la topologie induite pour le rayon $ r = 2 $, car elles permettent de générer tous les autres ouverts par unions.

Remarque. Un rayon $ r = 2 $ implique que les chaînes diffèrent d’une seule position, car une « balle ouverte » n’inclut pas les points situés à la frontière. C’est pourquoi on utilise l’inégalité stricte : $$ B(x, r) = \{ y \mid D_H(x, y) < 2 \} $$. Pour définir un fermé, on utiliserait au contraire l’inégalité large : $$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \} $$

Par exemple, l’union des balles $ B(000, 2) $ et $ B(110, 2) $ est :

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

Comme $ B(000, 2) = \{000, 001\} $ et $ B(110, 2) = \{110, 111\} $, leur union est :

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

Dans cette topologie, l’ensemble $ \{000, 001, 110, 111\} $ est donc également un ouvert.

En conclusion, ce système définit une topologie métrique fondée sur la distance de Hamming avec un rayon $ r = 2 $, dans laquelle tout ouvert se construit comme une union de balles ouvertes de ce rayon.

Et ainsi de suite.