Dobry algorytm podobny do Levenshteina, ale ważony dla klawiatur Qwerty?

Question

Zauważyłem tu kilka postów dotyczących dopasowywania ciągów, które przypominały mi stary problem, który chciałbym rozwiązać. Czy ktoś ma dobry algorytm podobny do tego, który jest ważony w stosunku do klawiatur Qwerty?

Chcę porównać dwa ciągi i pozwolić na literówki. Levenshtein jest w porządku, ale wolałbym również akceptować błędy pisowni na podstawie fizycznej odległości między klawiszami na klawiaturze QWERTY. Innymi słowy, algorytm powinien preferować "yelephone" do "zelephone", ponieważ klawisz "y" znajduje się bliżej klawisza "t" niż klawisza "z" na większości klawiatur.

Każda pomoc byłaby wspaniała ... ta funkcja nie ma zasadniczego znaczenia dla mojego projektu, więc nie chcę zejść do szczurzej dziury, gdy powinienem robić coś bardziej produktywnego.

Answer 1

W bioinformatyce, gdy wyrównujesz dwie sekwencje DNA, możesz mieć model, który ma inny koszt w oparciu o to, czy podstawienie jest przejściem czy transwersją. Dokładnie tego chcesz, ale zamiast matrycy 4x4 potrzebujesz matrycy 40x40 lub innej, odważysz się powiedzieć, funkcja odległości? Zatem koszt zastąpienia pochodzi z matrycy/funkcji, a nie z stałej.

PRZEGLĄD: Upewnij się, że skasowania i wstawki są ważone prawidłowo, więc nie są akceptowane jako minimum. Otrzymasz ciąg wstawek/usunięć/znaków bez podstawiania.

Nowa funkcja staramy się zminimalizować byłoby:

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