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 → ∞): r_n → (log n)/η (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 → ∞): D_n = (log log n) /(-log (1-h/η)) (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.