我们看到Google,Firefox一些AJAX页面在用户输入字符时会显示一个可能的项目列表.
有人能给出一个实现自动完成的好算法和数据 struct 吗?
我们看到Google,Firefox一些AJAX页面在用户输入字符时会显示一个可能的项目列表.
有人能给出一个实现自动完成的好算法和数据 struct 吗?
trie是一种数据 struct ,可用于快速查找与前缀匹配的单词.
编辑:下面是一个示例,说明如何使用其中一个来实现自动完成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都比关系数据库解决方案快得多.
该设备的安装成本低于Trie或DB解决方案.你必须决定是频繁构建新的"词集",还是更优先考虑查找速度.
这些结果是在java中,你的里程可能会随C++的解决方案而变化.