Skip to Main content Skip to Navigation
New interface
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 metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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


Publisher files allowed on an open archive




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



Record views


Files downloads