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

Question

Mir sind hier einige Beiträge zum String-Matching aufgefallen, die mich an ein altes Problem erinnerten, das ich gerne lösen würde.Hat jemand ein gutes? Levenstein-ähnlicher Algorithmus, der auf QWERTY-Tastaturen ausgerichtet ist?

Ich möchte zwei Zeichenfolgen vergleichen und Tippfehler berücksichtigen.Levenshtein ist in Ordnung, aber ich würde lieber auch Rechtschreibfehler akzeptieren, die auf dem physischen Abstand zwischen den Tasten auf der QWERTY-Tastatur basieren.Mit anderen Worten: Der Algorithmus sollte „yelephone“ gegenüber „zelephone“ bevorzugen, da sich die „y“-Taste auf den meisten Tastaturen näher an der „t“-Taste als an der „z“-Taste befindet.

Jede Hilfe wäre großartig...Diese Funktion ist für mein Projekt nicht von zentraler Bedeutung, daher möchte ich nicht in ein Rattenloch abdriften, wenn ich etwas Produktiveres tun sollte.

Answer 1

Wenn Sie in der Bioinformatik zwei DNA-Sequenzen ausrichten, erhalten Sie möglicherweise ein Modell, das unterschiedliche Kosten verursacht, je nachdem, ob es sich bei der Substitution um einen Übergang oder eine Transversion handelt.Das ist genau das, was Sie wollen, aber statt einer 4x4-Matrix möchten Sie eine 40x40-Matrix oder eine Distanzfunktion?Die Kosten für einen Ersatz ergeben sich also aus der Matrix/Funktion und sind keine Konstante.

VORBEHALT:Stellen Sie jedoch sicher, dass Löschungen und Einfügungen richtig gewichtet werden, damit sie nicht als Minimum akzeptiert werden.Am Ende erhalten Sie eine Zeichenfolge aus Einfügungen/Löschungen/nicht-änderbaren Ersetzungszeichen.

Die neue Funktion, die Sie minimieren möchten, wäre:

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