什么是最好的自动完成/建议算法，数据结构[C++/C]

我们看到Google，Firefox的一些AJAX页面显示可能项目列表，而用户输入字符。什么是最好的自动完成/建议算法，数据结构[C++/C]

有人可以给一个很好的算法，实现自动完成的数据结构？

2009-11-23 subbul

A trie是一种数据结构，可用于快速查找与前缀匹配的单词。

编辑：下面是示出了如何使用一个实现自动填充http://rmandvikar.blogspot.com/2008/10/trie-examples.html

这里是3个不同的auto-complete implementations的比较（虽然它是一个Java不C++）的例子。

* In-Memory Trie 
* In-Memory Relational Database 
* Java Set

查找键时，trie比Set实现稍快。 trie和set都比关系型数据库解决方案好一点。

Set的设置成本低于Trie或DB解决方案。您必须决定是否要频繁构建新的“词汇集”，或者查询速度是否优先。

这些结果是用Java编写的，你的里程可能会因C++解决方案而异。

来源

2009-11-23 15:03:59 Glen

有点关系是谷歌的彼得·诺维格的描述如何进行拼写校正：http://norvig.com/spell-correct.html – 2009-11-23 15:23:03

标准Trie的内存密集程度很高，对于较大的套件，您希望使用压缩Trie，这样可以大大减少内存占用量。其他优化包括节点值的延迟初始化和子/值集合的正确数据结构。前一段时间，我创建了一个[自动完成库]（https://github.com/fmmfonseca/completely），能够处理超大型数据集（10,000,000+），并有效地回答精确和近似的搜索。 – 2015-06-23 14:47:44

对于一个简单的解决方案：你产生一个“候选”以最小的编辑（Levenshtein）距离（1或2），然后在测试用散列容器候选的存在（设置就足够了一个简单的soltion ，然后从tr1或boost使用unordered_set）。

例如：你写了carr，你想要汽车。 arr是由1个删除产生的。你的unordered_set是否是arr？号码crr是由1次删除产生的。在你的unordered_set中是crr吗？号车是由1删除产生的。你的车是在无序的？是的，你赢了。

当然还有插入，删除，换位等等

您将看到，产生候选人的算法是真的，你是在浪费时间，特别是如果你有一个非常小unordered_set。

来源

2009-11-23 16:49:08 anno

对于大型数据集，后端的一个很好的候选者是三元搜索树。它们结合了两个最好的世界：二叉搜索树的低空间开销和数字搜索尝试的基于字符的时间效率。

见Dr. Dobbs Journal的：http://www.ddj.com/windows/184410528

的目标是有限的结果集，作为在用户类型的快速检索让我们首先考虑的是要搜索“计算机科学”就可以启动从“计算机”打字。或“科学”而不是“计算机”。因此，给定一个短语，生成以单词开始的子短语。现在对于每个短语，将它们送入TST（三元搜索树）。 TST中的每个节点将代表到目前为止输入的短语的前缀。我们将在该节点中存储该前缀的最佳10个（说）结果。如果对于一个节点，有更多的候选人比有限的结果数量（10个），应该有一个排名函数来解决两个结果之间的竞争。

根据数据的动态性，树可以每隔几个小时建立一次。如果数据是实时的，那么我想其他一些算法会给出更好的平衡。在这种情况下，绝对要求是快速检索键入的每个击键的结果，它的表现非常好。

如果涉及到拼写纠正的建议，会出现更多复杂问题。在这种情况下，编辑距离算法也必须考虑。

对于像国家列表这样的小数据集，Trie的一个简单实现就可以做到。如果您要在Web应用程序中实现此类自动完成下拉列表，则在您提供列表中的数据后，YUI3的自动完成小部件将为您执行所有操作。如果您使用YUI3作为大数据支持的自动填充的前端，请使用C++制作基于TST的Web服务，然后使用自动填充小部件的脚本节点数据源从Web服务获取数据，而不是使用简单列表。

来源

2009-11-23 19:17:01

如果你想建议最流行的完成，一个“推荐树”可能是一个不错的选择： Suggest Tree

来源

2010-10-28 09:25:26 Nicolai