# 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 :
Document type :
Conference papers
Domain :

Cited literature [11 references]

https://hal.inria.fr/hal-01184225
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 13, 2015 - 1:35:16 PM
Last modification on : Thursday, March 5, 2020 - 6:30:23 PM
Long-term archiving on: : Saturday, November 14, 2015 - 10:25:10 AM

### File

Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01184225, version 1

### Citation

Pierre Nicodème. Average profiles, from tries to suffix-trees. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.257-266. ⟨hal-01184225⟩

Record views