文章基本信息

标题：On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations
本地全文：下载
作者：Yuki Urabe ; Yuto Nakashima ; Shunsuke Inenaga 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：128
页码：1-11
DOI：10.4230/LIPIcs.CPM.2019.29
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Lempel-Ziv (LZ) factorization and Lyndon factorization are well-known factorizations of strings. Recently, Kärkkäinen et al. studied the relation between the sizes of the two factorizations, and showed that the size of the Lyndon factorization is always smaller than twice the size of the non-overlapping LZ factorization [STACS 2017]. In this paper, we consider a similar problem for the overlapping version of the LZ factorization. Since the size of the overlapping LZ factorization is always smaller than the size of the non-overlapping LZ factorization and, in fact, can even be an O(log n) factor smaller, it is not immediately clear whether a similar bound as in previous work would hold. Nevertheless, in this paper, we prove that the size of the Lyndon factorization is always smaller than four times the size of the overlapping LZ factorization.
关键词：Lyndon factorization; Lyndon words; Lempel-Ziv factorization