Analysis of the average depth in a suffix tree under a Markov model
Discrete Mathematics & Theoretical Computer Science · 01.01.2005 · DMTCS Proceedings vol. AD,... (Proceedings)
DOI: 10.46298/dmtcs.3371 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 01.01.2005. Verfasst von Julien Fayolle und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref).
Abstract (Originalsprache)
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]).
Zitieren
APA
Fayolle, J., & Ward, M. D. (2005). Analysis of the average depth in a suffix tree under a Markov model. Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AD,...(Proceedings). https://doi.org/10.46298/dmtcs.3371
Vancouver
Fayolle J, Ward MD. Analysis of the average depth in a suffix tree under a Markov model. Discrete Mathematics & Theoretical Computer Science. 2005;DMTCS Proceedings vol. AD,...(Proceedings). doi:10.46298/dmtcs.3371
BibTeX
@article{Fayolle2005,
author = {Fayolle, Julien and Ward, Mark Daniel},
title = {Analysis of the average depth in a suffix tree under a Markov model},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2005},
volume = {DMTCS Proceedings vol. AD,...},
number = {Proceedings},
doi = {10.46298/dmtcs.3371}
}
EUVIMED