Tight Additive Sensitivity on LZ-style Compressors and String Attractors
Yuto Fujie, Hiroki Shibata, Yuto Nakashima, Shunsuke Inenaga · 2025
Read Tight Additive Sensitivity on LZ-style Compressors and String Attractors by Yuto Fujie, Hiroki Shibata, Yuto Nakashima, Shunsuke Inenaga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-22778.txt.
Introduction
Yuto Fujie, Hiroki Shibata, Yuto Nakashima, and Shunsuke Inenaga pin down how much a single edit can change measures of string repetitiveness, in a 2025 paper. Such measures say how compressible a string is, and they matter for indexing huge texts. The question is sensitivity: if one character is edited, how much can the measure jump in the worst case?
The team prove an upper bound that grows with the square root of string length for two measures, the smallest string attractor and the smallest bidirectional scheme. That matches known lower bounds, so those results are tight. For the Lempel-Ziv family of compressors, they give matching upper and lower bounds that differ by scheme. Two variants grow as the two-thirds power of length, while LZ78 can change by the full length. The work closes open gaps on how stable these measures are under small edits.
Catalog record
| CREATOR | Yuto Fujie, Hiroki Shibata, Yuto Nakashima, Shunsuke Inenaga |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-22778
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tight Additive Sensitivity on LZ-style Compressors and String Attractors Yuto Fujie, Hiroki Shibata, Yuto Nakashima, Shunsuke Inenaga Abstract The worst-case additive sensitivity of a string repetitiveness measure c c is defined to be the largest difference between c ( w ) c(w) and c ( w ′ ) c(w^{\prime}) , where w w is a string of length n n and w ′ w^{\prime} is a string that can be obtained by performing a single-character edit operation on w w . We present O ( n ) O(\sqrt{n}) upper bounds for the worst-case additive sensitivity of the smallest string attractor size γ \gamma and the smallest bidirectional scheme size b \mathit{b} , which match the known lower bounds Ω ( n ) \Omega(\sqrt{n}) for γ \gamma and b \mathit{b} [Akagi et al. 2023]. Further, we present matching upper and lower bounds for the worst-case additive sensitivity of the Lempel-Ziv family - Θ ( n 2 3 ) \Theta(n^{\frac{2}{3}}) for LZSS and LZ-End, and Θ ( n ) \Theta(n) for LZ78. 1 Introduction Measuring the repetitiveness of strings is one of the most fundamental studies on strings which attract recent attention. Examples of string repetitiveness measures are the substring complexity \delta [ 8 ] , the smallest string attractor size \gamma [ 6 ] , the number r of runs in the Burrows-Wheeler transform [ 3 ] , the size \mathit{b} of the smallest bidirectional scheme [ 12 ] , the size z of the Lempel-Ziv factorization [ 13 ] (and its variants [ 12 , 9 , 7 ] ), and the smallest grammar size g [ 4 , 11 ] . We refer readers to the survey [ 10 ] for comparisons of these measures and others. Akagi et al. [ 1 ] introduced the notion of sensitivity of string repetitiveness measures, which evaluates the perturbation of the measures after an edit operation (insertion, deletion, or substitution of a character) is performed on the input string. Sensitivity is a mathematical model for robustness of string compressors/repetitiveness measures against dynamic changes and/or errors. Of two versions of sensitivity, the work in [ 1 ] mostly focuses on the worst-case multiplicative sensitivity \mathsf{MS}_{{\mathrm{edit}}}(c,n) with edit operation \mathrm{edit}\in\{\mathrm{ins},\mathrm{del},\mathrm{sub}\} that is defined to be the maximum of c(T^{\prime})/c(T) , where c is the measure, T is any string of length n , and T^{\prime} is any string that can be obtained by a single-character edit operation from T . The other alternative is the worst-case additive sensitivity \mathsf{AS}_{{\mathrm{edit}}}(c,n) , which is defined to be the maximum of c(T^{\prime})-c(T) . We note that most of the results on the additive sensitivity in [ 1 ] are byproducts of their multiplicative sensitivity, and they are evaluated in terms of the measure c . For instance, the multiplicative sensitivity 3 of the overlapping LZSS \mathit{z}_{\mathrm{ss}} immediately leads to a 2\mathit{z}_{\mathrm{ss}} additive sensitivity [ 1 ] . The behavior of \mathsf{AS}_{{\mathrm{edit}}}(c,n) in terms of n is not well understood for a majority of measures, except for the trivial bound for \delta [ 1 ] and the \Omega(\sqrt{n}) lower bounds for \gamma , \mathit{b} and r [ 1 , 5 ] . In this paper, we show tight upper and lower bounds of \mathsf{AS}_{{\mathrm{edit}}}(c,n) in terms of n for the following measures c : the smallest string attractor \gamma , the smallest bidirectional scheme \mathit{b} , the Lempel-Ziv family including the overlapping/non-overlapping LZSS \mathit{z}_{\mathrm{ss}} and \mathit{z}_{\mathrm{ssno}} [ 12 ] , the optimal LZ-End \mathit{z}_{\mathrm{end}} [ 7 ] , and LZ78 \mathit{z}_{\mathrm{78}} [ 14 ] . We present O(\sqrt{n}) upper bounds for the worst-case additive sensitivity of \gamma and \mathit{b} , which match the known lower bounds \Omega(\sqrt{n}) for \gamma and \mathit{b} [ 1 ] . Further, we present matching upper and lower bounds \Theta(n^{\frac{2}{3}}) for the worst-case additive sensitivity of \mathit{z}_{\mathrm{ss}} , \mathit{z}_{\mathrm{ssno}} , and \mathit{z}_{\mathrm{end}} . We also present an \Omega(n) lower bound instance for the worst-case additive sensitivity of \mathit{z}_{\mathrm{78}} , which matches a naïve O(n) upper bound. Our results and previous results are summarized in Table 1 . Independently to our work, Blocki et al. [ 2 ] presented an O(n^{\frac{2}{3}}) upper bound and an \Omega(n^{\frac{2}{3}}\log^{\frac{1}{3}}n) lower bound for the worst-case additive sensitivity of the non-overlapping LZ77 factorizations [ 13 ] . While they provide a specific constant factor for the upper bound, their lower bound is slightly loose (up to a logarithmic factor). We remark that our tight \Theta(n^{\frac{2}{3}}) sensitivity bounds for (non)overlapping LZSS can readily extend to (non)overlapping LZ77. Table 1: The worst-case additive sensitivity of the string compressors/repetitiveness measures studied in this paper, evaluated in terms of the length n of the string. All the bounds hold for any type of edit operations (substitutions, insertions, and deletions). All the bounds except those from [ 1 , 5 ] are our new results. string compressor/repetitiveness measure worst-case additive sensitivity upper bound lower bound substring complexity \delta 1 [ 1 ] 1 [ 1 ] smallest string attractor \gamma O(\sqrt{n}) \Omega(\sqrt{n}) [ 1 ] smallest bidirectional scheme \mathit{b} O(\sqrt{n}) \Omega(\sqrt{n}) [ 1 ] non-overlapping LZSS \mathit{z}_{\mathrm{ssno}} O(n^{\frac{2}{3}}) \Omega(n^{\frac{2}{3}}) overlapping LZSS \mathit{z}_{\mathrm{ss}} O(n^{\frac{2}{3}}) \Omega(n^{\frac{2}{3}}) non-overlapping LZ77 \mathit{z}_{\mathrm{77no}} O(n^{\frac{2}{3}}) [ 2 ] \Omega(n^{\frac{2}{3}}) overlapping LZ77 \mathit{z}_{\mathrm{77}} O(n^{\frac{2}{3}}) \Omega(n^{\frac{2}{3}}) optimal LZ-End \mathit{z}_{\mathrm{end}} O(n^{\frac{2}{3}}) \Omega(n^{\frac{2}{3}}) greedy LZ-End \mathit{z}_{\mathrm{e}} - \Omega(n^{\frac{2}{3}}) LZ78 \mathit{z}_{\mathrm{78}} O(n) \Omega(n) run-length BWT r - \Omega(\sqrt{n}) [ 5 ] 2 Preliminaries 2.1 Strings Let \Sigma be an alphabet . An element of \Sigma^{*} is called a string . The length of a string T is denoted by |T| . The empty string \varepsilon is the string of length 0. Let \Sigma^{n} denote the set of strings of length n . For a string T=xyz , x , y and z are called a prefix , substring , and suffix of T , respectively. Let \mathsf{Substr}(T) denote the set of substrings of s . The i -th symbol of a string T is denoted by T[i] for 1\leq i\leq|T| . Let T[i..j] denote the substring of T that begins at position i and ends at position j for 1\leq i\leq j\leq|T| . For convenience, let T[i..j]=\varepsilon when i>j . For a sequence s_{1},\ldots,s_{k} of strings, let \prod_{i=1}^{k}s_{k}=s_{1}\cdots s_{k} denote their concatenations. 2.2 String attractors Let T be a non-empty string of length n . A set \Gamma=\{p_{1},\ldots,p_{\ell}\} of \ell positions in T is said to be a string attractor [ 6 ] of T if any substring s\in\mathsf{Substr}(T) has an occurrence [i,j] such that s=T[i..j] and i\leq p_{k}\leq j for some p_{k}\in\Gamma . Since the set \{1,\ldots,n\} of all positions in T clearly satisfies the definition, any string has a string attractor. The size of a string attractor is the number of positions in it. Let \gamma(T) denote the size of the smallest string attractor(s) for T . For instance, the set \{5,7\} of positions is a string attractor of string T=\mathtt{baaaabbaaa} (see also Fig. 1 ), and it is the smallest since T contains two distinct characters \mathtt{a,b} . 2.3 Bidirectional macro scheme A sequence f_{1},\ldots,f_{b} of non-empty substrings of a string T is said to be a bidirectional macro scheme of T if T=f_{1}\cdots f_{b} and each f_{k}=T[p_{k},p_{k}+|f_{k}|-1] (called a phrase) is either a single character or a