上一篇文章《
字典树
》,介绍了字典树的四种实现形式。本文讨论两种改进的字典树。
补充上篇文章中提到的array trie,hash trie 以及 list trie的node结构如下:
Burst Tries
爆炸式字典树,开始的时候采用一个容器存储key。一旦容器full之后,“爆炸”产生多个分支,指向各个子容器,每一次爆炸,子树的高度加1.
一颗爆炸树结构,大致如下图所示,图中采用的是BST树作为容器结构。
具体开源代码,可以参考:https://github.com/gabrieldumitrescu/BurstTrie
参考论文:Heinz S, Zobel J, Williams H E. Burst tries: a fast, efficient data structure for string keys[J]. ACM Transactions on Information Systems (TOIS), 2002, 20(2): 192-223.
论文ppt:http://www.cs.uvm.edu/~xwu/wie/CourseSlides/Schips-BurstTries.pdf
HAT-trie
爆炸式字典树,一句话总结就是,用容器替代叶子节点的字典树。HAT-trie的原理相对简单,采用了一个cache优化的hash容器实现的爆炸式字典树而已。链式hash由于指针过多,性能不好。下面三张图一看就懂了。
参考资料:
https://en.wikipedia.org/wiki/HAT-trie
https://tessil.github.io/2017/06/22/hat-trie.html
https://github.com/Tessil/hat-trie
https://github.com/dcjones/hat-trie
Askitis N, Sinha R. HAT-trie: a cache-conscious trie-based data structure for strings[C]//Proceedings of the thirtieth Australasian conference on Computer science-Volume 62. Australian Computer Society, Inc., 2007: 97-105.
文章中,屏蔽了很多,插入,删除,爆炸操作等一系列细节,感兴趣的可以去review代码
领取专属 10元无门槛券
私享最新 技术干货