The Analysis of Hybrid Trie Structures

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073393
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:41:28 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Thursday, March 24, 2011 - 12:43:04 PM

Identifiers

  • HAL Id : inria-00073393, version 1

Collections

Citation

Julien Clément, Philippe Flajolet, Brigitte Vallée. The Analysis of Hybrid Trie Structures. [Research Report] RR-3295, INRIA. 1997. ⟨inria-00073393⟩

Share

Metrics

Record views

152

Files downloads

310