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.
Type de document :
Rapport
[Research Report] RR-3295, INRIA. 1997
Liste complète des métadonnées

https://hal.inria.fr/inria-00073393
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:41:28
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : jeudi 24 mars 2011 - 12:43:04

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

284