3 papers
cs.DS2026
Sensitivity and Size Relationships of the Lempel-Ziv Factorization
Hiroki Shibata, Yuto Fujie
The Lempel-Ziv (LZ) factorization is one of the most fundamental methods for compressing highly repetitive strings, and the number of phrases in its factorization is considered a r…
cs.DS2026
Sensitivity of Repetitiveness Measures to String Reversal
Hideo Bannai, Yuto Fujie, Peaker Guo +4
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, , of runs in the run-leng…
cs.DS2025
Tight Additive Sensitivity on LZ-style Compressors and String Attractors
Yuto Fujie, Hiroki Shibata, Yuto Nakashima +1
The worst-case additive sensitivity of a string repetitiveness measure is defined to be the largest difference between and , where is a string of length a…