Amélioration possible de Damerau-Levenshtein?

J'ai récemment implémenté l'algorithme de distance Damerau-Levenshtein à partir du pseudocode sur Wikipedia. Je ne pouvais trouver aucune explication exactement comment cela fonctionne et utilise des noms de pseudocode variables complètement uninformative comme DA, DB, i1et j1qui m'a laissé me gratter la tête.

Voici mon implémentation en Python: https://gist.github.com/badocelot/5327337

L'implémentation Python m'a aidé à parcourir le programme et à comprendre ce qui se passait, en renommant les variables en noms plus utiles. Je connaissais assez bien l'approche de Wagner-Fischer pour calculer la distance de Levenshtein que j'avais un cadre de référence.

Au risque d'être trop long, voici comment je comprends Damerau-Levenshtein:

Les variables mystères:

• DA( last_rowdans mon code) est une sorte de carte contenant la dernière ligne sur laquelle chaque élément a été vu; dans mon code c'est un vrai dictionnaire Python
• DB( last_match_col) contient la dernière colonne où la lettre bcorrespond à la lettre ade la ligne actuelle
• i1( last_matching_row) est le numéro de ligne de DAla lettre actuelle dansb
• j1n'est qu'une copie de la valeur de DB/ last_match_colavant sa mise à jour potentielle; dans mon code, je viens de déplacer où last_match_colest mis à jour et éliminé cette variable

Le coût de transposition:

H[i1][j1] + (i-i1-1) + 1 + (j-j1-1)

calcule le coût de l'échange du caractère actuel bavec le dernier caractère bconnu a(dernière correspondance), en traitant tous les caractères intermédiaires comme des ajouts ou des suppressions.

Composantes du coût:

• H[i1][j1] ramène le coût de base au point dans les calculs avant la transposition, car la recherche d'une transposition invalide le travail précédent
• (i-i1-1) est la distance entre la ligne actuelle et la dernière ligne correspondant au caractère actuel, qui est le nombre de suppressions qui seraient nécessaires
• (j-j1-1) est la distance entre la colonne actuelle et la dernière colonne avec une correspondance, qui est le nombre d'ajouts
• Le supplément + 1n'est que le coût de la transposition elle-même

Si cette analyse est incorrecte, j'aimerais savoir où je me suis trompé. Comme je l'ai dit, je n'ai trouvé aucune explication détaillée du fonctionnement de l'algorithme en ligne.

Version améliorée?

Ayant compris cela, cependant, il m'a frappé en calculant le coût des deux ajouts et les suppressions entre les lettres transposés semblait viciée: une addition et une suppression est équivalente à une substitution, qui ne vérifie pas ce pour.

Si tout cela est correct, la solution devrait être triviale: le coût des lettres entre les lettres transposées devrait être le plus élevé des ajouts et des suppressions: convertissez autant en substitutions que possible et ajoutez les ajouts ou suppressions restants.

Le coût serait donc:

H[i1][j1] + max((i-i1-1), (j-j1-1)) + 1

Voici mon code pour cette version: https://gist.github.com/badocelot/5327427

D'après certains tests simples, cela semble correct. Par exemple, "abcdef" -> "abcfad" donne une distance d'édition de 2 (transposez "d" et "f", changez "e" en "a"), tandis que l'algorithme d'origine donne une distance de 3 (soit les trois derniers les lettres sont des substitutions, ou 1 transposition + 1 ajout + 1 suppression).

Maintenant, je ne peux pas être la première personne à avoir pensé à ça. Alors, pourquoi ne l'ai-je pas croisé? Est-ce que je n'ai pas cherché assez longtemps? Ou y a-t-il une faille subtile qui empêche cela de fonctionner réellement?

J'ai dû rechercher la distance Damerau-Levenshtein sur wikipedia, alors pardonnez-moi si c'est faux. Mais il semble qu'il ne permette que la transposition de lettres adjacentes et non de lettres arbitraires. Donc votre exemple "abcdef" -> "abcfad" avec transposition de d et f ne fonctionne pas. Il me semble que vous avez modifié la définition de l'algorithme et que vous ne calculez plus la distance Damerau-Levenshtein.