猜测...可能

1. 搜索词
2. 如果找不到，请使用某种算法尝试“猜测”该单词。

可能是来自AI之类的东西，例如Hopfield网络或反向传播网络，或者是其他“识别指纹”，恢复损坏的数据或Davide已经提到的拼写更正...

使用Levenshtein距离 ，然后创建一个Metric树（或Slim树）来索引单词。然后运行一个1-Nearest Neighbor查询，您得到了结果。

我前段时间找到了这篇文章： 如何编写拼写校正器 ，作者是Peter Norvig （Google Inc.的研究主管）。

这是有关“拼写更正”主题的有趣读物。这些示例是使用Python编写的，但是清楚易懂，我认为该算法可以轻松转换为其他语言。

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

第1步：准备-设置Word数据库

最好的办法是您可以使用实际的搜索词及其出现方式。如果您没有，可以使用大量文本来代替。计算每个单词的出现（受欢迎程度）。

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

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

从上一步中选择最受欢迎的单词，并提出更正建议（如果不是单词本身）。

Google显然建议查询结果最好，而不是拼写正确的查询。但是在这种情况下，拼写校正器可能会更可行。当然，您可以根据返回的结果如何的某种度量，为每个查询存储一些值。

所以，

1. 您需要字典（英语或根据您的数据）

2. 使用您的字典生成单词网格并计算转换的概率。

3. 添加一个解码器以使用您的网格计算最小错误距离。当然，在计算距离时，您应该注意插入和删除。有趣的是，如果您敲击彼此靠近的按键，QWERTY键盘会最大化距离（cae会变成汽车，cay会变成猫）

4. 返回距离最小的单词。

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

对于“您是不是要”算法的理论，您可以参考“信息检索简介”的第3章。它可以免费在线获得。 第3.3节 （第52页）准确地回答了您的问题。要专门回答您的更新，您只需要一个单词词典就可以了（包括数百万个用户）。

嗯...我以为Google用他们庞大的数据集（互联网）来做一些严肃的NLP（自然语言处理）。

例如，他们拥有来自整个互联网的大量数据，因此他们可以计算出三个单词序列（称为trigram ）出现的次数。因此，如果他们看到这样的句子：“粉红色节俭音乐会”，他们会发现它的点击率不高，然后在他们的语料库中找到最可能的“粉红色*音乐会”。

他们显然只是改变了Davide Gualano所说的话，因此一定要阅读该链接。 Google当然会使用它作为语料库的所有网页，因此这使其算法特别有效。

通常，生产拼写校正器会使用几种方法来提供拼写建议。一些是：

• 确定确定是否需要拼写更正的方法。这些可能包括结果不足，结果不够明确或不够准确（根据某种度量）等。然后：

• 使用大块的文本或字典，其中所有或大部分已知拼写正确。这些可以在网上轻松找到，例如LingPipe 。然后，要确定最佳建议，您需要根据几种度量寻找最匹配的单词。最直观的一个是相似字符。通过研究和实验表明，两个或三个字符序列匹配效果更好。 （字母和字母）。为了进一步提高结果，请在单词的开头或结尾对比赛进行加权。出于性能原因，将所有这些词索引为三字母组或双字母组，以便在执行查找时转换为n-gram，然后通过哈希表或trie查找。

• 根据字符位置，使用与潜在的键盘错误相关的试探法。因此，“ hwllo”应为“ hello”，因为“ w”接近“ e”。

• 使用语音键（Soundex，Metaphone）为单词建立索引并查找可能的更正。实际上，如上所述，这通常比使用n-gram索引返回更差的结果。

• 在每种情况下，您都必须从列表中选择最佳校正。这可以是距离度量，例如levenshtein，键盘度量等。

• 对于多词短语，可能只拼错了一个词，在这种情况下，您可以将其余词用作确定最佳匹配的上下文。

这是我发现的最佳答案 ，由Google研究总监Peter Norvig实施和描述的拼写校正器。

如果您想进一步了解其背后的理论，可以阅读他的书中的章节 。

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

这是直接来自来源的解释（差不多）

搜索101！

在22:03分钟

值得一看！

基本上，根据Google前CTO Douglas Merrill的说法，它是这样的：

1）您在Google中写了一个（拼写错误的）单词

2）您找不到想要的东西（不要单击任何结果）

3）您意识到拼写错误的单词，因此您在搜索框中重写了单词。

4）找到所需的内容（单击第一个链接）

此模式乘以数百万次，显示出最常见的错误拼写和最“常见”的更正。

这样，Google几乎可以即时提供每种语言的拼写校正。

这也意味着，如果一夜之间所有人都开始拼写“ nigth”，那么google会建议该单词代替。

编辑

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

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

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

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

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

请参阅此Google Wave演示 （@ 44m 06s），该演示显示了如何考虑上下文以自动更正拼写。

在此说明自然语言处理的工作方式。

最后，这是一个很棒的演示，演示如何将自动机器翻译 （@ 1h 12m 47s）添加到混合中。

_{我在视频中添加了分钟和秒的锚点，以直接跳至内容，如果它们不起作用，请尝试重新加载页面或手动滚动到标记。}

我的猜测是，他们结合使用了Levenshtein距离算法和他们收集的有关运行搜索的大量数据。他们可以从输入的搜索字符串中拉出一组Levenshtein距离最短的搜索，然后选择结果最多的搜索。