Distance Damerau–Levenshtein

La distance de Damerau–Levenshtein est une métrique d’édition classique qui compte combien d’opérations sur un seul caractère transforment une chaîne en une autre lorsque les opérations autorisées sont l’insertion, la suppression, la substitution et la transposition de deux caractères adjacents. Cette dernière opération la distingue de la distance de Levenshtein simple et la rend particulièrement utile face aux coquilles réelles : les utilisateurs inversent souvent deux touches voisines (form contre from, teh contre the) et cela doit coûter une étape, pas deux substitutions. Cette capacité implémente la forme Optimal String Alignment de la distance avec une table pure de programmation dynamique, de sorte que chaque paire d’entrées produit le même entier sur tout runtime. Vous envoyez deux textes et un indicateur optionnel de sensibilité à la casse ; vous recevez la distance, les deux longueurs, une similarité normalisée entre zéro et un, et un booléen identical.

Ce que mesure Damerau–Levenshtein et la différence avec Levenshtein simple

La distance d’édition demande combien de changements unitaires sont nécessaires pour réécrire une chaîne source en chaîne cible. La Levenshtein classique autorise trois opérations unitaires : insérer un caractère, supprimer un caractère ou substituer un caractère par un autre. Chacune coûte un.

L’extension de Damerau ajoute une quatrième opération : échanger deux caractères adjacents pour un seul coût unitaire. Cette extension correspond à la façon dont les gens se trompent réellement au clavier. Par exemple, les chaînes ab et ba diffèrent d’une transposition adjacente sous Damerau–Levenshtein et de deux substitutions sous Levenshtein simple.

Kitten versus sitting coûte toujours trois (comme dans l’exemple manuel de Levenshtein) car le chemin le moins cher utilise des substitutions et une insertion plutôt qu’un seul échange. Ce point d’accès utilise la récurrence Optimal String Alignment (OSA) : une matrice de programmation dynamique où la cellule (i, j) est le minimum de supprimer, insérer, substituer ou faire correspondre, et—lorsque les deux derniers caractères de chaque préfixe forment une paire croisée—transposer depuis la cellule (i−2, j−2).

OSA est la forme que la plupart des bibliothèques appellent Damerau–Levenshtein pour la correction de coquilles ; elle interdit d’appliquer deux transpositions superposées sur la même sous-chaîne, ce qui garde la métrique simple et O(n·m) en temps et en espace. Les chaînes vides sont valides : la distance de la chaîne vide à toute chaîne est la longueur de cette chaîne, et la distance entre deux vides est zéro. Les chaînes identiques donnent toujours distance zéro et similarité un, y compris après le pliage optionnel de la casse.

Où cette distance se montre utile

Les outils de recherche produit et d’inventaire utilisent la distance d’édition avec transpositions pour classer SKU et marques presque coincidentes avant de basculer vers des modèles sémantiques plus lents. Les pipelines CRM et de déduplication signalent des lignes candidates en doublon lorsque la distance est au plus un ou deux et que la similarité dépasse un seuil fixe, capturant des lettres échangées que l’égalité pure ou même Levenshtein simple sous-évalueraient.

Les démos de correcteur et les exercices en classe ont besoin d’un oracle déterministe qui marque form contre from comme distance un et facture un tarif fixe transparent plutôt qu’un coût par jetons. Une entrée invalide ne consomme pas le solde.

Associez la distance entière à votre propre politique de seuil—acceptez distance zéro uniquement pour les clés exactes, distance un pour une correction agressive de coquilles, similarité au-dessus de 0.8 pour des indices de fusion douce—et vous obtenez un bloc auditable de correspondance floue sans déployer un moteur de recherche complet ni une pile TALN propre.