Ein guter Algorithmus ähnlich wie Levenshtein, aber gewichtet für QWERTY-Tastaturen?

Question

Ich bemerkte einige Einträge hier auf String Matching, die mich an ein altes Problem erinnerte, das ich gerne lösen würde. Hat jemand einen guten Levenshtein-ähnlichen Algorithmus, der auf QWERTY-Tastaturen gewichtet ist?

Ich möchte zwei Zeichenfolgen vergleichen und Tippfehler zulassen. Levenshtein ist in Ordnung, aber ich würde auch lieber Rechtschreibfehler akzeptieren, die auf dem physischen Abstand zwischen Schlüsseln auf der QWERTZ-Tastatur basieren. Mit anderen Worten, der Algorithmus sollte "yelephone" zu "zelephone" bevorzugen, da die "y" -Taste näher bei der "t" -Taste als bei der "z" -Taste auf den meisten Tastaturen liegt.

Jede Hilfe wäre großartig ... diese Funktion ist nicht zentral für mein Projekt, also möchte ich nicht in ein Rattenloch abschweifen, wenn ich etwas produktiveres tun sollte.

Answer 1

Wenn Sie in der Bioinformatik zwei DNA-Sequenzen ausrichten, haben Sie möglicherweise ein Modell mit unterschiedlichen Kosten, wenn die Substitution eine Transition oder eine Transversion ist. Das ist genau das, was Sie wollen, aber statt einer 4x4-Matrix, Sie wollen eine 40x40-Matrix oder einige, ich kann sagen, Distanz-Funktion? Die Kosten eines Ersatzes ergeben sich also aus der Matrix/Funktion, keine Konstante.

CAVEAT: Stellen Sie sicher, dass Löschungen und Einfügungen zwar richtig gewichtet sind, sie aber nicht als Minimum akzeptiert werden. Sie erhalten eine Zeichenfolge mit Einfüge-/Löschvorgängen/Ersatzzeichen ohne Änderung.

Die neue Funktion, die Sie wäre zu minimieren versuchen:

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]) 
)