Dernière mise à jour : 2026-07-01

Distance de Levenshtein

La distance de Levenshtein, aussi appelée distance d’édition, mesure à quel point deux chaînes diffèrent en comptant le plus petit nombre de modifications d’un seul caractère nécessaires pour transformer l’une en l’autre. Les modifications autorisées sont l’insertion, la suppression et la substitution, chacune au coût de un. Le calculateur prend deux chaînes et renvoie cette distance avec un pourcentage de similarité, utile pour la correction orthographique, la recherche approximative et la comparaison de séquences comme l’ADN.

Les trois opérations d’édition

Toute transformation entre deux chaînes peut s’exprimer comme une suite de trois mouvements de base. Une insertion ajoute un caractère, une suppression en retire un et une substitution remplace un caractère par un autre. La distance de Levenshtein cherche la suite la plus économique de ces mouvements, chacun coûtant un. Comme la substitution est une seule étape et non une suppression suivie d’une insertion, changer une lettre compte toujours pour une modification, pas deux.

Nommée d’après Vladimir Levenshtein, qui l’a définie en 1965, cette mesure généralise la plus ancienne Calculateur de distance de Hamming : la distance de Hamming n’autorise que les substitutions et seulement pour des chaînes de même longueur, tandis que celle de Levenshtein admet en plus les insertions et les suppressions, et traite donc des chaînes de longueurs différentes.

Le tableau de programmation dynamique

La distance se calcule en remplissant un tableau $D$ comportant une ligne par caractère de la première chaîne (plus une ligne vide en tête) et une colonne par caractère de la seconde (plus une colonne vide en tête). La cellule $D[i][j]$ contient la distance d’édition entre les $i$ premiers caractères de A et les $j$ premiers caractères de B.

La première ligne et la première colonne comptent les modifications par rapport à la chaîne vide, d’où $D[i][0] = i$ et $D[0][j] = j$. Toute autre cellule est le minimum de trois candidats :

où le coût de substitution $c$ vaut 0 lorsque les caractères coïncident et 1 lorsqu’ils diffèrent. La réponse se trouve dans la cellule en bas à droite. Remplir le tableau prend un temps proportionnel au produit des deux longueurs, $m \times n$.

Exemple résolu

Prenons le couple classique « kitten » et « sitting ». Le chemin optimal à travers le tableau donne trois modifications :

Aucune suite plus courte n’existe, la distance vaut donc 3. La chaîne la plus longue compte 7 caractères, si bien que la similarité est $1 - 3/7 \approx 0{,}571$, soit environ 57 %.

La similarité et ses limites

Le calculateur normalise la distance brute en un score de similarité au moyen de

$S = 1 - \dfrac{d_L}{\max(m, n)}$

Diviser par la longueur de la chaîne la plus longue maintient le résultat entre 0 % pour des chaînes totalement différentes et 100 % pour des chaînes identiques ; deux chaînes vides sont considérées identiques. Il s’agit d’une normalisation courante — d’autres outils divisent par la somme des longueurs ou utilisent des mesures fondées sur des rapports —, de sorte que les scores de similarité issus de sources différentes ne sont pas directement comparables.

Où elle est utilisée

Les correcteurs orthographiques classent les corrections proposées selon leur distance d’édition au mot mal orthographié. Les systèmes de recherche et de bases de données l’emploient pour la recherche approximative, tolérant les fautes de frappe lors de la consultation de noms ou d’adresses. En bio-informatique, la distance d’édition fonde l’alignement de séquences pour comparer ADN, ARN et protéines, où insertions et suppressions correspondent à des mutations. Le modèle de coût de Levenshtein simple traite toutes les modifications de la même façon ; les applications qui exigent des pénalités différentes selon les opérations, ou qui doivent aligner efficacement de très longues séquences, l’étendent avec des coûts pondérés ou des algorithmes d’alignement spécialisés.