冬のLAシンポジウム2021

一般セッション [22]文字列圧縮アルゴリズムの感度
赤木亨 （九州大学）
舩越満 （九州大学）〇稲永俊介（九州大学）

データ圧縮これ圧縮しといて

IoT/M2M通信
半自動生成データ

大量ログ

上司

...
配列データベース

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

どの圧縮法がいいんだろう…?

zip? gzip? lha?
7z? bzip2? xz?
新入社員

圧縮法の新評価指標
圧縮ソフトウェア C のレビュー１

圧縮ソフトウェア C のレビュー２

T = ababaaba…abT’ = aXabaaba..ab

C(T)

C(T’)

テストデータが相当縮みました！
圧縮解凍も爆速です！
しかも圧縮したまま検索できます！

でも、試しに1文字編集してみたらいきなり圧縮率悪くなりました…

レビュー読んでみたら(1) 圧縮率(2) 圧縮/展開速度(3) 圧縮検索
全部揃った C が良さそう！

え～、そんなことあるの？
うちの会社で扱うデータは更新されるから不安だなぁ…

本研究：新たな評価指標 (4) 圧縮感度 を提案

圧縮感度
【定義】
圧縮アルゴリズム C の感度

T’ は T に１文字編集操作（挿入・削除・置換）を行って得られる任意の文字列

最悪時感度（比）nmax{|C(T’)|/|C(T)| : T ∈ Σ , EditDistance(T, T’ ) = 1}

最悪時感度（差分）nmax{|C(T’)|−|C(T)| : T ∈ Σ , EditDistance(T, T’ ) = 1}

【直感的理解】感度が小さい圧縮 ⟺ 編集やエラーに影響されにくい圧縮

編集やエラーを含むデータ
Wikipediaページの更新履歴-* [[bzip]] (bunzip) - 特許侵害のために配布が中止された高圧縮形式。[[算術符号]]使用。

* [[bzip]] (*.bz) - 特許問題+のために配布が中止された高圧縮形式。[[算術符号]]使用。

-* [[bzip2]] (bunzip ver.2)- 主に[[UNIX]]で使われるオープンソースの高圧縮形式。bzipの後継として開発された。

* [[bzip2]] (*.bz 2)- 主に[[UNIX]]で使われるオー+プンソースの高圧縮形式。bzipの後継として開発された。

DNAシーケンシング

http://www.chevreux.org/thesis/node10.html

A?

圧縮感度（比）圧縮法・反復性指標
LZ77 z
LZSS s
双方向スキーム b
最小文法 g*BISECTION gBISCTN
GCIS gGCIS
LZ78 g78
RLBWT r
部分文字列複雑性 δ

関連研究はわずか
感度も良くない

圧縮感度（比）圧縮法・反復性指標

上界

下界

LZ77 z
LZSS s
双方向スキーム b
最小文法 g*BISECTION gBISCTN
GCIS gGCIS
LZ78 g78Ω(n1/4)RLBWT rΩ(log n) [SOFSEM 2021]

部分文字列複雑性 δ[Lagarde & Perifel
SODA 2018]

RLBWT の圧縮感度（下界）�𝐹𝐹：逆向きフィボナッチ文字列

𝐹𝐹�6ab𝐹𝐹�6r：入力文字列のローテーションを辞書式順序に整列した行列の最右列文字列の連長圧縮サイズa

辞書式順序にソート b5a8

b の追加によってソート順が3a1b1a2b2a5
b大きく変わるr(𝐹𝐹�6 ) = 2r(b𝐹𝐹�6 ) = 6

任意の i ≥ 2 について，r(𝐹𝐹�𝑖𝑖 ) = 2 かつ r(b𝐹𝐹�𝑖𝑖 ) = i = log 𝜙𝜙 𝑛𝑛
 RLBWT の圧縮感度の下界は r(b𝐹𝐹�𝑖𝑖 )/r(𝐹𝐹�𝑖𝑖 ) = Ω(log n)

他の圧縮アルゴリズムの感度はどれくらいなんだろう…？

圧縮感度（比）圧縮法・反復性指標

LZ77 z
LZSS s編集操作

上界下界任意挿入
削除・置換

双方向スキーム b

任意最小文法 g*

任意

BISECTION gBISCTN

任意GCIS gGCIS

任意

LZ78 g78

任意Ω(n1/4)RLBWT r挿入Ω(log n) [SOFSEM 2021]

部分文字列複雑性 δ

削除
挿入・置換

[Lagarde & Perifel
SODA 2018]主要な圧縮手法の感度は圧縮感度（比） （本研究成果） O(1) であることを証明
圧縮法・反復性指標

編集操作

上界下界任意

22挿入

22

削除・置換

33双方向スキーム b

任意

22

最小文法 g*

任意

2-

BISECTION gBISCTN

任意22

GCIS gGCIS

任意44

LZ78 g78

任意-Ω(n1/4)[Lagarde & Perifel
SODA 2018]

RLBWT r挿入

O(log r log n)Ω(log n)[SOFSEM 2021]

削除

1.51.5挿入・置換

22

LZ77 z
LZSS s部分文字列複雑性 δ多くの圧縮法についてタイトな上下界を与えた

圧縮感度（比） （本研究成果）
圧縮法・反復性指標

編集操作

上界下界

任意22挿入22削除・置換33

双方向スキーム b

任意22

最小文法 g*

任意2-

BISECTION gBISCTN

任意22

GCIS gGCIS

任意44

LZ78 g78

任意-Ω(n1/4)[Lagarde & Perifel
SODA 2018]

RLBWT r挿入

O(log r log n)Ω(log n)[SOFSEM 2021]

削除

1.5

1.5

挿入・置換

22

LZ77 z
LZSS s部分文字列複雑性 δ圧縮感度（比） （本研究成果）
圧縮法・反復性指標

LZSS圧縮について説明編集操作

上界下界任意

22

挿入

22

削除・置換

33

双方向スキーム b任意

22

最小文法 g*

任意

2-BISECTION gBISCTN

任意22

GCIS gGCIS

任意

44

LZ78 g78

任意-Ω(n1/4)[Lagarde & PerifelSODA 2018]

RLBWT r挿入

O(log r log n)Ω(log n)[SOFSEM 2021]

削除

1.5

1.5

挿入・置換

22

LZ77 z
LZSS s部分文字列複雑性 δLZSS圧縮 (zip / gzip / lha / 7zip / png …)
LZSS [Storer-Szymanski, 1982]
12

3

4

5

6

7

8910111213

14

15

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

文字列を左から右にスキャンしながら分割していく• 初出現の文字が出たら区切る• 直前の分割位置までに出現している最長の部分文字列で区切る

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

234

5

678

910111213

1415

T= a b a a b a b a b a b a b a b
初出現の文字

文字列を左から右にスキャンしながら分割していく• 初出現の文字が出たら区切る• 直前の分割位置までに出現している最長の部分文字列で区切る

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

14

15

T= a b a a b a b a b a b a b a b
初出現の文字文字列を左から右にスキャンしながら分割していく• 初出現の文字が出たら区切る• 直前の分割位置までに出現している最長の部分文字列で区切る

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

2

3

45678

910

1112

13

14

15

T= a b a a b a b a b a b a b a b
直前の分割位置までに出現している最長の部分文字列で区切る

文字列を左から右にスキャンしながら分割していく• 初出現の文字が出たら区切る• 直前の分割位置までに出現している最長の部分文字列で区切る

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

2

3

4

56789101112131415

T= a b a a b a b a b a b a b a b
直前の分割位置までに出現している最長の部分文字列で区切る

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

23456789

101112131415

T= a b a a b a b a b a b a b a b
直前の分割位置までに出現している最長の部分文字列で区切る

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

2

3456789101112131415

T= a b a a b a b a b a b a b a b
直前の分割位置までに出現している最長の部分文字列で区切る

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

T= a b a a b a b a b a b a b a b
直前の分割位置までに出現している最長の部分文字列で区切る

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

2

34

5

67

89

101112131415

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]
1234

5678

910

1112131415

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)

圧縮サイズ（項数）＝ 7

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

4

5

67

8

910

11

12

131415

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)

圧縮サイズ（項数）＝ 7

LZSS （自己参照あり）
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)

圧縮サイズ（項数）＝ 5

LZSS圧縮の感度（上界）
𝑠𝑠 ：編集前の文字列のLZSS圧縮サイズ
𝑠𝑠 ′ ：編集後の文字列のLZSS圧縮サイズ
定理 [LZSS圧縮の感度の上界]

任意の文字列に対して以下が成り立つ．
感度（比）𝑠𝑠 ′ /𝑠𝑠 ≤ 3
感度（差分） 𝑠𝑠 ′ − 𝑠𝑠 ≤ 2𝑠𝑠 − 2※ この上界は自己参照なし/ありの両方で成立

LZSS圧縮の感度（上界）【𝑠𝑠 ′ ≤ 3𝑠𝑠 を示す】

Claim 1: 編集位置 i を含む項 w について，w の区間内から始まる項の個数は高々3に増える
TiaiT’$

LZSS圧縮の感度（上界）【𝑠𝑠 ′ ≤ 3𝑠𝑠 を示す】

Claim 1: 編集位置 i を含む項 w について，w の区間内から始まる項の個数は高々3に増える
Tw

LZSS(T )

iaw
iT’w

$

LZSS圧縮の感度（上界）【𝑠𝑠 ′ ≤ 3𝑠𝑠 を示す】

Claim 1: 編集位置 i を含む項 w について，w の区間内から始まる項の個数は高々3に増える
TwuLZSS(T )iaw
iT’uav$v

LZSS圧縮の感度（上界）【𝑠𝑠 ′ ≤ 3𝑠𝑠 を示す】

Claim 1: 編集位置 i を含む項 w について，
w の区間内から始まる項の個数は高々3に増える
Tw

u

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

ua$v
u$v

xLZSS圧縮の感度（上界）【𝑠𝑠 ′ ≤ 3𝑠𝑠 を示す】

Claim 2: 編集位置 i より右側にある項 w について，w の区間内から始まる項の個数は高々3に増える
TuiaLZSS(T )T’LZSS(T’ )v
uav = wwiu’ $v
u’ av

xLZSS圧縮の感度（上界・下界）
定理 [LZSS圧縮の感度の上界]
任意の文字列に対して以下が成り立つ．
感度（比）𝑠𝑠 ′ /𝑠𝑠 ≤ 3
感度（差分） 𝑠𝑠 ′ − 𝑠𝑠 ≤ 2𝑠𝑠 − 2定理 [LZSS圧縮の感度の下界]

以下を満たす長さ n の文字列が存在する．
感度（比）lim inf(𝑠𝑠 ′ /𝑠𝑠) = 3𝑠𝑠→∞′感度（差分） 𝑠𝑠 − 𝑠𝑠 = 2𝑠𝑠 − Θ【下界の証明の概要】

𝑠𝑠 = Ω( 𝑛𝑛)

前ページの上界の証明に限りなく近い状況を満たす文字列の構成法を示した．

実際の圧縮ソフトウェアの感度理論的に2倍とか3倍になることはわかったけど、実際のソフトでそんな状況起こるのかな…？

圧縮ソフトの圧縮感度を調査

 拡張子 .7z の圧縮形式をサポート
 7z は zip の上位互換版（7z のほうが 30～70% 圧縮率がよい） 7z = LZSS＋RangeCoderの感度が高くなるように実際の圧縮ソフトウェアの感度 7z巧妙に構成された

stringX： 長さ 1,172,887 (1.12 MB)

とてもイジワルな文字列!“#$%&‘()*+,./0123456789:;?@ABCDEFGHIJKLMN!”#$%&’()*+,./01234
56789:;?@ABCDEFGHIJKLM!“#$%&‘()*+,./0123456789:;<=>?@ABCDEFGHIJKL!”#$%&’()*+,./0123456789:;<=>?@ ABCDE
中略’!“#$%&!
”#$%!“#$!”#!“!!{OOPOPQOPQROPQRSOPQRSTOPQRSTUOPQRST 以降略

stringXp

1083 番目の文字 “ { “ を “ ~ ” で置換!“#$%&‘()*+,./0123456789:;?@ABCDEFGHIJKLMN!”#$%&’()*+,./01234
56789:;?@ABCDEFGHIJKLM!“#$%&‘()*+,./0123456789:;<=>?@ABCDEFGHIJKL!”#$%&’()*+,./0123456789:;<=>?@ABCDE
中略’!“#$%&!
”#$%!“#$!”#!“!!~OOPOPQOPQROPQRSOPQRSTOPQRSTUOPQRST 以降略

7-Zipで圧縮したサイズ

stringX.7z
stgingXp.7z

4,884 バイト 感度（比）7,189 バイト 約1.5倍!!

まとめと今後の課題


圧縮アルゴリズムの新たな評価指標 圧縮感度 を提案し，多くの圧縮アルゴリズムの感度のタイトな上下界を示した．



実際の圧縮ソフトに対して，感度が約1.5倍になる実例を発見した （1文字/120万文字 の編集で達成）．

以下の圧縮法の上界・下界の解明
圧縮法・反復性指標

上界（比）

下界（比）

最小文法 g*2-

LZ78 g78-Ω(n1/4)RLBWT rO(log r log n)Ω(log n)

文字列アトラクタ γO(log n)2

AVL / a-balanced / Recomression 文法

O(log n)2--

RePair / Greedy / Longest 文法

圧縮感度（差分）圧縮法・反復性指標

上界

下界

下界 (nの関数)

LZ77圧縮 z𝑧𝑧 − 1𝑧𝑧 − 1

Ω( 𝑛𝑛)LZSS圧縮 sAVL 文法
双方向スキーム b
最小文法 g*2𝑠𝑠 − 𝑠𝑠O(s log n)
𝑏𝑏 + 2g*

BISECTION gBISCTN

gBISCTN

GCIS圧縮 gGCIS

3gGCIS

LZ78圧縮 g78-

連長BW変換 rO(r log r log n)

部分文字列複雑性 δ1

文字列アトラクタ γO(γ log n)

2𝑠𝑠 − Θ( 𝑠𝑠)Ω( 𝑛𝑛)-

Ω( 𝑛𝑛)-

𝑏𝑏/2 − 3-

gBISCTN − 42 log 2 𝑛𝑛 − 4-Ω(𝑛𝑛/log 𝑛𝑛)

3gGCIS − 29
Ω(𝑔𝑔78 3/2 )1

γ−33𝑛𝑛/4 + 1
Ω(log 𝑛𝑛)
1

Ω( 𝑛𝑛)