41

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

我试图将人们的输入文本与内部对象相匹配，而人们往往会犯拼写错误。
有2种错误：

  1. typos- “你好”而不是“你好”/“星期六”而不是“星期六”等。
  2. Spelling- “Shikago”而不是“Chicago”

我将 Damerau-Levenshtein 距离用于拼写错误，使用Double Metaphone进行拼写（此处和此处的 Python 实现）。

我想专注于 Damerau-Levenshtein（或简单地说edit-distance）。教科书的实现总是使用“1”作为删除、插入替换和转置的权重。虽然这很简单并且允许使用很好的算法，但它与“现实”/“现实世界的概率”不匹配。

例子：

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

删除、插入、替换和转座的“真实世界”权重应该是多少？

即使是Norvig 非常酷的拼写校正器也使用非加权编辑距离。

顺便说一句-我确定权重需要是函数而不是简单的浮点数（根据上面的示例）...

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

我应该猜他们吗？

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

  • 由于上述原因，我当前的非加权算法在遇到拼写错误时经常失败。“周四回归”：每个“真人”都可以轻松判断周四比周二更有可能，但他们都在 1 编辑距离之内！（是的，我会记录并衡量我的表现）。
  • 我正在开发一个 NLP 旅行搜索引擎，所以我的字典包含 ~25K 目的地（预计增长到 100K）、时间表达式 ~200（预计 1K）、人物表达式 ~100（预计 300）、金钱表达式 ~100（预计 500 )、“粘合逻辑词”（“from”、“beautiful”、“apartment”）~2K（预计10K）等等……
  • 对于上述每个词组，编辑距离的使用是不同的。我尝试“在明显时自动更正”，例如与字典中仅 1 个其他单词相距 1 个编辑距离。我还有许多其他手动调整的规则，例如 Double Metaphone 修复，它与长度 > 4 的字典单词的编辑距离不超过 2...随着我从现实世界的输入中学习，规则列表继续增长。
  • “你的阈值内有多少对字典条目？”：嗯，这取决于“花式加权系统”和现实世界（未来）的输入，不是吗？无论如何，我进行了大量的单元测试，因此我对系统所做的每一次更改都只会让它变得更好（当然，基于过去的输入）。大多数低于 6 个字母的单词与一个单词的编辑距离在 1 个编辑距离之内，而该单词与另一个字典条目的编辑距离为 1 个编辑距离。
  • 今天，当有 2 个字典条目与输入的距离相同时，我尝试应用各种统计数据来更好地猜测用户的意思（例如，法国巴黎比伊朗巴黎更可能出现在我的搜索中）。
  • 选择错误单词的代价是向最终用户返回半随机（通常是荒谬的）结果，并可能失去客户。不理解的成本略低：将要求用户重新措辞。
  • 复杂性的代价值得吗？是的，我敢肯定。您不会相信人们向系统抛出的拼写错误数量并期望它能够理解，而且我肯定可以使用Precision 和 Recall的提升。
4

5 回答 5

14

现实世界中的错字统计可能来自维基百科的完整编辑历史。

http://download.wikimedia.org/

此外，您可能对 AWB 的 RegExTypoFix 感兴趣

http://en.wikipedia.org/wiki/Wikipedia:AWB/T

于 2010-08-07T07:19:13.220 回答
8

我会建议你检查trigram alogrithm。在我看来，它更适合查找错别字然后编辑距离算法。它也应该工作得更快，如果你在 postgres 数据库中保存字典，你可以使用 index.html。

你可能会发现关于谷歌“你的意思是”的有用的stackoverflow主题

于 2010-08-05T21:57:13.157 回答
5

Church 和 Gale对拼写纠正的概率评分可能会有所帮助。在那篇论文中，作者将拼写错误建模为作者和计算机之间的嘈杂通道。附录包含美联社出版物语料库中出现的拼写错误表格。以下每种错别字都有一个表格：

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

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

于 2012-06-05T16:49:55.580 回答
2

如果研究是您的兴趣，我认为继续使用该算法，尝试找到合适的权重将是富有成效的。

我无法帮助您解决拼写错误，但我认为您还应该使用 python 的 difflib。具体来说就是 SequenceMatcher 的 ratio() 方法。它使用文档http://docs.python.org/library/difflib.html声称非常适合匹配“看起来正确”的算法，并且可能有助于增强或测试您正在做的事情。

对于只寻找拼写错误的 Python 程序员来说，这是一个很好的起点。我的一位同事使用了 Levenshtein 编辑距离和 SequenceMatcher 的 ratio()，并从 ratio() 获得了更好的结果。

于 2010-08-06T08:43:23.347 回答
1

给您一些问题，以帮助您确定是否应该问“我在哪里可以找到真实世界的权重”的问题：

您是否实际测量过统一加权实施的有效性？如何？

你有多少不同的“内部对象”——即你的字典有多大？

您实际上是如何使用编辑距离的，例如 John/Joan、Marmaduke/Marmeduke、Featherstonehaugh/Featherstonhaugh：是“全 1 错误”还是 25% / 11.1% / 5.9% 的差异？你用的是什么门槛？

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

如果 John 和 Juan 在您的字典中并且用户键入 Joan，您会怎么做？

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

引入一个复杂的加权系统实际上是否会充分降低上述两种错误类型的概率，从而使复杂性和较慢的速度值得？

顺便说一句，你怎么知道用户使用的是什么键盘？

更新：

“”“由于上述原因，我目前的非加权算法在遇到拼写错误时经常失败。“周四返回”：每个“真实的人”都可以很容易地看出周四比周二更有可能，但它们都是 1-edit-distance离开！（是的，我会记录并衡量我的表现）。"""

是的，星期四 -> 星期四通过省略“h”，但星期二 -> 星期四通过替换“r”而不是“e”。E 和 R 在 qwERty 和 azERty 键盘上彼此相邻。每个“真人”都可以很容易地猜到星期四比星期二更有可能。即使统计数据和猜测表明星期四比星期二更有可能（也许省略 h 将花费 0.5 并且 e->r 将花费 0.75），差异（也许 0.25）是否足够显着以总是选择星期四？你的系统可以/会问“你的意思是星期二吗？” 或者它会在星期四继续前进吗？

于 2010-08-06T02:10:48.647 回答