Analysis of a Class of Tries with Adaptive Multi-digit Branching

We study a class of adaptive multi-digit tries, in which the numbers of digits r n processed by nodes with n incoming strings are such that, in memoryless model (with n → ∞): rn ® \fraclog nh (pr.)r_n \longrightarrow \frac{log n}{\eta} (pr.)where η is an algorithm-specific constant. Examples of known data structures from this class include LC-tries (Andersson and Nilsson, 1993), “relaxed” LC-tries (Nilsson and Tikkanen, 1998), tries with logarithmic selection of degrees of nodes, etc. We show, that the average depth D n of such tries in asymmetric memoryless model has the following asymptotic behavior (with n → ∞):Dn = \fraclog log n-log(1 - h/h)(1 + o(1))D_n = \frac{log log n}{-log(1 - h/\eta)}(1 + o(1))where n is the number of strings inserted in the trie, and h is the entropy of the source. We use this formula to compare performance of known adaptive trie structures, and to predict properties of other possible implementations of tries in this class.