Analysis of the average depth in a suffix tree under a Markov model - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

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

Julien Fayolle
  • Fonction : Auteur
  • PersonId : 866782

Résumé

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]).
Fichier principal
Vignette du fichier
dmAD0109.pdf (140.05 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184043 , version 1 (12-08-2015)

Identifiants

Citer

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⟩
409 Consultations
692 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More