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
CNRS - Centre National de la Recherche Scientifique : UMR8623, X - École polytechnique, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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 12 avril 2018 - 01:48:42

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

222