你的意思是什么?算法的工作吗?

小开

我在前段时间发现了这篇文章:如何编写拼写纠正器 . 0，由Peter Norvig(谷歌公司的研究总监)撰写。

这是一篇关于“拼写纠正”主题的有趣文章。例子是用Python写的，但是很清楚，很容易理解，而且我认为算法可以很容易翻译成其他语言

下面是算法的简短描述。该算法包括两个步骤，准备和单词检查

步骤1:准备-设置word数据库

最好的情况是你可以使用实际的搜索词和它们的出现。如果你没有，你可以用大量的文本来代替。计算每个单词的出现次数(流行度)

步骤2。单词检查-找到与被检查的单词相似的单词

相似意味着编辑距离很低(通常是0-1或0-2)。编辑距离是将一个单词转换为另一个单词所需的插入/删除/更改/交换的最小数量。

从上一步中选择一个最流行的词，并建议它作为更正(如果不是这个词本身的话)。

小开

我猜…它可以

寻找词语
如果没有找到，使用一些算法来尝试“猜测”这个词。

可能是来自人工智能的东西，比如Hopfield网络或反向传播网络，或者其他“识别指纹”，恢复损坏的数据，或者Davide已经提到的拼写纠正……

小开

嗯…我认为谷歌使用他们庞大的数据语料库(互联网)来做一些严肃的NLP(自然语言处理)。

例如，他们有来自整个互联网的大量数据，以至于他们可以计算出三个单词序列出现的次数(称为卦)。因此，如果他们看到一个句子:“pink frugr concert”，他们可以看到它的点击率很少，然后在语料库中找到最有可能的“pink * concert”。

他们显然只是做了Davide Gualano所说的一种变化，所以一定要阅读那个链接。谷歌当然使用它所知道的所有网页作为一个语料库，这使得它的算法特别有效。

小开

几年前我在这方面看到过一些东西，所以可能已经改变了，但显然他们是通过分析相同用户在短时间内提交非常相似的查询的日志开始的，并根据用户如何纠正自己使用机器学习。

小开

简单。他们有吨的数据。他们有每一个可能的术语的统计数据，基于它被查询的频率，以及它的什么变化通常会产生用户点击的结果……因此，当他们看到你在搜索词中经常拼写错误时，他们会提出更常见的答案。

实际上，如果拼写错误实际上是搜索频率最高的词，算法就会把它当成正确的词。

小开

我的猜测是，他们使用Levenshtein距离算法和他们收集的关于正在运行的搜索的大量数据的组合。他们可以提取一组与输入的搜索字符串的Levenshtein距离最短的搜索，然后选择结果最多的搜索。

小开

最佳答案

以下是直接来自来源的解释(几乎)

搜索101!< / >

最少22:03

值得一看!

基本上，根据谷歌前CTO Douglas Merrill的说法，它是这样的:

1)你在谷歌里写了一个(拼错的)单词

2)你找不到你想要的(不要点击任何结果)

3)你意识到你拼错了这个词，所以你在搜索框里重写了这个词。

4)你找到你想要的(你点击第一个链接)

这个模式乘以数百万次，显示了什么是最常见的拼写错误，什么是最“常见”的更正。

这样谷歌几乎可以立即提供每种语言的拼写纠正。

这也意味着如果一夜之间每个人都开始把night拼成“nigth”，谷歌会建议用这个词来代替。

编辑

道格拉斯将其描述为“统计机器学习”。

他们知道谁更正了查询，因为他们知道哪个查询来自哪个用户(使用cookie)

如果用户执行查询，只有10%的用户点击了结果，而90%的用户返回并输入了另一个查询(带有更正的单词)，这一次90%的用户点击了结果，那么他们知道他们已经找到了更正。

它们还可以知道这些是否是两个不同的“相关”查询，因为它们拥有它们所显示的所有链接的信息。

此外，他们现在将上下文纳入拼写检查，因此他们甚至可以根据上下文建议不同的单词。

请看这个演示谷歌波 (@ 44m06s)，它显示了如何考虑上下文来自动更正拼写。

在这里解释了自然语言处理如何工作。

最后，这里有一个很棒的演示，可以做什么添加自动机器翻译 (@ 1h 12m 47s)到混合。

< p > <子> 我已经在视频中添加了分钟和秒的锚，可以直接跳到内容，如果它们不起作用，可以尝试重新加载页面或手动滚动到标记处。 < / sub > < / p >

小开

关于“did you mean”算法的理论可以参考《信息检索导论》第3章。在线是免费的。3.3节(第52页)准确地回答了你的问题。为了明确回答你的更新，你只需要一个单词字典，不需要其他任何东西(包括数百万用户)。

小开

关于你的问题，如何在没有大量数据的情况下模仿行为——为什么不使用谷歌收集的大量数据呢?下载拼写错误的单词的谷歌sarch结果，搜索“;你的意思是:"在HTML中。

我猜现在这叫做混搭:-)

小开

最简单的方法是动态规划。

这是一种从信息检索中借来的算法，在现代生物信息学中大量使用，以查看两个基因序列有多相似。

最优解采用动态规划和递归。

这是一个已经解决的问题，有很多解决方案。在你找到一些开源代码之前，一直在你的周围打转。

小开

谷歌显然建议搜索结果最好的问题，而不是拼写正确的问题。但在这种情况下，可能拼写纠正器会更可行。当然，您可以为每个查询存储一些值，基于它返回的结果有多好。

所以,

你需要一本字典(英文或根据你的资料)

生成一个单词网格，并使用字典计算转换的概率。

添加一个解码器来计算使用网格的最小误差距离。当然，在计算距离时，您应该注意插入和删除。有趣的是，QWERTY键盘最大限度地距离，如果你击中彼此的关键。(cae会变成汽车，cay会变成猫)

返回距离最小的单词。

然后您可以将其与查询数据库进行比较，并检查是否有其他相近匹配的更好结果。

小开

通常，产品拼写纠正器会使用几种方法来提供拼写建议。一些人:

决定一种方法来确定是否需要拼写纠正。这些可能包括不充分的结果、不够具体或不够准确的结果(根据某种衡量标准)等等。然后:

使用大量的文本或字典，其中所有或大部分都是正确的拼写。这些很容易在网上找到，比如LingPipe。然后，为了确定最佳建议，你要根据几个衡量标准来寻找一个最接近的词。最直观的是相似字符。研究和实验表明，两三个字符序列匹配效果更好。(二字和三字)。为了进一步提高结果，可以在单词的开头或结尾权衡一个更高的分数。出于性能考虑，请将所有这些单词索引为三元组或三元组，以便在执行查找时转换为n-三元组，并通过哈希表或trie进行查找。

使用与基于字符位置的潜在键盘错误相关的启发式方法。所以"hwllo"应该是"hello"因为" w "很接近" e "

使用语音键(Soundex, Metaphone)来索引单词并查找可能的更正。在实践中，这通常比使用n-gram索引返回更差的结果，如上所述。

在每种情况下，您必须从列表中选择最佳修正。这可能是一个距离度量，如levenshtein，键盘度量等。

对于一个多词短语，可能只有一个单词拼写错误，在这种情况下，您可以使用其余单词作为上下文来确定最佳匹配。

小开

有一个特定的数据结构——三元搜索树——自然地支持部分匹配和近邻匹配。

小开

使用Levenshtein距离，然后创建一个度量树(或纤细树)来索引单词。然后运行1-Nearest Neighbour查询，得到结果

小开

你是说拼写检查器?如果它是一个拼写检查器而不是一个完整的短语，那么我有一个关于拼写检查的链接，其中算法是用python开发的。检查这个链接

同时，我也在从事一个项目，包括使用文本搜索数据库。我想这能解决你的问题

小开

这是一个老问题，我很惊讶没有人建议OP使用Apache Solr。

Apache Solr是一个全文搜索引擎，除了许多其他功能，还提供拼写检查或查询建议。从文档:

默认情况下，Lucene拼写检查器首先根据分由弦距计算和秒由频
.(如果有)索引中的建议

小开

这里是我找到的最好答案，拼写纠正器实现和描述的谷歌的研究主任彼得诺维格。

如果你想阅读更多关于这背后的理论，你可以阅读他的书。

该算法的思想基于统计机器学习。

小开

除了上面的答案，如果你想自己快速实现一些东西，这里有一个建议-

算法

你可以在GitHub上找到这个算法的实现和详细文档。

创建带有比较器的优先级队列。
创建一个Ternay搜索树，插入所有英语单词(从Norvig的文章开始)及其频率。
开始遍历TST，对于TST中遇到的每个单词，从input_word计算它的Levenshtein距离(LD)
如果LD ≤3然后把它放在优先队列中。
最后从优先队列中提取10个单词并显示。