  Tries are among the most versatile and widely used data structures on words.
They are pertinent to the (internal) structure of (stored) words and several
splitting procedures used in diverse contexts ranging from document taxonomy to
IP addresses lookup, from data compression (i.e., Lempel-Ziv'77 scheme) to
dynamic hashing, from partial-match queries to speech recognition, from leader
election algorithms to distributed hashing tables and graph compression. While
the performance of tries under a realistic probabilistic model is of
significant importance, its analysis, even for simplest memoryless sources, has
proved difficult. Rigorous findings about inherently complex parameters were
rarely analyzed (with a few notable exceptions) under more realistic models of
string generations. In this paper we meet these challenges: By a novel use of
the contraction method combined with analytic techniques we prove a central
limit theorem for the external path length of a trie under a general Markov
source. In particular, our results apply to the Lempel-Ziv'77 code. We envision
that the methods described here will have further applications to other trie
parameters and data structures.
