m-Bonsai: a Practical Compact Dynamic Trie

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 $σ$, the information-theoretic lower bound is $n \log σ+ O(n)$ bits. The Bonsai data structure is a compact trie proposed by Darragh et al. (Softw., Pract. Exper. 23(3), 1993, p. 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 σ+ O(M \log \log M)$ (which is asymptotically non-optimal for smaller $σ$ or if $n \ll M$) and a lack of support for deletions. It supports traversal and update operations in $O(1/ε)$ expected time (based on assumptions about the behaviour of hash functions), where $ε= (M-n)/M$ and has excellent speed performance in practice. We propose an alternative, m-Bonsai, that addresses the above problems, obtaining a trie that uses $(1+β) n (\log σ+ O(1))$ bits in expectation, and supports traversal and update operations in $O(1/β)$ expected time and $O(1/β^2)$ amortized expected time, for any user-specified parameter $β> 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.