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. This notion enables one to measure the robustness of compression algorithms in terms of errors and/or dynamic changes occurring in the input string. In this paper, we analyze the worst-case multiplicative sensitivity of string compression algorithms, which is defined by maxT∈Σ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 (2 or 3, depending on the version of the Lempel-Ziv 77 and the edit operation type), i.e., the size of the Lempel-Ziv 77 factorizations can be larger by only a small constant factor. We strengthen our upper bound results by presenting matching lower bounds on the worst-case sensitivity for all these major versions of the Lempel-Ziv 77 factorizations. We generalize these results to the smallest bidirectional scheme b. In addition, we show that the sensitivity of a grammar-based compressor called GCIS (Grammar Compression by Induced Sorting) is also a small constant. Further, we extend the notion of the worst-case sensitivity to string repetitiveness measures such as the smallest string attractor size γ and the substring complexity δ, and show that the worst-case sensitivity of δ is also a small constant. These results contrast with the previously known related results such that the size z78 of the Lempel-Ziv 78 factorization can increase by a factor of Ω(n1/4) (shown by Lagarde and Perifel), and the number r of runs in the Burrows-Wheeler transform can increase by a factor of Ω(log⁡n) (shown by Giuliani et al.) when a character is prepended to an input string of length n. By applying our sensitivity bounds of δ or the smallest grammar to known results (cf. Navarro's survey) some non-trivial upper bounds for the sensitivities of important string compressors and repetitiveness measures including γ, r, LZ-End, RePair, LongestMatch, and AVL-grammar, are derived. We also exhibit the worst-case additive sensitivity maxT∈Σn⁡{C(T′)−C(T):ed(T,T′)=1}, which allows one to observe more details in the changes of the output sizes.

A string w is called a minimal absent word for another string T if w does not occur (as a substring) in T and all proper substrings of w occur in T. State-of-the-art data structures for reporting the set MAW(T) of MAWs from a given string T of length n require O(n) space, can be built in O(n) time, and can report all MAWs in O(|MAW(T)|) time upon a query. This paper initiates the problem of computing MAWs from a compressed representation of a string. In particular, we focus on the most basic compressed representation of a string, run-length encoding (RLE), which represents each maximal run of the same characters a by a^p where p is the length of the run. Let m be the RLE-size of string T. After categorizing the MAWs into five disjoint sets ℳ₁, ℳ₂, ℳ₃, ℳ₄, ℳ₅ using RLE, we present matching upper and lower bounds for the number of MAWs in ℳ_i for i = 1,2,4,5 in terms of RLE-size m, except for ℳ₃ whose size is unbounded by m. We then present a compact O(m)-space data structure that can report all MAWs in optimal O(|MAW(T)|) time.

A string w is called a minimal absent word (MAW) for another string T if w does not occur in T but the proper substrings of w occur in T. For example, let Σ={a,b,c} be the alphabet. Then, the set of MAWs for string w=abaab is {aaa,aaba,bab,bb,c}. In this paper, we study combinatorial properties of MAWs in the sliding window model, namely, how the set of MAWs changes when a sliding window of fixed length d is shifted over the input string T of length n, where 1≤d