DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

Average profiles, from tries to suffix-trees

Pierre Nicodème


We build upon previous work of [Fayj04] and [ParSzp05] 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,P(ν) of internal nodes at depth k of a trie whose number of input keys follows a Poisson law of parameter ν. 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,P(ν)/2k as k reaches the value 2log(ν)/(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 [Nic03]; the proof follows from comparisons to the profile of tries in the Poisson model.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional