LZ77分解 1

LZ77分解とは1977年にZivとLempelによって提案された圧縮法である.彼らは翌年にも圧縮法を提案しており,そちらはLZ78分解と呼ばれる.LZ77とLZ78は違う圧縮法にも関わらず,どちらかを明記せずLZ圧縮と単純に呼ばれることがあるので注意して欲しい.

今日はLZ77分解の定義と簡単な構築方法について説明する.

少し長くなりそうなので,定義と特徴,LZ77の応用だけ話し,構築方法については後日また説明しようと思う.

まず,最初に断っておくが,今回話すLZ77の定義は1977年に発表されたオリジナルとは違うかもしれない.僕は原論文を読んだことは一度もなく,書籍や論文などの説明を読んで理解しただけである.また,ウェブでLZ77, 78に関して少し調べてみると,ウインドウを使ったアルゴリズムの説明が多いが,本記事では出てこない.更に言えば,符号化の話も出てこない.今回はもう少し抽象度の高い話をしたいと思う.おそらく,上記のウインドウを使ったアルゴリズムよりも理解しやすいと思うし,符号化の話もしないので,LZ77の本質について集中できるかと思う.

以下のサーベイ論文に従う.

 Anisa Al-Hafeedh, Maxime Crochemore, Lucian Ilie, Evguenia Kopylova, William F. Smyth, German Tischler, Munina Yusufu: A comparison of index-based lempel-Ziv LZ77 factorization algorithms. ACM Comput. Surv. 45(1): 5 (2012)

定義

文字列TのLZ77分解T=f1 f2 ... fzとは次の性質を満たす分解である.

Tのi番目から始まるファクターfjについて,

  1. もし,T[i]がi未満で出現しないなら,fj = T[i]
  2. そうでない場合,fjはi未満で少なくとも1回出現するiから始まる最長の部分文字列

例で表してみよう.

T=ababaabbaのLZ77分解は

T=a|b|aba|ab|baとなる.

f1, f2はそれぞれ,a,bが以前に出現していないので1文字で分解.f3は1文字目から始まるabaが以前に出現した最長の部分文字列となる.以下同様.

条件2の時,iから始まるファクターはi以前に少なくとも1回出現するので,その部分文字列の開始位置と長さの整数の2組で表すことが出来る.それぞれPrevious position(Prev)とLongest Previous Factor(LPF)と呼ぶことにする.

条件1の時を(-1, T[i])と表すことにすると,先ほどの例のLZ77分解は以下のように表すことが出来る.

T=a|b|aba|ab|ba

T=(-1, a), (-1, b), (1, 3), (1, 2), (2, 2)

 

各ファクターはi未満から始まる部分文字列で表されるため,先頭から順番に展開していくことでこの整数のペアの列から元の文字列を得ることが出来る.(少し詳しく述べればiから始まるファクターfj=(prev, lpf)を展開しようと思う時T[1..i-1]が展開されているはずなのでT[prev..prev+lpf-1]を展開すれば良い).

LZ77の応用

LZ77の応用は,一番は圧縮だ.先ほど説明したように,任意のファクターはその長さがどんなに長かろうが,それ以前に出現していれば整数の2組で表すことが出来る.最近注目されている文法圧縮もそのような性質を持っているが,LZ77のファクターの数は最少文法の下界となっており,LZ77の方が(理論的な)圧縮性能が高い.

LZ77は現在提案されている圧縮法の中でも特に優秀な部類だと言って良いだろう.よく圧縮できるということは,それだけ入力テキストの性質を捉えることができている見ることも出来る.近年では,LZ77分解を利用した,文字列の規則性を調べる方法も提案されている.具体的には連や,回文,周期性などである.(と論文に書いてあるが,詳しく知らないので自信を持っては言えない.)