Skip to Main content Skip to Navigation
Conference papers

Analysis of the average depth in a suffix tree under a Markov model

Abstract : In this report, we prove that under a Markovian model of order one, the average depth of suffix trees of index n is asymptotically similar to the average depth of tries (a.k.a. digital trees) built on n independent strings. This leads to an asymptotic behavior of $(\log{n})/h + C$ for the average of the depth of the suffix tree, where $h$ is the entropy of the Markov model and $C$ is constant. Our proof compares the generating functions for the average depth in tries and in suffix trees; the difference between these generating functions is shown to be asymptotically small. We conclude by using the asymptotic behavior of the average depth in a trie under the Markov model found by Jacquet and Szpankowski ([JaSz91]).
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 3:52:43 PM
Last modification on : Thursday, February 3, 2022 - 11:17:11 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:53 AM


Publisher files allowed on an open archive




Julien Fayolle, Mark Daniel Ward. Analysis of the average depth in a suffix tree under a Markov model. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.95-104, ⟨10.46298/dmtcs.3371⟩. ⟨hal-01184043⟩



Record views


Files downloads