sub*_*bul 48 c c++ algorithm search autocomplete
我们看到谷歌,Firefox,一些AJAX页面显示可能的项目列表,而用户键入字符.
有人能给出一个好的算法,数据结构来实现自动完成吗？
Gle*_*len 58
一个线索是可以用来快速找到匹配前缀词的数据结构.
编辑:这是一个示例,显示如何使用一个实现自动完成http://rmandvikar.blogspot.com/2008/10/trie-examples.html
这里是3种不同的自动完成实现的比较(尽管它是用Java而不是C++).
* In-Memory Trie
* In-Memory Relational Database
* Java Set
查找键时,trie比Set实现略快.trie和set都比关系数据库解决方案快得多.
Set的设置成本低于Trie或DB解决方案.您必须决定是否经常构建新的"字集",或者查找速度是否更高.
这些结果是用Java编写的,您的里程可能因C++解决方案而异.
Joy*_*tta 19
对于大型数据集,后端的一个很好的候选者将是三元搜索树.它们结合了两个世界中最好的:二进制搜索树的低空间开销和数字搜索尝试的基于字符的时间效率.
参见Dr. Dobbs Journal:http://www.ddj.com/windows/184410528
目标是在用户输入时快速检索有限结果集.让我们首先考虑搜索"计算机科学",你可以从"计算机"或"科学"而不是"计算机"开始输入.因此,给定一个短语,生成以单词开头的子短语.现在,对于每个短语,将它们输入TST(三元搜索树).TST中的每个节点将表示到目前为止已键入的短语的前缀.我们将在该节点中存储该前缀的最佳10(说)结果.如果节点的候选者数量多于有限数量(此处为10),则应该有一个排序函数来解决两个结果之间的竞争.
树可以每隔几个小时构建一次,具体取决于数据的动态.如果数据是实时的,那么我猜其他一些算法会给出更好的平衡.在这种情况下,绝对要求是每次击键键入的结果的闪电般快速检索,它做得非常好.
如果涉及拼写更正的建议,将会出现更多复杂情况.在这种情况下,还必须考虑编辑距离算法.
对于像国家列表这样的小型数据集,Trie的一个简单实现就可以了.如果要在Web应用程序中实现此类自动完成下拉列表,则在列表中提供数据后,YUI3的自动完成小组件将为您完成所有操作.如果您使用YUI3作为大数据支持的自动完成的前端,请在C++中创建基于TST的Web服务,然后使用自动完成小部件的脚本节点数据源从Web服务而不是简单列表中获取数据.