Geodesic
Analysis of the average depth in a suffix tree under a Markov model
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

Voir la notice de l'article provenant de la source Episciences

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]). 
@article{DMTCS_2005_special_249_a19,
     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},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3371},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3371/}
}
TY  - JOUR
AU  - Fayolle, Julien
AU  - Ward, Mark Daniel
TI  - Analysis of the average depth in a suffix tree under a Markov model
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3371/
DO  - 10.46298/dmtcs.3371
LA  - en
ID  - DMTCS_2005_special_249_a19
ER  - 
%0 Journal Article
%A Fayolle, Julien
%A Ward, Mark Daniel
%T Analysis of the average depth in a suffix tree under a Markov model
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3371/
%R 10.46298/dmtcs.3371
%G en
%F DMTCS_2005_special_249_a19
Fayolle, Julien; Ward, Mark Daniel. Analysis of the average depth in a suffix tree under a Markov model. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3371. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3371/

Cité par Sources :