The analysis of hybrid trie structures
Julien Clément, Philippe Flajolet, Brigitte Vallée · 1998
: This paper provides a detailed analysis of various implementations of digital tries, including the "ternary search tries" of Bentley and Sedgewick. The methods employed combine symbolic uses of generating functions, Poisson models, and Mellin transforms. Theoretical results are matched against real-life data and justify the claim that ternary search tries are a highly efficient dynamic dictionary structure for strings and textual data. (Paper to appear in the Proceedings of the Ninth ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, January 1998, SIAM Press.) Unit'e de recherche INRIA Rocquencourt Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France) T'el'ephone : (33) 01 39 63 55 11 -- T'el'ecopie : (33) 01 39 63 53 Analyse des arbres digitaux hybrides R'esum'e : Cet article fournit une analyse d'etaill'ee de diverses implantations des arbres digitaux ou "tries", incluant notamment les "arbres ternaires de recherche" de Bentley et Sedgewick. Les...