Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

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

dmAD0123.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184225, version 1

Collections

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⟩

Share

Metrics

Record views

307

Files downloads

420