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.
展开▼
