Possibile miglioramento di Damerau-Levenshtein?

Recentemente ho implementato l'algoritmo di distanza Damerau-Levenshtein dallo pseudocodice su Wikipedia. Non sono riuscito a trovare alcuna spiegazione su come funziona esattamente e lo pseudocodice usa nomi di variabili completamente disinformati come DA , DB , i1 e j1 che mi ha lasciato la mente grattata.

Ecco la mia implementazione in Python: link

L'implementazione di Python mi ha aiutato a percorrere il programma e a capire cosa stava succedendo, rinominando le variabili in nomi più utili. Ero abbastanza familiare con l'approccio di Wagner-Fischer al calcolo della distanza di Levenshtein che avevo un quadro di riferimento.

A rischio di essere eccessivamente lunghi, ecco come intendo Damerau-Levenshtein:

Le variabili misteriose:

• DA ( last_row nel mio codice) è un tipo di mappa che contiene l'ultima riga su cui ogni elemento è stato visto; nel mio codice è un vero dizionario Python
• DB ( last_match_col ) contiene l'ultima colonna in cui la lettera in b corrisponde alla lettera in a per la riga corrente
• i1 ( last_matching_row ) è il numero di riga da DA per la lettera corrente in b
• j1 è solo una copia del valore di DB / last_match_col prima che sia potenzialmente aggiornato; nel mio codice mi sono appena spostato dove last_match_col è stato aggiornato ed eliminato questa variabile

Il costo di trasposizione:

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

sta calcolando il costo di scambiare il carattere corrente in b con l'ultimo carattere in b noto per essere in a (l'ultima corrispondenza), trattando tutti i caratteri in mezzo come aggiunte o cancellazioni.

Componenti del costo:

• H[i1][j1] ripristina il costo di base al punto nei calcoli prima della trasposizione, poiché trovare una trasposizione invalida il lavoro precedente
• (i-i1-1) è la distanza tra la riga corrente e l'ultima riga che corrisponde al carattere corrente, che è il numero di cancellazioni che sarebbero richieste
• (j-j1-1) è la distanza tra la colonna corrente e l'ultima colonna con una corrispondenza, che è il numero di aggiunte
• L'extra + 1 è solo il costo della trasposizione stessa

Se questa analisi non è corretta, mi piacerebbe sapere dove ho sbagliato. Come ho detto, non sono riuscito a trovare nessuna spiegazione dettagliata di come funziona l'algoritmo online.

Versione migliorata?

Dopo averlo capito, tuttavia, mi ha colpito il fatto che calcolando il costo di entrambe le aggiunte e le cancellazioni tra lettere trasposte sembravano imperfette: un'aggiunta e una cancellazione equivalgono a una sostituzione, che non è stai cercando.

Se tutto è corretto, la soluzione dovrebbe essere banale: il costo delle lettere tra lettere trasposte dovrebbe essere il più alto delle aggiunte e cancellazioni: convertire il maggior numero possibile in sostituzioni e aggiungere in qualsiasi aggiunte o eliminazioni.

Quindi il costo sarebbe:

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

Ecco il mio codice per questa versione: link

Da alcuni semplici test, questo sembra corretto. Ad esempio, "abcdef" - > "abcfad" fornisce una distanza di modifica di 2 (trasporre "d" e "f", cambia "e" a "a"), mentre l'algoritmo originale indica una distanza di 3 (le ultime tre lettere sono sostituzioni o 1 trasposizione + 1 aggiunta + 1 cancellazione).

Ora, non posso essere la prima a pensarci. Quindi, perché non l'ho incontrato? Non ho cercato abbastanza a lungo? O c'è qualche sottile difetto che impedisce a questo di funzionare?