Analysis of the multiplicity matching parameter in suffix trees

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...

وصف كامل

التفاصيل البيبلوغرافية

المؤلفون الرئيسيون:	Mark Daniel Ward, Wojciech Szpankowski
التنسيق:	Artigo
اللغة:	Inglês
منشور في:	Discrete Mathematics & Theoretical Computer Science 2005-01-01
سلاسل:	Discrete Mathematics & Theoretical Computer Science
الموضوعات:	data compression complex asymptotics suffix trees combinatorics on words pattern matching autocorrelation polynomial [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg]
الوصول للمادة أونلاين:	https://dmtcs.episciences.org/3387/pdf
الوسوم:	إضافة وسم لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!