EUVIMEDEUVIMED entdecken
Crossref

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

Julien Fayolle, Mark Daniel Ward

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →