现实世界的错别字统计？

Question

我在哪里可以找到一些真实世界的打字错误统计数据呢？

我正在尝试将人们输入的文本与内部对象匹配，而人们往往会犯拼写错误。
有两种类型的错误：

1. 打字错误 - "Helllo" 而不是 "Hello" / "Satudray" 而不是 "Saturday" 等。
2. 拼写错误 - "Shikago" 而不是 "Chicago"

我使用Damerau-Levenshtein距离处理打字错误和双重音形码处理拼写错误（Python实现在这里和在这里）。

我想专注于Damerau-Levenshtein算法（或简称为 编辑距离）。教科书中的实现总是将删除、插入、替换和转置的权重设置为1。虽然这很简单并且可以使用好的算法，但它并不符合"现实"或"真实世界的概率"。

示例：

• 我确信 "Helllo"（"Hello"）的可能性比 "Helzlo" 更大，但它们都是1步编辑距离。
• "Gello" 比 "Qello" 在 QWERTY 键盘上更接近 "Hello"。
• Unicode音译： "München" 和 "Munchen" 之间的"真实"距离是多少？

删除、插入、替换和转置的 "真实世界" 权重应该是多少呢？

即使Norvig的很酷的拼写纠正器也使用非加权编辑距离。

顺便说一句-我确信这些权重需要是函数而不是简单的浮点数（根据上述例子）...

我可以调整算法，但我在哪里可以“学习”这些权重？我没有访问Google规模的数据...

我应该猜测它们吗？

编辑-试图回答用户问题：

• 我的当前非加权算法经常在面对上述原因的错别字时失败。 “Return on Tursday”：每个“真人”都可以轻松地发现周四比周二更有可能，但它们都只相差1个编辑距离！ （是的，我记录并衡量我的表现）。
• 我正在开发一个NLP旅行搜索引擎，因此我的词典包含大约25K个目的地（预计将增长到100K），时间表达式约200（预计1K），人物表达式约100（预计300），货币表达式约100（预计500），“胶水逻辑单词”（“from”，“beautiful”，“apartment”）约2K（预计10K）等。
• 每个上述单词组的编辑距离使用方式不同。我尝试在明显情况下“自动纠正”，例如与字典中仅1个其他单词相差1个编辑距离。我有许多其他手动调整的规则，例如Double Metaphone修复，其与长度> 4的字典单词的编辑距离不超过2个...规则列表随着我从真实世界输入中学习而不断增长。

"在您的门槛内有多少对字典条目？"：好吧，这取决于“花哨的加权系统”和现实世界（未来）的输入，不是吗？无论如何，我有广泛的单元测试，以便对系统进行的每一次更改都只会使它变得更好（当然是基于过去的输入）。大多数少于6个字母的单词与另一个字典条目相隔1个编辑距离。

当有2个字典条目与输入距离相同时，我尝试应用各种统计方法来更好地猜测用户想要的是哪个（例如，巴黎，法国比伊朗的Pārīz更有可能出现在我的搜索结果中）。

选择错误的单词的代价是向最终用户返回半随机（经常荒谬的）结果，并可能失去客户。不理解的代价稍微便宜一些：用户将被要求重新表述。

复杂性的代价是否值得？是的，我确信是的。你不会相信人们给系统投入的错别字量，他们期望它能够理解，而我完全可以利用精确度和召回率的提高。

- Tal Weiss

---

也许微软进行了一项研究（尽管Word的拼写更正并不像智能，事实上我认为它只是根据常见错误列表检查每个拼写）。此外，谷歌非常致力于开源开发，如果你礼貌地提出请求，也许他们会给你这样的数据？ - Rafe Kettler

那些谷歌规模的数据很有趣。它是可以访问和查询的吗，还是只是一个示例页面？ - Caleb Hearth

如果你在权重计算中考虑按键的相邻关系，可能会有所帮助。在 QWERTY 键盘上，因为 q 键靠近“正确”的 o 键，所以更容易发生打错 Hellp 的情况，而不是打错 Hellz。 - Jason Hall

尽管我同意错别字频率会很有用，但是找到这种频率数据将会很困难，因为它本质上是主观的。 "现实世界"概率的问题在于"现实世界"是一个非常大的地方。小学生的错误频率分布与从事应收账款工作的中年妇女不同，而后者又与大学英语教授不同。找到适合您问题域的"平均值"将不是一件容易的事情。 - Cerin

那是除非你在推特上，这个伟大的平等者。 - VoronoiPotato

Answer 1

可能可以从维基百科的完整编辑历史中获取真实世界的错别字统计数据。 http://download.wikimedia.org/ 此外，您可能会对AWB的RegExTypoFix感兴趣。 http://en.wikipedia.org/wiki/Wikipedia:AWB/T

- tszming

---

非常有趣！我一定会研究一下这个！ - Tal Weiss

我等了一会儿，到目前为止这是最好的答案。谢谢！ - Tal Weiss

Answer 2

我建议您查看 trigram算法。在我看来，它比编辑距离算法更适合查找拼写错误。它应该也更快，并且如果您将字典保存在postgres数据库中，则可以利用索引。

您可能会发现stackoverflow上有关谷歌“Did you mean”算法的主题很有用。

- jethro

Answer 3

Church和Gale的拼写纠正概率评分 可能会有所帮助。在那篇论文中，作者将打字错误建模为作者和计算机之间的噪声信道。附录中列出了Associated Press出版物语料库中出现的打字错误表格。每种打字错误都有一个表格，包括：

• 删除
• 插入
• 替换
• 转位

例如，检查插入表格，我们可以看到l在l后面被错误地插入了128次（该列中最高的数字）。使用这些表格，您可以生成所需的概率。

- mndrix

---

链接已失效 - 在这里找到它： http://www.denizyuret.com/ref/church/published_1991_hand.ps.gz - Tal Weiss

Answer 4

如果研究是您的兴趣，我认为继续使用那个算法，并尝试找到合适的权重将会很有成果。

我无法帮助您处理错别字的统计，但我认为您也应该尝试使用Python的difflib库。具体来说，可以使用SequenceMatcher的ratio()方法。它使用一种算法，文档http://docs.python.org/library/difflib.html声称这种算法非常适合查找“看起来正确”的匹配项，并且可能有助于增强或测试您正在进行的工作。

对于只想查找错别字的Python程序员来说，这是一个很好的起点。我的一个同事已经使用了Levenshtein编辑距离和SequenceMatcher的ratio()方法，并从ratio()方法中获得了更好的结果。

- JivanAmara

Answer 5

一些问题供您思考，以帮助您确定是否应该询问“如何找到真实世界的权重”问题：

您是否实际测量了均匀赋权实现的有效性？如何进行的测量？

您有多少个不同的“内部对象” - 即您的字典大小是多少？

您实际上如何使用编辑距离（如John/Joan、Marmaduke/Marmeduke、Featherstonehaugh/Featherstonhaugh）：是“全部1个错误”，还是25％/11.1％/5.9％的差异？您正在使用什么阈值？

在您的阈值内有多少对字典条目（例如John与Joan、Joan与Juan等）？如果引入了花哨的加权系统，有多少对字典条目会迁移（a）从阈值内到外（b）反之亦然？

如果您的字典中都有John和Juan，而用户输入了Joan，您会怎么做？

选择错误的字典单词（而不是用户所需的单词）的惩罚/成本是什么（1）（2）未能识别用户的输入？

引入一个复杂的加权系统是否能够有效地降低上述两种错误类型的概率，使得这种复杂性和较慢的速度值得？

顺便问一下，您怎么知道用户使用的键盘？

更新：

“”“我的当前非加权算法由于上述原因在面对打字错误时经常失败。“Return on Tursday”：每个“真人”都可以轻松判断星期四比星期二更有可能，但它们都是1个编辑距离！（是的，我记录并测量我的表现）。 “””

是的，通过省略“h”，Thursday -> Tursday，但是通过用“r”替换“e”，Tuesday -> Tursday。 在qwERty和azERty键盘上，E和R相邻。 每个“真人”都可以轻松猜测星期四比星期二更有可能。即使统计数据和猜测都指向星期四比星期二更有可能（也许省略h将花费0.5，e->r将花费0.75），差异（也许为0.25）是否足以始终选择星期四？您的系统是否可以/会询问“您是否指的是星期二？”还是只会坚持星期四？

- John Machin

---

好问题。我故意省略了一些答案，以使问题更加通用并对其他用户有兴趣...无论如何，我会编辑问题来尝试回答它们。 - Tal Weiss

我不知道用户使用的是哪种键盘，但我肯定QWERTY变体比Dvorak更常见。 - Tal Weiss