autocomplete - 自动完成算法、论文、策略等

Question

我想知道是否有人有很好的资源来阅读或编写代码来试验“自动完成”

我想知道自动完成背后的理论是什么，从哪里开始常见的错误是什么等。

我发现 Enso、Launchy、Google chrome 甚至 tcsh 等产品执行自动补全的方式令人着迷，我只是出于好奇而开始了自己的一些示例代码，我得出的结论是，这一定是一个之前被广泛探索的领域。

如果有人分享任何关于如何实现这一点的良好技术资源，我将不胜感激。

提前致谢。

score 12 · Accepted Answer

http://humanized.com/weblog/2007/03/30/what_makes_a_good_autocomplete/ --
http://social.msdn.microsoft.com/Forums/en-US/vblanguage/thread/2ccb37b9-c7e1-4113-86ac-ad3d33b4b4b1/——在.Net世界
关于自动完成方法的令人讨厌的专利（理论仍然值得一读）http://www.patentstorm.us/patents/5845300/description.html
http://ask.metafilter.com/91068/Fuzzy-text-completion-algorithm对要采取的策略进行高级讨论。

score 2 · Accepted Answer

查看这篇关于使用 GWT 实现自动完成的博客：

http://jroller.com/glongman/entry/gwt_autocompleter

但我建议你先从一些非常简单的东西开始，自己掌握实现是如何完成的。我会从 Trie 开始，甚至可能完全存储在客户端上，然后如果您认为有必要，可以使用服务器查询进行优化。

score 0 · Accepted Answer

自动完成通常使用以下方法之一实现：

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

关于这个主题的几篇论文：

博日沃伊·梅利查尔。有限自动机的近似字符串匹配；
贡萨洛·纳瓦罗。近似字符串匹配的导览；
列昂尼德·博伊佐夫。近似字典搜索的索引方法：比较分析；
Marios Hadjieleftheriou 和 Divesh Srivastava。近似字符串处理；
Surajit Chaudhuri 和 Raghav Kaushik。扩展自动完成以容忍错误；

完全看一下，一个 Java 自动完成库。

score 0 · Accepted Answer

这是一个开放的问题，根据情况有十几种策略。根据我的知识，我列出了一些著名的自动完成策略及其相应的数据结构的简短亮点。我还试图总结他们与自动完成问题相关的主要优点和缺点。

蛮力：

优点：可以通过检查所有宇宙（输入）作为下一步来实现
优点：超级简单
优点：它适用于状态有限的小型数据集
缺点：没有存储连接，因此每次您必须执行搜索时
缺点：具有最差的时间复杂度。

前缀树（ Trie ）：

优点：它是为这类问题设计的最简单的数据结构。
优点：所有可用下一个状态的列表存储在每个状态中。
缺点：数据大小应该很小（最多应该是 RAM 大小的一小部分）。

有向无环图（DAG）：

Trie 存在空间问题，因此其他数据结构的主要目标是降低空间复杂度。有向无环图（DAG）是其中一种选择。通过使用 DAG，您可以将所有相似的子路径合并为一个。因此将保留大量空间。

快速自动完成存储库位于此区域，它使用有向词图 (DWG) 和 Levenshtein 编辑距离。

其他一些树选项：

在每个状态（或节点）上都有一个搜索问题。线性搜索是最坏的情况选择，因此大多数策略通过使用排序（O(nlog(n)）然后使用二进制搜索（O(log(n) ) ）或使用哈希表（O(1) ）来改进搜索时间，速度快，但空间复杂度更高）。遇到如此多的权衡困境，其他树数据结构变体，如Radix Tree、Suffix Tree、Suggest Tree和Merkle Tree可能会派上用场。

Prioritizig Offers：马尔可夫链可用于优先考虑下一个状态。它存储连接概率，从而产生更准确的结果。