Tight Additive Sensitivity on LZ-style Compressors and String Attractors

Abstract

The worst-case additive sensitivity of a string repetitiveness measure $c$ is defined to be the largest difference between $c(w)$ and $c(w^{\prime })$, where $w$ is a string of length $n$ and $w^{\prime }$ is a string that can be obtained by performing a single-character edit operation on $w$. We present $O(\sqrt{n})$ upper bounds for the worst-case additive sensitivity of the smallest string attractor size ${\hat{I}}^3$ and the smallest bidirectional scheme size $b$, which match the known lower bounds $\hat{I}\text{c◯}(\sqrt{n})$ for ${\hat{I}}^3$ and $b$ [Akagi et al. 2023]. Further, we present matching upper and lower bounds for the worst-case additive sensitivity of the Lempel-Ziv family - $\hat{I}˜(n^{\frac{2}{3}})$ for LZSS and LZ-End, and $\hat{I}˜(n)$ for LZ78.