哪种字符串距离算法最适合衡量打字准确性？

Question

我正在尝试编写一个函数，用于检测用户输入的特定短语/句子/单词/词组的准确度。我的目标是构建一个应用程序来训练用户对某些短语的打字准确性。

我的最初想法是使用基本的Levenshtein距离算法（主要是因为这是我能够立即想到的唯一算法）。

但在进行了更多研究后，我发现Jaro-Winkler是一个稍微更有趣的算法，因为它考虑了置换的影响。

我甚至找到了一篇文章，讲述了这些算法之间的差异： Jaro-Winkler和Levenshtein距离之间的区别是什么？ 阅读所有这些内容后，加上各自的维基百科文章，我仍然不太清楚哪个算法最适合我的目标。

- adrianmc

Answer 1

如果您想评估打字质量并希望训练学生做到零错误，您应该使用Levenshtein距离，因为它更加严格。

此外，Levenshtein分数更易于理解，并且比Jaro-Winkler结果更容易以图形方式表示。您可以修改Levenshtein算法以单独报告插入、删除和错误，并向最终用户显示更正列表。另一方面，Jaro-Winkler会给出一个难以向最终用户展示的得分，因为中间拼写错误的惩罚低于末尾的惩罚。

- Sergey Kalinichenko

Answer 2

略带玩笑，但只是略带：建立一个生成模型以打字，该模型给予敲击正确字母的高（先验）概率，并分配一些概率以同时敲击两个相邻键、以错误顺序从不同手敲击两个键、以错误顺序从同一手敲击两个键、敲击正确键附近的键、以及远离正确键的键等。或者更少的特定目的：为所需继续输入的当前键对给出一个给定按键序列的概率。这样的模型可以做很多事情；例如，通过为学习者的实际表现给出可能性得分，您可以获得“距离”类似的指标。但更好的是，给他们一个报告，总结他们最常犯什么类型的错误——毕竟，为什么要将他们的表现归结为单个数字，而不是用许多数字？如果您从真实打字员工作的大型语料库中学习不同类型错误的概率，则可以获得额外的奖励分数。

- Daniel Wagner

---

听起来像是一个很棒的开源项目想法。你开始建立代码库，我会做出贡献的。 - adrianmcli

我喜欢错误报告摘要的想法。对于我的打字，我猜测错误可能是： 1）来自不同手的字符顺序错误。 2）由于“相似单词”而拼错，“ron” -> “run”。 3）后缀添加，“run” -> “runs”。 - Breck Baldwin

Answer 3

我基本上同意dasblinkenlight的答案，但建议使用Damerau-Levenshtein distance而不是仅使用Levenshtein距离，即包括转置。转置在打字时非常频繁且容易出错，没有理由为什么它们应该相对于其他可能的错误（插入、删除和替换）承担双倍的距离惩罚。

- fnl