自动补全算法？

Question

我指的是当用户在Google中键入搜索词时用于给出查询建议的算法。

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

我知道你可以使用Trie或广义trie来查找匹配，但它不能满足上述要求……

之前问过的类似问题here

Answer 1

有关(heh)令人惊叹的模糊/部分字符串匹配算法，请查看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个单词的trie，为该用户保留最近/前N个单词的trie。

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

苹果数据缓存查找结果:如果用户点击任何搜索结果，您可以非常快速地提供这些结果，然后异步获取完整的部分/模糊lookup.

• precompute查找结果:如果用户输入了"appl"，他们很可能会继续使用“”，"apply".
• prefetch
• ：例如，web应用程序可以向浏览器发送一组较小的结果，小到足以在JS中进行暴力搜索。

Answer 2

我只想说...这个问题的一个很好的解决方案是合并不止一个三元搜索树。Ngram和Shingles (短语)是必需的。还需要检测词边界错误。“地狱o”应该是“你好”...“白袜子”应该是“白袜子”--这些都是预处理步骤。如果你没有对数据进行适当的预处理，你将不会得到有价值的搜索结果。三元搜索树是一个很有用的组件，用于确定单词是什么，以及当输入的单词在索引中不是有效单词时实现相关单词猜测。

google算法执行短语建议和更正。google算法也有一些上下文的概念...如果你搜索的第一个单词是与天气相关的，你把它们组合在一起，"weatherforcst“、"monsoonfrcst”和"deskfrcst“--我的猜测是在幕后，基于遇到的第一个单词，建议中的排名正在改变--天气和天气是相关的单词，因此forecast get在Did- you -Mean猜测中排名很高。

单词分词(Ngram)，短语术语(shingles)，单词邻近度(单词聚类索引)，三元搜索树(单词查找)。

Answer 3

谷歌的确切算法尚不清楚，但it is said的工作原理是通过统计分析用户的输入。一种不适合大多数情况的方法。更常见的情况是使用以下方法之一实现自动完成：

• Trees.通过在树结构(前缀树、后缀树、dawg等)中索引可搜索文本人们可以以牺牲内存存储为代价来执行非常快的搜索。树遍历法可以适用于近似的matching.
• Pattern分区。通过将文本划分为标记(Ngram)，可以使用简单的散列scheme.
• Filtering.执行模式匹配搜索找到一组潜在的匹配项，然后应用顺序算法检查每个候选项。

看看completely，这是一个Java autocomplete库，它实现了后面的一些概念。