Analysis of digital tries with Markovian dependency

Abstract

A complete characterization of a digital tree, also called a trie, is presented from the depth viewpoint in a Markovian framework, that is, under the assumption that symbols in a key are Markov-dependent. The main findings show that asymptotically, as the number of keys n tends to infinity, the average depth becomes ED/sub n/ approximately (1/h/sub 1/) log N+c', and the variance is var D/sub n/ approximately alpha log n+c", where h/sub 1/ is the entropy of the (Markovian-dependent) alphabet, alpha is a parameter of the probabilistic model and c' and c" are constants. The symmetric independent model has alpha =0, hence in this case var D/sub n/=O(1). Limiting distribution is also derived for the depth D/sub n/, and in particular, it is shown that D/sub n/ tends to the normal distribution in all cases except the symmetric independent model. These results extend all previous analyses since most of them have been limited to independent models.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>