Visualiseur de distance de Levenshtein

Saisissez deux chaînes pour voir leur distance de Levenshtein (d'édition) — le nombre minimal de modifications d'un seul caractère nécessaires pour transformer l'une en l'autre.

Exemple résolu — Visualiseur de distance de Levenshtein

Distance d'édition	3
Similarité	57,14%

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Visualiseur de distance de Levenshtein

La distance de Levenshtein entre deux chaînes est le plus petit nombre de modifications d’un seul caractère qui transforme l’une en l’autre, une modification étant une insertion, une suppression ou une substitution. C’est un minimum sur toutes les façons possibles de s’y prendre, et c’est précisément ce qui la rend difficile à évaluer à l’œil et facile à calculer avec une grille : il existe un nombre astronomique de séquences d’éditions, et ce procédé trouve la plus courte sans en énumérer une seule.

Ce que signifie chaque symbole

m, n: les longueurs des deux chaînes, A et B.
D(i, j): la façon la moins coûteuse de transformer les i premiers caractères de A en les j premiers caractères de B. Une case du tableau de cette page.
[aᵢ ≠ bⱼ]: vaut 1 lorsque les deux caractères diffèrent et 0 lorsqu’ils coïncident — le prix de la substitution, nul s’il n’y a rien à substituer.
d: la réponse, D(m, n) : la case en bas à droite.

D’où vient la formule

Décidez ce que signifie une case avant d’en remplir la moindre. Soit D(i, j) le nombre minimal d’éditions transformant les i premiers caractères de A en les j premiers de B. Le nombre cherché est D(m, n), et toute autre case est une version réduite de la même question.
Les bords ne demandent aucune réflexion. Pour construire les j premiers caractères de B à partir de rien, il faut faire j insertions : D(0, j) = j. Pour réduire à rien les i premiers caractères de A, il faut faire i suppressions : D(i, 0) = i. C’est la première ligne et la première colonne de la grille, et voilà pourquoi elles se contentent de compter.
Vient l’étape qui fait tout le travail. Prenez une séquence optimale quelconque pour D(i, j) et regardez seulement son dernier mouvement. Il n’y a que trois possibilités : elle a supprimé aᵢ, laissant la tâche D(i−1, j) ; elle a inséré bⱼ, laissant D(i, j−1) ; ou elle a apparié aᵢ et bⱼ, laissant D(i−1, j−1). Chacune est une case déjà remplie.
La case vaut donc le moins cher des trois : D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] ). Remplissez la grille de gauche à droite et de haut en bas : en arrivant sur une case, ses trois voisines sont déjà connues. C’est tout l’algorithme — m × n cases, trois comparaisons chacune.

Comment lire ce que vous voyez

La grille de cette page est ce tableau. Les lignes sont A, les colonnes sont B, et la ligne et la colonne supplémentaires en haut à gauche sont les préfixes vides de l’étape 2 — d’où leur simple 0, 1, 2, 3. La teinte d’une case est sa valeur : le couloir diagonal pâle est l’endroit où les deux chaînes coïncident encore à bon compte. Survolez une case ou touchez-la, et le panneau en dessous détaille l’étape 3 pour cette case précise — les trois candidats, chacun avec son calcul, le gagnant mis en évidence. La ligne colorée est un chemin optimal remonté depuis le coin inférieur droit, et la bande d’alignement en dessous est ce même chemin écrit en caractères.

Suppose: Chaque édition coûte exactement 1, et les caractères sont comparés par égalité stricte — pas de repli de casse, pas de normalisation Unicode, aucune notion de ressemblance entre caractères. Deux conséquences sont visibles ici. Ce qui est compté ici, ce sont des unités de code UTF-16, pas ce que vous appelleriez des lettres : tapez un seul émoji dans une case et le tableau fait 3 × 1, car un émoji vaut deux unités, et le supprimer coûte 2. Et café avec un é précomposé face à café écrit e plus un accent combinant donne une distance de 2 alors que les deux sont identiques à l’écran.
Ne tient plus quand: La grille compte m × n cases : le travail croît comme le produit des longueurs. Cela convient pour deux mots et devient sans espoir pour une requête contre un dictionnaire d’un million d’entrées, soit un million de grilles. La réponse naturelle serait un algorithme plus astucieux, et la surprise est qu’il n’en existe pour ainsi dire aucun : Backurs et Indyk ont montré en 2015 qu’une distance d’édition nettement sous-quadratique réfuterait l’hypothèse du temps exponentiel fort. Les correcteurs orthographiques réels ne battent pas cette borne, ils l’évitent — en s’arrêtant dès que la distance dépasse une petite limite, ou en indexant de sorte que presque aucun candidat ne soit jamais comparé.

La grille est petite parce que chaque sous-question n'est posée qu'une seule fois 🖖

Chercher parmi toutes les séquences d'éditions possibles est sans espoir — le nombre de combinaisons explose avec la longueur des mots. L'idée sauveuse est que toute paire de préfixes possède exactement une seule meilleure réponse, et cette réponse ne change jamais, quoi qu'il arrive plus loin dans la chaîne. Ainsi, plutôt que d'explorer des séquences, vous remplissez une grille : une ligne par lettre du premier mot, une colonne par lettre du second, plus une ligne et une colonne vides représentant le préfixe vide. Transformer kitten en sitting nécessite donc 7 × 8 = 56 cases, chacune étant déterminée en observant trois voisines déjà remplies, et la réponse 3 vous attend dans le coin inférieur droit. La quantité de calculs augmente avec le produit des deux longueurs, et non avec le nombre de façons d'éditer.

Une interversion coûte deux éditions tant que vous n’en décidez pas autrement 🖖

Tapez form et from : Levenshtein répond 2. L’algorithme n’a aucune notion du fait que les lettres ont été interverties, il paie donc deux substitutions. Or les lettres interverties comptent parmi les fautes de frappe les plus fréquentes, et c’est précisément pourquoi Damerau a ajouté un quatrième mouvement : si les deux caractères qu’il vous faut sont exactement les deux que vous avez dans l’ordre inverse, prenez-les tous les deux pour le prix d’un. Changez le modèle de coût ci-dessus et la même paire coûte 1. Rien n’a changé dans les mots — c’est le tarif qui a changé. Cela vaut d’être retenu partout où une distance d’édition sert de score de similarité, car le nombre est une propriété du modèle de coût choisi autant que des deux chaînes.

La version rapide ne peut pas dessiner cette image 🖖

Chaque cellule n’a besoin que de la ligne au-dessus d’elle et de la cellule à sa gauche : les lignes plus anciennes ne gagnent rien à rester. Les implémentations réelles acceptent le marché et conservent deux lignes au lieu de la table entière, ce qui fait passer la mémoire de m × n à min(m, n) — pour deux chaînes de mille caractères, d’environ un million de cellules à deux mille. Ce qu’elles abandonnent est exactement ce qui est dessiné ci-dessus. La distance survit dans la dernière cellule, mais le chemin qui y mène habitait les lignes écrasées : une implémentation à deux lignes peut donc vous dire que deux chaînes sont à trois éditions l’une de l’autre, sans dire lesquelles. Récupérer le chemin sans la grille complète est plus difficile qu’il n’y paraît ; Hirschberg l’a résolu en 1975 en coupant la table par le milieu et en descendant récursivement dans les deux moitiés.

Problème entièrement résolu

La séquence d'éditions la moins coûteuse pour transformer kitten en sitting 5 étapes
Transformez kitten en sitting. Trouvez la séquence d'édition la moins coûteuse et prouvez qu'il n'en existe aucune de moindre coût — puis déterminez ce que cela coûte lorsque le second mot est un dictionnaire entier.
1. La relation de récurrence constitue l'intégralité de l'algorithme. Chaque case évalue le coût pour y parvenir par suppression, par insertion ou en alignant les deux caractères courants — cette dernière option étant gratuite s'ils coïncident. Une case n'a besoin que de ses trois voisines situées au-dessus et à sa gauche, de sorte qu'un unique balayage de gauche à droite remplit le tableau.
  
  $d_{i, j} = min ⎩ ⎨ ⎧ d_{i - 1, j} + 1 d_{i, j - 1} + 1 d_{i - 1, j - 1} + [a_{i} \neq = b_{j}]$
2. Avant de remplir quoi que ce soit, encadrez la réponse. Les longueurs diffèrent de un, donc au moins une insertion est inévitable ; et réécrire le mot intégralement coûte 7. La réponse se situe entre les deux, ce qui élimine déjà la plupart des conjectures.
  
  $∣ a ∣ - ∣ b ∣ = 1 \leq d \leq max (∣ a ∣, ∣ b ∣) = 7$
3. Trois éditions suffisent : substituer k → s, substituer e → i, insérer g. Chacune est une opération d'édition valide et la chaîne aboutit au mot cible.
  
  $k \underline{i} tten \to s \underline{i} tten \to sitt \underline{i} n \to sitting$
4. Exhiber trois éditions prouve seulement que la distance vaut au plus 3. Le tableau prouve qu'elle vaut exactement 3, car chaque chemin vers le coin inférieur droit est évalué et le minimum est retenu à chaque case le long du parcours. C'est toute la différence entre trouver une réponse et savoir qu'elle ne peut pas être améliorée.
  
  $d = 3, similarity = 1 - \frac{3}{7} = 0.5714 = 57.14%$
5. Le coût est d'une case par paire de caractères — 42 ici, ce qui n'est rien. Face à un dictionnaire de 100 000 mots de sept lettres chacun, cela représente plus de quatre millions de mises à jour de cases pour une seule recherche.
  
  $Θ (∣ a ∣ ∣ b ∣) = 6 \times 7 = 42 cells; d (a, c) \leq d (a, b) + d (b, c)$
Réponse

L'outil affiche 3 et une similitude de 57,14 %, soit 1 − 3/7 : la distance normalisée par le mot le plus long. Tous deux proviennent d'un tableau que vous pouvez remplir à la main en une minute. Ce qui ne passe pas à l'échelle, c'est le tableau — le travail est en Θ(mn), de sorte que doubler les deux chaînes le quadruple, et chaque correcteur orthographique que vous avez utilisé est conçu autour du principe d'éviter cela. L'échappatoire n'est pas un tableau plus rapide. C'est que Levenshtein satisfait l'inégalité triangulaire, ainsi d(a, c) ≤ d(a, b) + d(b, c) permet à un index de prouver qu'un candidat est trop éloigné sans jamais mesurer à quelle distance.

$d (kitten, sitting) = 3, 1 - \frac{3}{7} = 57.14%$

Références (4)

The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.

Par l’équipe 42Math · Mis à jour 2026-05-21

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

kitten → sitting - kitten → sitting est le cas des manuels, et la réponse est 3 : deux substitutions et une insertion, soit 57,14% de similarité
book → back - book → back fait 2 opérations entre deux mots de quatre lettres, affiché comme 50,00% de similarité
Saturday → Sunday - Saturday → Sunday demande 3 éditions et affiche 62,50% de similarité, dont deux suppressions
form → from (interversion) - form → from est une simple interversion sous Damerau–Levenshtein, que l’outil lit comme 75,00% de similarité
Comparaison ADN - GATTACA → GCATGCG demande 4 opérations et 42,86% — la même mesure appliquée à des séquences