### Average profiles, from tries to suffix-trees

*Pierre Nicodème*

#### Abstract

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 2*log*(ν)/(*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