Geodesic
Analysis of the multiplicity matching parameter in suffix trees
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 a suffix tree, the multiplicity matching parameter (MMP) $M_n$ is the number of leaves in the subtree rooted at the branching point of the $(n+1)$st insertion. Equivalently, the MMP is the number of pointers into the database in the Lempel-Ziv '77 data compression algorithm. We prove that the MMP asymptotically follows the logarithmic series distribution plus some fluctuations. In the proof we compare the distribution of the MMP in suffix trees to its distribution in tries built over independent strings. Our results are derived by both probabilistic and analytic techniques of the analysis of algorithms. In particular, we utilize combinatorics on words, bivariate generating functions, pattern matching, recurrence relations, analytical poissonization and depoissonization, the Mellin transform, and complex analysis. 
@article{DMTCS_2005_special_249_a35,
     author = {Ward, Mark Daniel and Szpankowski, Wojciech},
     title = {Analysis of the multiplicity matching parameter in suffix trees},
     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.3387},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3387/}
}
TY  - JOUR
AU  - Ward, Mark Daniel
AU  - Szpankowski, Wojciech
TI  - Analysis of the multiplicity matching parameter in suffix trees
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.3387/
DO  - 10.46298/dmtcs.3387
LA  - en
ID  - DMTCS_2005_special_249_a35
ER  - 
%0 Journal Article
%A Ward, Mark Daniel
%A Szpankowski, Wojciech
%T Analysis of the multiplicity matching parameter in suffix trees
%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.3387/
%R 10.46298/dmtcs.3387
%G en
%F DMTCS_2005_special_249_a35
Ward, Mark Daniel; Szpankowski, Wojciech. Analysis of the multiplicity matching parameter in suffix trees. 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.3387. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3387/

Cité par Sources :