自动完成的algorithm？
我指的是当用户在Google中inputsearch词时，用于提供查询build议的algorithm。
我主要感兴趣的是谷歌的algorithm能够显示：1.最重要的结果（最有可能的查询，而不是任何匹配）2.匹配子string3.模糊匹配
我知道你可以使用Trie或者通用的trie来寻找匹配，但是它不能满足上面的要求。
本文前面提到的类似问题
对于（赫赫）真棒模糊/部分string匹配algorithm，检查出该死的algorithm：
- 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个单词的特里结构。
最后，你想尽可能地防止查找…
- caching查找结果：如果用户点击任何search结果，则可以非常快地提供服务，然后asynchronous获取完整的部分/模糊查找。
- 预先计算的查询结果：如果用户input了“appl”，他们可能继续“apple”，“apply”。
- 预取数据：例如，一个networking应用程序可以发送一个较小的结果集到浏览器，足够小，使JSpowershellsearch可行。
我只想说…这个问题的一个好的解决scheme将会包含多于一个三元search树。 Ngrams和Shingles（短语）是必要的。 还需要检测字边界错误。 “hell o”应该是“hello”，而“whitesocks”应该是“white socks” – 这是预处理步骤。 如果你没有正确地预处理数据，你不会得到有价值的search结果。 三元search树是计算什么是单词的有用组件，也可用于在input的单词不是索引中的有效单词时执行相关单词猜测。
谷歌algorithm执行短语build议和更正。 谷歌algorithm也有一些上下文的概念…如果你search的第一个词是天气相关的，你结合他们“weatherforcst”vs“monsoonfrcst”vs“deskfrcst” – 我的猜测是在幕后排名正在改变基于遇到的第一个词的build议 – 预测和天气是相关的词，因此预测在Did-You-Mean猜测中得到很高的排名。
单词部分（ngrams），短语术语（带状疱疹），单词接近（单词聚类索引），三元search树（单词查找）。
有像soundex和levenshtein距离这样的工具可以用来find一定范围内的模糊匹配。
Soundexfind听起来相似的单词，levenshtein距离find与另一个单词相距一定编辑距离的单词。
看看Firefox的真棒栏algorithm
谷歌build议是有用的，因为它需要考虑到数以百万计的stream行查询+过去相关的查询。
它没有一个很好的完成algorithm/用户界面：
- 不做子串
- 看起来像一个相对简单的词边界前缀algorithm。
例如：尝试tomcat tut– >正确提示“tomcat tutorial”。 现在尝试tomcat rial– >没有build议） – ： - 不支持“你的意思是？ – 在谷歌search结果。
对于子串和模糊匹配，Levenshtein距离algorithm对我来说工作得相当好。 虽然我承认这似乎不像自动完成/build议的行业实现那样完美。 谷歌和微软的Intellisense都做得更好，我认为是因为他们已经完善了这个基本的algorithm来衡量匹配不同string所需的编辑操作。 例如，转换两个字符应该只能算作1个操作，而不是2个（插入和删除）。
但即使如此，我觉得这已经足够接近了。 这是它在C＃中的实现…
// This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make // it more like Google's autocomplete/suggest. It returns the number of operations // (insert/delete/substitute) required to change one string into another, with the // expectation that userTyped is only a partial version of fullEntry. // Gives us a measurement of how similar the two strings are. public static int EditDistance(string userTyped, string fullEntry) { if (userTyped.Length == 0) // all entries are assumed to be fully legit possibilities return 0; // at this point, because the user hasn't typed anything. var inx = fullEntry.IndexOf(userTyped[0]); if (inx < 0) // If the 1st character doesn't exist anywhere in the entry, it's not return Int32.MaxValue; // a possible match. var lastInx = inx; var lastMatchCount = 0; TryAgain: // Is there a better starting point? var len = fullEntry.Length - inx; var matchCount = 1; var k = 1; for (; k < len; k++) { if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx]) { if (matchCount > lastMatchCount) { lastMatchCount = matchCount; lastInx = inx; } inx = fullEntry.IndexOf(userTyped[0], inx + 1); matchCount = 0; if (inx > 0) goto TryAgain; else break; } else matchCount++; } if (k == len && matchCount > lastMatchCount) lastInx = inx; if (lastInx > 0) fullEntry = fullEntry.Substring(lastInx); // Jump to 1st character match, ignoring previous values // The start of the Levenshtein Distance algorithem. var m = userTyped.Length; var n = Math.Min(m, fullEntry.Length); int[,] d = new int[m + 1, n + 1]; // "distance" - meaning number of operations. for (var i = 0; i <= m; i++) d[i, 0] = i; // the distance of any first string to an empty second string for (var j = 0; j <= n; j++) d[0, j] = j; // the distance of any second string to an empty first string for (var j = 1; j <= n; j++) for (var i = 1; i <= m; i++) if (userTyped[i - 1] == fullEntry[j - 1]) d[i, j] = d[i - 1, j - 1]; // no operation required else d[i, j] = Math.Min ( d[i - 1, j] + 1, // a deletion Math.Min( d[i, j - 1] + 1, // an insertion d[i - 1, j - 1] + 1 // a substitution ) ); return d[m, n]; }
谷歌的确切algorithm是未知的，但据说通过用户input的统计分析工作。 一种不适合大多数情况的方法。 更常见的自动完成是使用以下之一来实现的：
- 树木 。 通过将可search的文本索引在树结构（前缀树，后缀树，dawg等）中，可以执行非常快速的search，代价是存储器存储。 树遍历可以适应近似匹配。
- 模式分区 。 通过将文本划分为令牌（ngrams），可以使用简单的哈希scheme执行对模式发生的search。
- 过滤 。 find一组潜在的匹配，然后应用顺序algorithm来检查每个候选人。
完整地看一下实现了后面一些概念的Java自动完成库。
我认为，build立一个专门的线索可能会更好，而不是追求完全不同的数据结构。
我可以看到，这个functionperformance在每一片叶子都有一个反映其相应单词search频率的字段中。
search查询方法将显示具有最大值的后代叶节点，所述最大值是通过将与每个后代叶节点的距离乘以与每个后代叶节点相关联的search频率来计算的。
Google使用的数据结构（以及algorithm）可能会复杂得多，可能会涉及到大量其他因素，例如从您自己的特定帐户search频率（以及时间和天气…季节…和月相……和…）。 然而，我相信基本特里数据结构可以扩展到任何types的专门的search偏好，包括每个节点的附加字段，并在search查询方法中使用这些字段。
如果您正在为此问题寻找整体devise，请尝试阅读https://www.interviewbit.com/problems/search-typeahead/上的内容。;
他们首先通过一种天真的方法来构build自动完成，然后使用一个trie，然后构build它。 他们还解释了采样和离线更新等优化技术，以满足特定用例的需求。
为了保持解决scheme的可伸缩性，您必须智能地分割您的数据库数据。
