Sequences in London 2024

Sensitivity of string compressors
and repetitiveness measures
Shunsuke Inenaga(Kyushu University)

Data Compression

Can you compress
these files?

massivedata

SNS, IoT, M2M,Sensors, etc.

...
DNA databases

zip? gzip? lha?
7z? bzip2? xz?

Boss

CACTCGCATCG...
CACACGCATCG...
CACTCGCGTCG...
...
CTCTCGCATGG...

Which compressor
should I use?

YouNew Criterion for Compressors
Review 1 for Compressor C

Review 2 for Compressor C

T = ababaaba…abT’ = aXabaaba..ab

C(T)

C(T’)

(1) Excellent compression ratio!
(2) Super fast (de)compression!
(3) Searchable compression!

But the compressed size blew up
just after a small edit operation!!

The compressor C looks
great because it satisfies
all the known criteria(1),(2),(3)!

What!? Can it happen?
My company deals withdynamic data…, so it canbe problematic.

New criterion (4) Compression Sensitivity

Compression Sensitivity[Definition]
Sensitivity of compressor C

T’ is any string that can beobtained by performing a single
character edit operation on T .

Worst-case multiplicative sensitivity
nmax{|C(T’)|/|C(T)| : T ∈ Σ , EditDistance(T, T’ ) = 1}

Worst-case additive sensitivity
nmax{|C(T’)|−|C(T)| : T ∈ Σ , EditDistance(T, T’ ) = 1}

[Intuition]

Small sensitivity ⟺ Robust compression under edits/errors

Multiplicative Compression Sensitivity
Compressor / Measure
LZ77 z
LZSS sUpper BoundLower Bound
Very few previous work

Bidirectional scheme b
Smallest grammar g*
BISECTION gBISCTN
GCIS gGCIS
LZ78 g78Ω(n1/4)RLBWT rΩ(log n) [SOFSEM 2021]

Substring complexity δ[Lagarde & Perifel
SODA 2018]

Lower Bound for RLBWT rReversed Fibonacci word sirev

r：RLE size of the rightmost columnof the lexicographically sorted
rotations of the input string.

i = logφ nr(sirev) = 2r(b s irev) = Ω(log n)Multi. Sensitivity of Repetitiveness Measures & Dictionary Comp.
Compressor / Measure
Substring complexity δSmallest string attractor γ

Bidirectional scheme b
LZ77 z
LZSS sLZ78 g78

Edit Operation

Upper Bounddelins/sub

1.5
2

anyO(log n)

ins/sub2222
3

delanyins
del/subins
del/sub

O((n / log n)2/3)

Lower Bound

1.5
2et al.
2.5 [BannaiESA 2022]
2
1.52
23& PerifelΩ(n1/4) [LagardeSODA 2018]Ω(n1/4)

LZEnd zEndanyO(log2 (n / d))2

RLBWT ranyO(log r log n)Ω(log n)Multiplicative Sensitivity of Grammar Compressors
Grammar compressors

Edit Operation

Upper Bound

Lower Bound

Smallest grammar g*

any

2-any

O(log (n / g*))-any

O((n / log n)2/3)

-sub2

2

ins/del|Σ|+1|Σ|

any

4

4

sub8

2

ins/del132α-balanced
AVL-grammar
RePairLongest-MatchGreedy
BisectionGCISCDAWG

Multi. Sensitivity of Repetitiveness Measures & Dictionary Comp.
Compressor / Measure
Substring complexity δSmallest string attractor γ

Bidirectional scheme b
LZ77 z
LZSS s
LZ78 g78

Edit Operation

Upper Bound

del

1.5
2

ins/subany
ins/subdelanyins
del/sub
ins
del/sub

Lowe Bound

1.5
2
O(log n)2
et al.
22 [BannaiESA 2022]
I will talk about this222
2
2
2
3
3
O((n / log n)2/3)& PerifelΩ(n1/4) [LagardeSODA 2018]Ω(n1/4)

LZEnd zEndanyO(log2 (n / d))

2RLBWT ranyO(log r log n)Ω(log n)

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

6

7

8

910

11

12

13

14

15

T= a b a a b a b a b a b a b a b

Scans T from left to right and parses T• at each fresh letter, or• at the ending position of the longest previouslyoccurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

T= a b a a b a b a b a b a b a b
Fresh letter

Scans T from left to right and parses T• at each fresh letter, or• at the ending position of the longest previously
occurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

T= a b a a b a b a b a b a b a b
Fresh letter

Scans T from left to right and parses T• at each fresh letter, or• at the ending position of the longest previously
occurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

6

7

8

9

10

11

12

1314

15

T= a b a a b a b a b a b a b a b
The ending position of the longest
previously occurring substring.
Scans T from left to right and parses T• at each fresh character, or• at the ending position of the longest previouslyoccurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

67

8

910

11

12

13

1415

T= a b a a b a b a b a b a b a b
The ending position of the longest
previously occurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1234567

8910

1112131415

T= a b a a b a b a b a b a b a b
The ending position of the longest
previously occurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

67

8

9101112131415

T= a b a a b a b a b a b a b a b
The ending position of the longest
previously occurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

234

5

67

8

910

1112

13

14

15

T= a b a a b a b a b a b a b a b
The ending position of the longest
previously occurring substring.

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

T= a b a a b a b a b a b a b a b(5, 7)

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

23

4

5

67

8

9101112131415

T= a b a a b a b a b a b a b a b(a) (b) (1, 1) (1, 3)(2, 3)(5, 8)(5, 7)

Compression size (# of phrases) = 7

LZSS (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
1

2

3

4

5

6

7

8

910

11

12

13

1415

T= a b a a b a b a b a b a b a b(a) (b) (1, 1) (1, 3)(2, 3)(5, 8)(5, 7)

Compression size (# of phrases) = 7

LZSS with self-references
123

456789101112131415

T= a b a a b a b a b a b a b a b(a) (b) (1, 1) (1, 3)(5, 13)Compression size (# of phrases) = 5

Upper Bound for Sensitivity of LZSS
𝑠𝑠 : LZSS compression size before edit𝑠𝑠 ′ : LZSS compression size after edit

Theorem
For any string, we have the following:Multiplicative sensitivity for LZSS is 𝑠𝑠 ′ /𝑠𝑠 ≤ 3.
Additive sensitivity for LZSS is𝑠𝑠 ′ − 𝑠𝑠 ≤ 2𝑠𝑠 − 2.
These upper bounds hold for both versions of LZSS
with/without self-references.

Upper Bound for Sensitivity of LZSS
Proof for 𝑠𝑠 ′ ≤ 3𝑠𝑠 (without self-references)

Claim 1: For the phrase w that contains the edited position i,# phrases starting in the interval for w can increase to at most 3.
TiaiT’$

Upper Bound for Sensitivity of LZSS
Proof for 𝑠𝑠 ′ ≤ 3𝑠𝑠 (without self-references)

Claim 1: For the phrase w that contains the edited position i,# phrases starting in the interval for w can increase to at most 3.
Tw

LZSS(T )

iaw
iT’w

$

Upper Bound for Sensitivity of LZSS
Proof for 𝑠𝑠 ′ ≤ 3𝑠𝑠 (without self-references)

Claim 1: For the phrase w that contains the edited position i,# phrases starting in the interval for w can increase to at most 3.
Tw

uLZSS(T )iaw
iT’uav$v

Upper Bound for Sensitivity of LZSS
Proof for 𝑠𝑠 ′ ≤ 3𝑠𝑠 (without self-references)

Claim 1: For the phrase w that contains the edited position i,# phrases starting in the interval for w can increase to at most 3.
Tw

uLZSS(T )iavw
iT’LZSS(T’ )

ua$v
u$v

x

Upper Bound for Sensitivity of LZSS
Proof for 𝑠𝑠 ′ ≤ 3𝑠𝑠 (without self-references)

Claim 2: For any phrase w to the right of the edited position i,# phrases starting in the interval for w can increase to at most 3.
T

uiaLZSS(T )T’LZSS(T’ )vuav = ww

iu’ $vu’ avxUpper/Lower Bounds for Sensitivity of LZSSTheorem (Upper Bound)
For any string, we have the following:Multiplicative sensitivity for LZSS is 𝑠𝑠 ′ /𝑠𝑠 ≤ 3.
Additive sensitivity for LZSS is𝑠𝑠 ′ − 𝑠𝑠 ≤ 2𝑠𝑠 − 2.
Theorem (Lower Bound)

There exists a family of strings of length n such that:Multiplicative sensitivity for LZSS is lim inf(𝑠𝑠 ′ /𝑠𝑠) = 3.
𝑠𝑠→∞

Additive sensitivity for LZSS is 𝑠𝑠 ′ − 𝑠𝑠 = 2𝑠𝑠 − Θ

𝑠𝑠 = Ω( 𝑛𝑛).

For the lower bound, we showed strings that have theaforementioned worst-case situations for most of their phrases.

Sensitivity of Compression Software
Does similar happen fora real-world compression software?

We tested compression software 7zip = LZSS + RangeCoder.
 Supports .7z compression format.
 Compression ratio of 7zip is usually
better than that of zip by 30-70%.

Sensitivity of Compression Software (7zip)
stringX： length 1,172,887 (1.12 MB)!“#$%&‘()*+,./0123456789:;?@ABCDEFGHIJKLMN!”#$%&’()*+,./01234
56789:;?@ABCDEFGHIJKLM!“#$%&‘()*+,./0123456789:;<=>?@ABCDEFGHIJKL!”#$%&’()*+,./0123456789:;<=>?@ ABCDE...
’!“#$%&!
”#$%!“#$!”#!“!!{OOPOPQOPQROPQRSOPQRSTOPQRSTUOPQRST ...

stringXp

Replace the 1083rd letter “ { “ with “ ~ ”!“#$%&‘()*+,./0123456789:;?@ABCDEFGHIJKLMN!”#$%&’()*+,./01234
56789:;?@ABCDEFGHIJKLM!“#$%&‘()*+,./0123456789:;<=>?@ABCDEFGHIJKL!”#$%&’()*+,./0123456789:;<=>?@ ABCDE...
’!“#$%&!
”#$%!“#$!”#!“!!~OOPOPQOPQROPQRSOPQRSTOPQRSTUOPQRST ...

7zip compressed size

stringX.7z

4,884 byte

stgingXp.7z

7,189 byte

1.5 times
bigger!References
1. Sensitivity of string compressors and repetitiveness measures.
T. Akagi, M. Funakoshi, S. Inenaga(Information & Computation 2023)
2. Novel results on the number of runs of the Burrows-Wheeler-transform.
S. Giuliani,. S. Inenaga, Z. Lipták, N. Prezza, M. Sciortino, A. Toffanello(SOFSEM 2021)
3. Bit Catastrophes for the Burrows-Wheeler Transform.
S. Giuliani, S. Inenaga, Z. Lipták, G. Romana, M. Sciortino, C. Urbina(DLT 2023)
4. On Sensitivity of Compact Directed Acyclic Word Graphs.
H. Fujimaru, Y. Nakashima, S. Inenaga(WORDS 2023)
5. Sensitivity of CDAWGs is constant.
R. Hamai, S. Inenaga(Unpublished)