自动完成算法？

Question

我指的是当用户在Google中键入搜索字词时用于提供查询建议的算法.

我主要感兴趣的是:1.最重要的结果(最有可能是查询而不是匹配的任何东西)2.匹配子串3.模糊匹配

我知道你可以使用Trie或generalized trie来找到匹配,但它不符合上述要求......

这里提到类似的问题

Answer 1

对于(嘿)令人敬畏的模糊/部分字符串匹配算法,请查看Damn Cool算法:

• http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

这些不会取代尝试,而是在尝试中防止暴力查找 - 这仍然是一个巨大的胜利.接下来,您可能想要一种限制trie大小的方法:

• 保持全球使用的最近/前N个词;
• 对于每个用户,请为该用户保留最近/前N个单词.

最后,您希望尽可能防止查找...

• 缓存查找结果:如果用户点击任何搜索结果,您可以非常快速地提供服务,然后异步获取完整的部分/模糊查找.
• 预计算查找结果:如果用户键入了"appl",则他们可能会继续使用"apple","apply".
• 预取数据:例如,一个Web应用程序可以向浏览器发送一小组结果,小到可以在JS中进行暴力搜索.

Answer 2

我只想说......这个问题的一个很好的解决方案是不仅仅包含三元搜索树.需要Ngrams和Shingles(Phrases).还需要检测字边界错误."地狱o"应该是"你好"......而"whitesocks"应该是"白袜子" - 这些都是预处理步骤.如果您没有正确预处理数据,那么您将无法获得有价值的搜索结果.三元搜索树是确定单词是什么的有用组件,也是当键入的单词不是索引中的有效单词时实现相关单词猜测的有用组件.

谷歌算法执行短语建议和更正.谷歌算法也有一些上下文的概念...如果你搜索的第一个单词是天气相关的,你将它们结合起来"weatherforcst"vs"monsoonfrcst"vs"deskfrcst" - 我的猜测是在幕后排名正在改变基于遇到的第一个单词的建议 - 预测和天气是相关的单词,因此预测得到了在你的平均猜测中的高排名.

word-partials(ngrams),短语 - 术语(shingles),word-proximity(word-clustering-index),三元搜索树(word-lookup).

Answer 3

Google的确切算法尚不清楚，但据说可以通过对用户输入的统计分析来起作用。一种不适用于大多数情况的方法。更常见的是，自动完成使用以下一种方法实现：

• 树木。通过在树结构（前缀树，后缀树，dawg等）中索引可搜索的文本，可以执行非常快速的搜索，但会浪费内存。可以将树遍历用于近似匹配。
• 模式分区。通过将文本划分为标记（ngram），可以使用简单的哈希方案对模式出现进行搜索。
• 过滤。找到一组潜在的匹配项，然后应用顺序算法检查每个候选者。

看一看完全的Java的自动完成库，它实现了后面的一些概念。

Answer 4

soundex和levenshtein distance等工具可用于查找特定范围内的模糊匹配。

Soundex 查找听起来相似的单词，levenshtein distance 查找与另一个单词在一定编辑距离内的单词。