Levenshtein Edit Distance

La distance d'édition de Levenshtein remplit un tableau de (m+1) x (n+1) cases, où la case (i, j) contient le nombre minimal de modifications élémentaires (insertions, suppressions, substitutions) nécessaires pour transformer les i premiers caractères de la source en les j premiers caractères de la cible. La première ligne initialise chaque case j à la valeur j (j insertions depuis la chaîne vide), et la première colonne initialise chaque case i à la valeur i (i suppressions). Pour les cases intérieures, une correspondance de caractères recopie la diagonale sans coût ; un désaccord prend 1 plus le minimum de trois voisins : la case au-dessus (suppression dans la source), la case à gauche (insertion dans la cible) ou la diagonale (substitution). L'exemple canonique transformant « kitten » en « sitting » donne une distance de 3 : substitution de k par s, substitution de e par i, et ajout de g.

La distance d'édition est à la base des correcteurs orthographiques (le « vouliez-vous dire » de Google classe les candidats par distance d'édition par rapport à la faute), de la recherche floue de chaînes dans les bases de données, et de la comparaison de séquences DNA/RNA où les insertions et suppressions reflètent des mutations biologiques. Contrairement à la plus longue sous-séquence commune (LCS), la distance d'édition attribue un coût à toutes les non-correspondances, ce qui en fait une véritable métrique satisfaisant l'inégalité triangulaire. Cette propriété métrique permet une recherche efficace du plus proche voisin dans les arbres BK, qui stockent les mots d'un dictionnaire et élaguent les branches lorsque l'inégalité triangulaire exclut des candidats, réduisant le coût moyen d'une requête de O(n) à O(log n) pour des rayons d'édition faibles.