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

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

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

这是我找到的最好的答案，由谷歌的研究总监Peter Norvig实施和描述的拼写纠正器。

如果你想了解更多这背后的理论，你可以阅读他书中的章节。

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

我的猜测是，他们使用了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.