Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184222
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 13, 2015 - 1:35:05 PM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Saturday, November 14, 2015 - 10:24:31 AM

File

dmAD0128.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184222, version 1

Collections

Citation

Mark Daniel Ward, Wojciech Szpankowski. Analysis of the multiplicity matching parameter in suffix trees. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.307-322. ⟨hal-01184222⟩

Share

Metrics

Record views

171

Files downloads

490