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]).
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.95-104, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184043
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:52:43
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:53

Fichier

dmAD0109.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184043, version 1

Collections

Citation

Julien Fayolle, Mark Daniel Ward. Analysis of the average depth in a suffix tree under a Markov model. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.95-104, 2005, DMTCS Proceedings. 〈hal-01184043〉

Partager

Métriques

Consultations de la notice

347

Téléchargements de fichiers

214