Average profiles, from tries to suffix-trees

Abstract : We build upon previous work of Fayolle (2004) and Park and Szpankowski (2005) to study asymptotically the average internal profile of tries and of suffix-trees. The binary keys and the strings are built from a Bernoulli source $(p,q)$. We consider the average number $p_{k,\mathcal{P}}(\nu)$ of internal nodes at depth $k$ of a trie whose number of input keys follows a Poisson law of parameter $\nu$. The Mellin transform of the corresponding bivariate generating function has a major singularity at the origin, which implies a phase reversal for the saturation rate $p_{k,\mathcal{P}}(\nu)/2^k$ as $k$ reaches the value $2\log(\nu)/(\log(1/p)+\log(1/q))$. We prove that the asymptotic average profiles of random tries and suffix-trees are mostly similar, up to second order terms, a fact that has been experimentally observed in Nicodème (2003); the proof follows from comparisons to the profile of tries in the Poisson model.
Type de document :
Communication dans un congrès
Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.257-266, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184225
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 13 août 2015 - 13:35:16
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:25:10

Fichier

dmAD0123.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184225, version 1

Collections

Citation

Pierre Nicodème. Average profiles, from tries to suffix-trees. Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.257-266, 2005, DMTCS Proceedings. 〈hal-01184225〉

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

53