什麼字符串距離算法最適合測量打字精度？

Question

我試圖編寫一個函數來檢測用戶輸入特定的短語/句子/單詞/單詞的準確程度。我的目標是建立一個應用程序來訓練用戶輸入某些短語的準確性。

我最初的直覺是使用基本的levenshtein距離算法（主要是因爲這是我唯一的頭腦知道的算法）。

但經過多一點研究，我看到Jaro-Winkler是一個稍微有趣的算法，因爲它考慮了換位。

我甚至發現，談到這些算法之間的差異的鏈接：

Difference between Jaro-Winkler and Levenshtein distance?

看了這一切，除了各自的維基百科文章中，我還是有點無能，其算法最符合我的目標。

Answer 1

由於您正在對打字質量進行分級，並且您希望訓練學生做出零錯誤，所以您應該使用Levenshtein距離，因爲它不夠寬容。

另外，Levenshtein評分比Jaro-Winkler結果更直觀，易於理解，並且更易於用圖形表示。您可以修改Levenshtein算法來分別報告插入，刪除和錯誤類型，並向最終用戶顯示更正列表。另一方面，Jaro-Winkler爲您提供了難以向最終用戶展示的分數，因爲中間拼寫錯誤的處罰低於最終的處罰。

Answer 2

略顯舌頭，但只是略微：建立一個打字的生成模型，給出打出正確的字母的高（先驗）概率，並分配一次打擊兩個相鄰鍵的概率，錯誤順序的不同手牌，錯誤順序的同一手牌的兩把鑰匙，靠近正確鑰匙的鑰匙，遠離正確鑰匙的鑰匙等等。或者可能不那麼特別：給你的模型一個給定的概率給定當前的一對按鍵以繼續通道的按鍵順序。你可以用這樣的模型做很多事情;例如，通過爲學習者的實際表現給出可能性分數，您可以得到一個「距離」式度量。但更好的辦法是給他們一份總結他們最擅長的錯誤的報告 - 畢竟，爲什麼在許多數字會做的時候把他們的表現降到一個數字？如果您從大量真實打字員的作品中瞭解各種錯誤的概率，可以獲得獎勵積分。

Answer 3

我大多同意dasblinkenlight給出的答案，但是，會建議使用Damerau-Levenshtein distance而不是隻有Levenshtein，也就是說，包括換位。換位在輸入時非常頻繁且容易進行，並且沒有很好的理由說明爲什麼他們應該對其他可能的錯誤（插入，刪除和替換）產生雙重距離處罰。