m-Bonsai: A Practical Compact Dynamic Trie

作     者：Poyias, Andreas Puglisi, Simon J. Raman, Rajeev 

作者机构：Univ Leicester Dept Informat Univ Rd Leicester LE1 7RH Leics England Univ Helsinki Dept Comp Sci Helsinki Inst Informat Technol POB 68 FI-00014 Helsinki Finland 

出 版 物：《INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE》 (国际计算机科学基础杂志)

年 卷 期：2018年第29卷第8期

页      面：1257-1278页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Academy of Finland Academy of Finland (AKA) Funding Source: Academy of Finland (AKA) 

主　　题：Trie succinct data structures dynamic trie cardinal tree digital search tree compact hashing 

摘      要：We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with n nodes with an alphabet of size sigma, the information-theoretic space lower bound is n log sigma + O(n) bits. The Bonsai data structure is a compact trie proposed by Darragh et al. (Softw. Pract. Exper. 23(3) (1993) 277-291). Its disadvantages include the user having to specify an upper bound M on the trie size in advance (which cannot be changed easily after initalization), a space usage of M log sigma + O(M log log M) (which is asymptotically non-optimal for smaller sigma or if n 0 (again based on assumptions about the behaviour of hash functions). We give an implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.