文章基本信息

标题：On the Size of Lempel-Ziv and Lyndon Factorizations
本地全文：下载
作者：Juha K{\"a}rkk{\"a}inen ; Dominik Kempa ; Yuto Nakashima 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：45:1-45:13
DOI：10.4230/LIPIcs.STACS.2017.45
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Lyndon factorization and Lempel-Ziv (LZ) factorization are both important tools for analysing the structure and complexity of strings, but their combinatorial structure is very different. In this paper, we establish the first direct connection between the two by showing that while the Lyndon factorization can be bigger than the non-overlapping LZ factorization (which we demonstrate by describing a new, non-trivial family of strings) it is always less than twice the size.
关键词：Lempel-Ziv factorization; Lempel-Ziv parsing; LZ; Lyndon word; Lyndon factorization; Standard factorization