自动完成算法? [英] Algorithm for autocomplete?

问题描述

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

I am referring to the algorithm that is used to give query suggestions when a user types a search term in Google.

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

I am mainly interested in: 1. Most important results (most likely queries rather than anything that matches) 2. Match substrings 3. Fuzzy matches

我知道您可以使用 Trie 或通用 trie 来查找匹配项，但它不符合上述要求...

I know you could use Trie or generalized trie to find matches, but it wouldn't meet the above requirements...

之前提出的类似问题此处

Similar questions asked earlier here

推荐答案

对于(呵呵)很棒的模糊/部分字符串匹配算法，请查看该死的酷算法:

For (heh) awesome fuzzy/partial string matching algorithms, check out Damn Cool Algorithms:

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

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

These don't replace tries, but rather prevent brute-force lookups in tries - which is still a huge win. Next, you probably want a way to bound the size of the trie:

• 保留最近/最常用的 N 个全球使用的词；
• 对于每个用户，为该用户保留最近/排名前 N 的单词.

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

Finally, you want to prevent lookups whenever possible...

• 缓存查找结果:如果用户点击任何搜索结果，您可以非常快速地提供这些结果，然后异步获取完整的部分/模糊查找.
• 预先计算查找结果:如果用户输入了appl"，他们很可能会继续输入apple"、apply".
• 预取数据:例如，网络应用程序可以向浏览器发送较小的结果集，小到足以在 JS 中进行暴力搜索.

这篇关于自动完成算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！