爆炸式字典树

上一篇文章《

字典树

》,介绍了字典树的四种实现形式。本文讨论两种改进的字典树。

补充上篇文章中提到的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代码

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190104G07KRX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券