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 informationtheoretic 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, pp. 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 ≪ 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.