Analysis of the multiplicity matching parameter in suffix trees

Abstract : 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.
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.307-322, 2005, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01184222
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 13 août 2015 - 13:35:05
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:24:31

Fichier

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

Identifiants

  • HAL Id : hal-01184222, version 1

Collections

Citation

Mark Daniel Ward, Wojciech Szpankowski. Analysis of the multiplicity matching parameter in suffix trees. 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.307-322, 2005, DMTCS Proceedings. 〈hal-01184222〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

140