Julien Fayolle ; Mark Daniel Ward
-
Analysis of the average depth in a suffix tree under a Markov model
dmtcs:3371 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
-
https://doi.org/10.46298/dmtcs.3371
Analysis of the average depth in a suffix tree under a Markov model
Authors: Julien Fayolle 1; Mark Daniel Ward 2
NULL##NULL
Julien Fayolle;Mark Daniel Ward
1 Algorithms
2 Department of mathematics Purdue University
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]).
Ann, Hsing-Yen; Yang, Chang-Biau; Peng, Yung-Hsing; Liaw, Bern-Cherng, 2010, Efficient Algorithms For The Block Edit Problems, Information And Computation, 208, 3, pp. 221-229, 10.1016/j.ic.2009.12.001.
LĂŠonard, M.; Mouchard, L.; Salson, M., 2012, On The Number Of Elements To Reorder When Updating A Suffix Array, Journal Of Discrete Algorithms, 11, pp. 87-99, 10.1016/j.jda.2011.01.002.
Milioris, Dimitrios, 2017, Joint Sequence Complexity: Introduction And Theory, Topic Detection And Classification In Social Networks, pp. 21-56, 10.1007/978-3-319-66414-9_3.
Milioris, Dimitrios; Jacquet, Philippe, 2014, Joint Sequence Complexity Analysis: Application To Social Networks Information Flow, Bell Labs Technical Journal, 18, 4, pp. 75-88, 10.1002/bltj.21647.
Rasheed, Faraz; Adnan, Muhaimenul; Alhajj, Reda, 2012, Out-of-core Detection Of Periodicity From Sequence Databases, Knowledge And Information Systems, 36, 1, pp. 277-301, 10.1007/s10115-012-0546-1.