Profile of Tries

Gayun Park Hsien-Kuei Hwang Pierre Nicodème 1, 2, * Wojciech Szpankowski
* Auteur correspondant
1 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8623
Résumé : Les tries sont une des strucutres de données les plus utilisées pour les mots. Ce papier preesente une étude détaillée de la distribution des profils des tries générés par des sources sans mémoire. La croissance des profils attendus dépend de la distance à la racine. Les résultats sont obtenus en utilisant les outils de l'algorithmique analytique, notamment les fonctions génératrices, la transformation de Mellin, la Poissonisation et la dé-Poissonisation, la méthode du col, l'analyse de singularités, l'analyse asymptotique.
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2009, 38 (5), pp.1821-1880. 〈10.1137/070685531〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00781400
Contributeur : Mireille Regnier <>
Soumis le : samedi 26 janvier 2013 - 13:00:50
Dernière modification le : jeudi 10 mai 2018 - 02:06:16

Identifiants

Collections

Citation

Gayun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski. Profile of Tries. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2009, 38 (5), pp.1821-1880. 〈10.1137/070685531〉. 〈hal-00781400〉

Partager

Métriques

Consultations de la notice

252