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

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

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

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

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

搜索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所说的一种变化，所以一定要阅读那个链接。谷歌当然使用它所知道的所有网页作为一个语料库，这使得它的算法特别有效。

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

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

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