Sensitivity and Size Relationships of the Lempel-Ziv Factorization

Abstract

The Lempel-Ziv (LZ) factorization is a fundamental method for compressing repetitive strings. Its multiplicative sensitivity to an operation measures how much that operation can increase the number of phrases, as the maximum ratio of the phrase counts after and before the operation. While its sensitivity to single-character edits is known, its sensitivity to more global operations such as prefix deletion and string reversal remains unknown. Further open questions concern its size relationships with other compressed representations and whether it can be converted into an LZ-like encoding of polylogarithmic height without asymptotically increasing its size. In this paper, We determine the multiplicative sensitivity of the LZ factorization to prefix deletion, cyclic rotation, and string reversal by establishing an $\Omega (\log n)$ lower bound for each operation that matches the known upper bound, where $n$ is the input length. Using the result for prefix deletion, we show that the combined size of the relative LZ factorization and the LZ encoding of its reference string can be asymptotically smaller than that of the LZ factorization. We also obtain asymptotically tight worst-case ratios of $\Theta (\log n)$ for the size of the LZ factorization divided by the minimum size of a collage system and for the size of the lex-parse divided by that of the LZ factorization. We give lower and upper bounds on the worst-case ratio of the minimum size of an LZ-like encoding of height at most $h$ to the size of the LZ factorization, with matching bounds for $h\ge \lg n$. In particular, we show that the minimum size of an LZ-like encoding with height at most $h\in O(\mathrm{poly}\log n)$ can be larger than the size of the LZ factorization by a factor of $\Omega (\log n/\log \log n)$. All our lower bounds follow from a common string construction based on the bit-reversal permutation.