4

我们都在 Google 中看到，如果我们输入查询并打错字，Google 会建议使用更合理的查询版本（这通常是正确的）。现在他们是怎么做到的？我能想到的一种可能方法是找出与给定字符串编辑距离为 1 的所有其他字符串，如果其中任何一个返回具有更高值“搜索”属性的字符串（可能来自后端数据库，每个索引查询词都有一个权重，基于该词在查询中出现的频率）而不是给定的字符串，建议使用该字符串。如果没有找到，则搜索编辑距离为 2 的字符串，依此类推，直到在 5 处，SE 确定该字符串可能是用户正在查找的字符串，并返回相应的搜索结果。

现在有可能在给定字符串的给定编辑距离处找到字符串吗？这个过程的效率如何？有什么很酷的算法可以做到这一点吗？

4

2 回答 2

2

Peter Norvig 的一篇有趣的文章“如何编写拼写校正器”谈论“你的意思是”如何工作

于 2012-10-15T14:27:29.630 回答
1

这当然是猜测，但可以肯定的是，谷歌有一个庞大的统计基础来猜测正确的单词。上下文可能是另一个取决于其他词的因素。

所以我的猜测是，他们使用的算法首先根据所有单词确定可能的上下文，然后统计查找给定上下文中正确单词的错别字变体。如果没有上下文（单个单词），他们可能会查找任何可能相似的内容。

此外，由于 Google 使用基于 MySQL 的数据库，他们还可以使用SOUNDS LIKE功能，该功能会根据人声列出听起来相似的单词。

于 2012-10-14T22:53:01.437 回答