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$. This notion enables one to measure the robustness of compression algorithms in terms of errors and/or dynamic ch...
Bewaard in:
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Artikel |
| Gepubliceerd in: |
2021
|
| Onderwerpen: | |
| Online toegang: | https://arxiv.org/abs/2107.08615 http://arxiv.org/abs/2107.08615 |
| Tags: |
Geen labels, Wees de eerste die dit record labelt!
|
| _version_ | 1879174353521737728 |
|---|---|
| author | Akagi, Tooru Funakoshi, Mitsuru Inenaga, Shunsuke |
| author_browse | Akagi, Tooru Funakoshi, Mitsuru Inenaga, Shunsuke |
| author_facet | Akagi, Tooru Funakoshi, Mitsuru Inenaga, Shunsuke |
| author_sort | Akagi, Tooru |
| building | arXiv |
| collection | Acceso abierto |
| description | 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 $\max_{T \in Σ^n}\{C(T')/C(T) : ed(T, T') = 1\}$, where $ed(T, T')$ denotes the edit distance between $T$ and $T'$. For the most common versions of the Lempel-Ziv 77 compressors, we prove that the worst-case multiplicative sensitivity is upper bounded by a small constant, and give matching lower bounds. We generalize these results to the smallest bidirectional scheme $b$. In addition, we show that the sensitivity of a grammar-based compressor called GCIS 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 $z_{\rm 78}$ of the Lempel-Ziv 78 factorization can increase by a factor of $Ω(n^{1/4})$ [Lagarde and Perifel, 2018], and the number $r$ of runs in the Burrows-Wheeler transform can increase by a factor of $Ω(\log n)$ [Giuliani et al., 2021] 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 (c.f. [Navarro, 2021]), 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. |
| doi_str_mv | 10.1016/j.ic.2022.104999 |
| first_indexed | 2026-10-16T00:11:50Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2107.08615</identifier><datestamp>2023-02-10</datestamp>
<dc:title>Sensitivity of string compressors and repetitiveness measures</dc:title>
<dc:creator>Akagi, Tooru</dc:creator>
<dc:creator>Funakoshi, Mitsuru</dc:creator>
<dc:creator>Inenaga, Shunsuke</dc:creator>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:description>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 $\max_{T \in Σ^n}\{C(T')/C(T) : ed(T, T') = 1\}$, where $ed(T, T')$ denotes the edit distance between $T$ and $T'$. For the most common versions of the Lempel-Ziv 77 compressors, we prove that the worst-case multiplicative sensitivity is upper bounded by a small constant, and give matching lower bounds. We generalize these results to the smallest bidirectional scheme $b$. In addition, we show that the sensitivity of a grammar-based compressor called GCIS 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 $z_{\rm 78}$ of the Lempel-Ziv 78 factorization can increase by a factor of $Ω(n^{1/4})$ [Lagarde and Perifel, 2018], and the number $r$ of runs in the Burrows-Wheeler transform can increase by a factor of $Ω(\log n)$ [Giuliani et al., 2021] 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 (c.f. [Navarro, 2021]), 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. </dc:description>
<dc:description>The journal version is superceded by this version (we added almost tight bounds for Bisection with insertions and deletions)</dc:description>
<dc:date>2021-07-19</dc:date>
<dc:date>2023-02-09</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2107.08615</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2107.08615</dc:identifier>
<dc:identifier>Information and Computation, Volume 291, March 2023, 104999</dc:identifier>
<dc:identifier>doi:10.1016/j.ic.2022.104999</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2107.08615 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:11:50Z |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| record_format | oai_dc |
| spelling | arxiv-2107.086152023-02-10 Sensitivity of string compressors and repetitiveness measures Akagi, Tooru Funakoshi, Mitsuru Inenaga, Shunsuke Data Structures and Algorithms 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 $\max_{T \in Σ^n}\{C(T')/C(T) : ed(T, T') = 1\}$, where $ed(T, T')$ denotes the edit distance between $T$ and $T'$. For the most common versions of the Lempel-Ziv 77 compressors, we prove that the worst-case multiplicative sensitivity is upper bounded by a small constant, and give matching lower bounds. We generalize these results to the smallest bidirectional scheme $b$. In addition, we show that the sensitivity of a grammar-based compressor called GCIS 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 $z_{\rm 78}$ of the Lempel-Ziv 78 factorization can increase by a factor of $Ω(n^{1/4})$ [Lagarde and Perifel, 2018], and the number $r$ of runs in the Burrows-Wheeler transform can increase by a factor of $Ω(\log n)$ [Giuliani et al., 2021] 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 (c.f. [Navarro, 2021]), 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. The journal version is superceded by this version (we added almost tight bounds for Bisection with insertions and deletions) 2021-07-19 2023-02-09 text https://arxiv.org/abs/2107.08615 http://arxiv.org/abs/2107.08615 Information and Computation, Volume 291, March 2023, 104999 doi:10.1016/j.ic.2022.104999 |
| spellingShingle | Data Structures and Algorithms Akagi, Tooru Funakoshi, Mitsuru Inenaga, Shunsuke Sensitivity of string compressors and repetitiveness measures |
| title | Sensitivity of string compressors and repetitiveness measures |
| title_full | Sensitivity of string compressors and repetitiveness measures |
| title_fullStr | Sensitivity of string compressors and repetitiveness measures |
| title_full_unstemmed | Sensitivity of string compressors and repetitiveness measures |
| title_short | Sensitivity of string compressors and repetitiveness measures |
| title_sort | sensitivity of string compressors and repetitiveness measures |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2107.08615 http://arxiv.org/abs/2107.08615 |
| work_keys_str_mv | AT akagitooru sensitivityofstringcompressorsandrepetitivenessmeasures AT funakoshimitsuru sensitivityofstringcompressorsandrepetitivenessmeasures AT inenagashunsuke sensitivityofstringcompressorsandrepetitivenessmeasures |