HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal.inria.fr/inria-00073393
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:41:28 PM
Last modification on : Friday, February 4, 2022 - 3:07:51 AM
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

98

Files downloads

204