Trie实施

Question

在C/C++中是否有任何速度和缓存效率的trie实现？我知道什么是特里,但我不想重新发明轮子,自己实施.

Answer 1

如果您正在寻找ANSI C实现,您可以从FreeBSD"窃取"它.您要查找的文件名为radix.c.它用于管理内核中的路由数据.

Answer 2

我意识到问题是关于准备好的实现,但供参考......

在你跳到Judy之前,你应该阅读" Judy与哈希表的性能比较 ".然后谷歌搜索标题可能会给你一生的讨论和反驳阅读.

我所知道的一个明确缓存意识的是HAT-trie.

正确实施HAT-trie非常酷.但是,对于前缀搜索,您需要对散列桶进行排序步骤,这与前缀结构的想法有些冲突.

一个稍微简单的trie是burst-trie,它基本上为你提供了某种标准树(如BST)和trie之间的插值.我从概念上喜欢它,它实现起来要容易得多.

Answer 3

我和libTrie好运.它可能没有专门的缓存优化,但性能一直适合我的应用程序.

Answer 4

GCC附带了一些数据结构,作为其"基于策略的数据结构"的一部分.这包括一些trie实现.

http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html