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

搜索101 !

在分钟 22：03

值得一看!

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

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

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

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

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

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

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

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

EDIT

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

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

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

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

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

请看谷歌wave (@ 44m06 s)的演示，它展示了如何考虑上下文来自动纠正拼写。

这里将解释自然语言处理是如何工作的。

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

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

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

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

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

我猜…它可以

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

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

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

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

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

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

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

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

So,

You need a dictionary (english or based on your data) Generate a word trellis and calculate probabilities for the transitions using your dictionary. Add a decoder to calculate minimum error distance using your trellis. Of course you should take care of insertions and deletions when calculating distances. Fun thing is that QWERTY keyboard maximizes the distance if you hit keys close to each other.(cae would turn car, cay would turn cat) Return the word which has the minimum distance. Then you could compare that to your query database and check if there is better results for other close matches.