Sensitivity and Size Relationships of the Lempel-Ziv Factorization

Abstract

The Lempel-Ziv (LZ) factorization is one of the most fundamental methods for compressing highly repetitive strings, and the number of phrases in its factorization is considered a repetitiveness measure. Sensitivity to an edit operation measures the maximum increase in a repetitiveness measure when the operation is applied to a string. While asymptotically tight bounds are known for the sensitivity of the LZ factorization to single-character edits, whether its multiplicative sensitivity is bounded by a constant has remained open for operations that change a large part of the structure of a string, such as prefix deletion, substring deletion, cyclic rotation, and string reversal. We resolve this question. For each of these four operations, we construct a family of strings in which a string of length $n$ has sensitivity $\Omega(\log n)$ to that operation. We also determine the size relationships among the LZ factorization, collage systems and the lex-parse. We construct a family of strings whose LZ factorizations are $\Omega(\log n)$ times larger than their minimum collage systems, and a family of strings whose lex-parses are $\Omega(\log n)$ times larger than their LZ factorizations. All of these lower bounds are asymptotically tight, matching $O(\log n)$ upper bounds.