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

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

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

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

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.

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

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

搜索101 !

在分钟 22：03

值得一看!

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

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

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

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

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

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

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

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

EDIT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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