- En cours de remplissage
- Lue
- Réponse
Distance d'édition (distance de Levenshtein)
Combien de changements d'une seule lettre transforment kitten en sitting ? Trois : remplacer k par s, remplacer e par i, et ajouter un g. Ce nombre est la distance d'édition : c'est grâce à lui que les correcteurs orthographiques classent leurs suggestions et que les biologistes comparent des gènes. Tapez deux mots et regardez un tableau la trouver. Appuyez sur Lecture pour regarder le tableau se remplir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Tapez deux mots : le premier s'écrit le long du bord gauche du tableau, le second en haut. Chaque case contient le plus petit nombre de modifications qui transforment les lettres jusqu'à sa ligne en les lettres jusqu'à sa colonne. À la fin, les modifications sont relues à partir de la case en bas à droite. Nouvel exemple choisit une autre paire de mots. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Tapez deux mots : le premier s'écrit le long du bord gauche du tableau, le second en haut.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
- Regardez chaque case prendre le moins cher de ses trois voisins, puis voyez les modifications relues en orange.
Comment fonctionne le tableau
Une case contient le plus petit nombre de modifications qui transforment les lettres du premier mot jusqu'à sa ligne en les lettres du second mot jusqu'à sa colonne. La première ligne compte des insertions, qui construisent le second mot à partir de rien, et la première colonne compte des suppressions. Si les deux lettres d'une case sont égales, elle recopie la case en haut à gauche : aucune modification n'est nécessaire. Sinon, elle vaut un de plus que le plus petit de trois voisins : en haut à gauche pour un remplacement, au-dessus pour une suppression, et à gauche pour une insertion.
Relire les modifications
La case en bas à droite est la distance d'édition. En partant de là, l'application cherche de quel voisin vient la valeur de la case et s'y rend : en diagonale pour une lettre conservée ou remplacée, vers le haut pour une lettre supprimée, vers la gauche pour une lettre insérée. Lues depuis le coin en haut à gauche, les étapes forment une liste de modifications la plus courte possible, affichée sous le tableau : une lettre seule est conservée, k→s est un remplacement, −e une suppression et +g une insertion.
Questions fréquemment posées
Qu'est-ce que la distance de Levenshtein ?
C'est un autre nom de cette distance d'édition : le plus petit nombre d'insertions, de suppressions et de remplacements d'une seule lettre qui transforment une chaîne en une autre. Elle porte le nom de Vladimir Levenshtein, qui l'a décrite en 1965.
Quelle est la distance d'édition entre kitten et sitting ?
3 : remplacer k par s, remplacer e par i, et insérer g à la fin. Le tableau montre qu'il n'existe aucune liste de modifications plus courte.
L'algorithme de distance d'édition est-il rapide ?
Pour des mots de longueurs m et n, le tableau a (m + 1)·(n + 1) cases, chacune remplie en une étape : le calcul prend donc un temps O(m·n). Si seule la distance compte, deux lignes du tableau suffisent.
Quelles autres distances d'édition existe-t-il ?
La distance de Damerau–Levenshtein compte aussi l'échange de deux lettres voisines comme une seule modification, ce qui convient bien aux fautes de frappe. La distance de Hamming n'autorise que les remplacements et s'applique à des chaînes de même longueur. La distance LCS n'autorise que les insertions et les suppressions.
Des données sont-elles envoyées quelque part ?
Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur