什么是最好的自动完成/建议算法，数据结构 [C++/C] [英] What is the best autocomplete/suggest algorithm,datastructure [C++/C]

问题描述

我们看到 Google、Firefox 的一些 AJAX 页面会在用户键入字符时显示可能的项目列表.

We see Google, Firefox some AJAX pages show up a list of probable items while user types characters.

谁能给出一个好的算法，实现自动完成的数据结构?

Can someone give a good algorithm, data structure for implementing autocomplete?

推荐答案

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

A trie is a data structure that can be used to quickly find words that match a prefix.

这是一个示例，展示了如何使用一个来实现自动完成http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Here's an example showing how to use one to implement autocomplete http://rmandvikar.blogspot.com/2008/10/trie-examples.html

这是 3 种不同自动完成实现的比较(尽管它是在 Java 中而不是在 C++ 中).

Here's a comparison of 3 different auto-complete implementations (though it's in Java not C++).

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

查找键时，trie 比 Set 实现略快.trie 和 set 都比关系数据库解决方案快很多.

When looking up keys, the trie is marginally faster than the Set implementation. Both the trie and the set are a good bit faster than the relational database solution.

Set 的设置成本低于 Trie 或 DB 解决方案.您必须决定是频繁地构建新的词集"，还是优先考虑查找速度.

The setup cost of the Set is lower than the Trie or DB solution. You'd have to decide whether you'd be constructing new "wordsets" frequently or whether lookup speed is the higher priority.

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

These results are in Java, your mileage may vary with a C++ solution.

这篇关于什么是最好的自动完成/建议算法，数据结构 [C++/C]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！