類似於Levenshtein的一個很好的算法，但加權Qwerty鍵盤？

Question

我在這裏發現的字符串匹配，這讓我想起了一個老問題了，我想解決的一些職位。有沒有人有向全鍵盤加權良好的Levenshtein樣的算法？

我想比較兩個字符串，並允許錯別字。 Levenshtein沒問題，但我更願意接受基於Qwerty鍵盤上鍵之間物理距離的拼寫錯誤。換句話說，算法應該更喜歡，因爲「Y」鍵位於接近比大多數鍵盤上的「Z」鍵「T」鍵「yelephone」到「zelephone」。

任何幫助都會很棒......這個功能對我的項目來說並不重要，所以我不希望在我應該做更有成效的事情時進入老鼠洞。

Answer 1

在生物信息學，當你對齊DNA的兩個序列，你可能有具有基於不同的成本，如果替代是一個過渡或顛的模型。這正是你想要的，但不是4x4矩陣，你需要一個40x40矩陣或者一些，我敢說距離函數？因此，替換的成本來自矩陣/函數，而不是常數。

CAVEAT：確保儘管刪除和插入的權重正確，所以它們不會被接受爲最小值。你最終會得到一串插入/刪除/不可替換的字符。

您要儘量減少新的功能是：

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