Un buon algoritmo simile a Levenshtein ma ponderato per le tastiere Qwerty?

Question

Ho notato alcuni post qui sulla corrispondenza delle stringhe, che mi hanno ricordato un vecchio problema che vorrei risolvere.Qualcuno ha un bene Levenstein-simil-algoritmo ponderato per le tastiere Qwerty?

Voglio confrontare due stringhe e consentire errori di battitura.Levenshtein va bene, ma preferirei accettare anche errori di ortografia basati sulla distanza fisica tra i tasti della tastiera Qwerty.In altre parole, l'algoritmo dovrebbe preferire "yelephone" a "zelephone" poiché il tasto "y" si trova più vicino al tasto "t" che al tasto "z" sulla maggior parte delle tastiere.

Qualsiasi aiuto sarebbe grande...questa funzionalità non è centrale nel mio progetto, quindi non voglio virare in una tana di topi quando dovrei fare qualcosa di più produttivo.

Answer 1

In bioinformatica quando si allineano due sequenze di DNA si potrebbe avere un modello che ha un costo diverso a seconda che la sostituzione sia una transizione o una trasversione.Questo è esattamente quello che vuoi ma invece di una matrice 4x4, vuoi una matrice 40x40 o qualcosa del genere, oserei dire funzione di distanza?Quindi il costo di una sostituzione dipende dalla matrice/funzione, non da una costante.

AVVERTIMENTO:Assicurati però che le eliminazioni e gli inserimenti siano ponderati correttamente, in modo che non siano accettati eccessivamente come minimo.Ti ritroverai con una stringa di caratteri di inserimento/cancellazione/sostituzione senza modifiche.

La nuova funzione che stai cercando di minimizzare sarebbe:

d[i, j] := minimum(
    d[i-1, j] + del_cost,
    d[i, j-1] + ins_cost,
    d[i-1, j-1] + keyboard_distance( s[i], t[j] )
)