Skip to Main content Skip to Navigation
Journal articles

Dynamical sources in information theory: a general analysis of trie structures

Julien Clément 1 Philippe Flajolet 2 Brigitte Vallée 1
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
2 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : Digital trees, also known as tries, are a general purpose flexible data structure that implements dictionaries built on sets of words. An analysis is given of three major representations of tries in the form of array-tries, list tries, and bst-tries (“ternary search tries”). The size and the search costs of the corresponding representations are analysed precisely in the average case, while a complete distributional analysis of the height of tries is given. The unifying data model used is that of dynamical sources and it encompasses classical models like those of memoryless sources with independent symbols, of finite Markov chains, and of nonuniform densities. The probabilistic behaviour of the main parameters, namely, size, path length, or height, appears to be determined by two intrinsic characteristics of the source: the entropy and the probability of letter coincidence. These characteristics are themselves related in a natural way to spectral properties of specific transfer operators of the Ruelle type.
Document type :
Journal articles
Complete list of metadata
Contributor : Julien Clément <>
Submitted on : Tuesday, September 6, 2011 - 3:48:32 PM
Last modification on : Friday, June 4, 2021 - 10:44:55 AM

Links full text



Julien Clément, Philippe Flajolet, Brigitte Vallée. Dynamical sources in information theory: a general analysis of trie structures. Algorithmica, Springer Verlag, 2001, 29 (1-2), pp.307-369. ⟨10.1007/BF02679623⟩. ⟨hal-00619544⟩



Record views