# 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.
Keywords :
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
Domaine :

Littérature citée [11 références]

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 7 février 2019 - 16:57:26
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:25:10

### Fichier

Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184225, version 1

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

### Métriques

Consultations de la notice

## 292

Téléchargements de fichiers