Tight Additive Sensitivity on LZ-style Compressors and String Attractors
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908427315314688 |
|---|---|
| author | Fujie, Yuto Shibata, Hiroki Nakashima, Yuto Inenaga, Shunsuke |
| author_facet | Fujie, Yuto Shibata, Hiroki Nakashima, Yuto Inenaga, Shunsuke |
| contents | The worst-case additive sensitivity of a string repetitiveness measure $c$ is defined to be the largest difference between $c(w)$ and $c(w')$, where $w$ is a string of length $n$ and $w'$ 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 $γ$ and the smallest bidirectional scheme size $b$, which match the known lower bounds $Ω(\sqrt{n})$ for $γ$ 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 - $Θ(n^{\frac{2}{3}})$ for LZSS and LZ-End, and $Θ(n)$ for LZ78. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22778 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Additive Sensitivity on LZ-style Compressors and String Attractors Fujie, Yuto Shibata, Hiroki Nakashima, Yuto Inenaga, Shunsuke Data Structures and Algorithms Computational Complexity The worst-case additive sensitivity of a string repetitiveness measure $c$ is defined to be the largest difference between $c(w)$ and $c(w')$, where $w$ is a string of length $n$ and $w'$ 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 $γ$ and the smallest bidirectional scheme size $b$, which match the known lower bounds $Ω(\sqrt{n})$ for $γ$ 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 - $Θ(n^{\frac{2}{3}})$ for LZSS and LZ-End, and $Θ(n)$ for LZ78. |
| title | Tight Additive Sensitivity on LZ-style Compressors and String Attractors |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2506.22778 |