Size and path length of Patricia tries: Dynamical sources context

Digital trees, such as tries, and Patricia tries are data structures routinely used in a variety of computer and communication applications including dynamic hashing, partial match retrieval, searching and sorting, conflict resolution algorithms for communication broadcast, data compression, and so forth. Here, we consider tries and Patricia tries built from n words emitted by a probabilistic dynamical source. Such sources encompass classical and many models such as memoryless sources and finite Markov chains. The probabilistic behavior of its main parameters, namely, the size and the path length, appears to be determined by some intrinsic characteristics of the source, such as Shannon entropy and entropy‐like constants, that depend on the spectral properties of specific transfer operators of Ruelle type.