Sensitivity of string compressors and repetitiveness measures

The sensitivity of a string compression algorithm $C$ asks how much the output size $C(T)$ for an input string $T$ can increase when a single character edit operation is performed on $T$. We analyze the worst-case multiplicative sensitivity of string compression algorithms, which is defined by $\max_{T \in \Sigma^n}\{C(T')/C(T) : ed(T, T') = 1\}$, where $ed(T, T')$ denotes the edit distance between $T$ and $T'$. In particular, for the most common versions of the Lempel-Ziv 77 compressors, we prove that the worst-case multiplicative sensitivity is only a small constant. We strengthen our upper bound results by presenting matching lower bounds. We also generalize these results to the smallest bidirectional scheme $b$. These results contrast with the previously known related results such that the size $z_{\rm 78}$ of the Lempel-Ziv 78 factorization can increase by a factor of $\Omega(n^{1/4})$ [Lagarde and Perifel, 2018], and the number $r$ of runs in the Burrows-Wheeler transform can increase by a factor of $\Omega(\log n)$ [Giuliani et al., 2021] when a character is prepended to an input string of length $n$. In addition, we show that the worst-case multiplicative sensitivity of $r$ is upper bounded by $O(\log r \log n)$. We also study the worst-case sensitivity of several grammar-based compressors including RePair, LongestMatch, Bisection, AVL-grammar, GCIS, and CDAWG. Further, we extend the notion of the worst-case sensitivity to string repetitiveness measures such as the smallest string attractor size $\gamma$ and the substring complexity $\delta$. We present some non-trivial upper and lower bounds of the worst-case multiplicative sensitivity for $\gamma$ and matching upper and lower bounds of the worst-case multiplicative sensitivity for $\delta$. We also exhibit the worst-case additive sensitivity $\max_{T \in \Sigma^n}\{C(T') - C(T) : ed(T, T') = 1\}$.