« September 2008 | Main | November 2008 »

2008.10.22

LZ法再び

可逆データ圧縮としてはgzipやlha, pngなどダントツで使われているLZ法(Lemple Ziv法)ですが、他のデータ圧縮法(BWT法、PPM法、CM法)に比べ圧縮率が低いということで研究の対象としてはあまり注目をあびていませんでした。ところが次の論文で真面目にやれば圧縮率は非常に高くなる可能性があり、BWT法とかそれを超える可能性があることが示されています。。

"On the bit-complexity of Lempel-Ziv compression", SODA 2009, P. Ferragina, et. al. [pdf]

まず、LZ法についておさらいですが、基本的にはデータを前から順番に見ていったときに、既に出現した文字列がもう一度出現(マッチング)したら、その文字列を前回出現した(相対)位置と長さのペア(pos, len)で置き換えることで圧縮する方法です。データには大抵繰り返しが多く出現するので、保存サイズを減らすことができます。例えば、abracadabraという文字列はabr(3,1)c(2,1)d(7,4)となります。(3,1)は3文字前から1文字コピーするという意味で、初めて出現する文字をそのまま書いています。
これは厳密にはLZSS法といわれるもので他にもたくさん変種がありますが基本的にはこのアイディアに基づいています。

この入力文字列を以前出現した文字に置き換えていく作業は部分文字列に分解するようにみえるので、lz-factorizationと最近では呼んだりします。先ほどのは abr a c a d abraとなります(圧縮以外にもパターンマイニングなどいろいろな利用用途があることが分かっている)

現在のlz法の殆どの実装では、以前出現したかどうかを調べる部分を近似的に行っています。近似的というのは、一つは長い文字列は見つけようとはするが、必ずしも最長一致を見つけていないということ、もう一つは同じ一致長のマッチングの中でも一番近い最右のものを見つけていないことです。近いマッチングを見つけることができれば一致情報を表すのに小さい数字を使えばよく、必要な符号長を減らすことができます。

現在のlz法の実装は大抵、数文字使ったハッシュを利用してマッチングの候補を見つけ、そこから伸ばしていくか、今まで見た文脈を適当に間引いてtrieを作って探索しているかです。まじめに最長&最右一致を探そうとすると、単純な実装では計算量は爆発します。

さらに、マッチングを探す場合に過去の文脈全てを見ると計算量+作業領域量が大きくなるので決められた範囲内だけ(たとえば現在の位置から64KBだけからとか)からしかマッチングを調べないようになってます。

上記の論文でまず示したのは、上の三つの近似を取っ払って真面目に最長&最右一致を全過去の文脈から探すと圧縮率は非常に高くなる、たとえばbwt法の最高の符号法の一つとほぼ同じところまで圧縮率が向上することです。lz法はbwt法やppm法と違って復元が(1)めちゃくちゃ速い (2)必要なメモリ量は文脈の分だけ (3)前から順番に復元できる(stream復元, ppmもできるが)という三つの特徴を持ってるため、圧縮率がほぼ同じところにいけば、実用的にはかなり美味しくなります。

上記の論文ではさらに最適なparsingを求めることが現実的な計算量で求められることを示しています。例えば、上のparsingはgreedyな戦略、つまり毎回最長一致を探して置き換えていきますが、数文字スキップしたらもっと長いマッチングがあって全体は小さくできるかもしれません。この全体のサイズを小さくするようなparsingを求める問題は、重み付きDAGの最小重みパスを求める問題に帰着できるのは知られていますが、このDAGをほぼ線形もしくはO(nlogn)time, spaceで求められることを示しています。この最適なparsingを使うことで先ほどの最長&最右一致よりも更に数%圧縮率を向上させることができます(詳しい数値は論文を参照してください)

で、少なくとも最長、最右一致が効率的に求められるだけでも嬉しいのですが、これだけでもかなり手ごわい問題です。メモリさえ許せばsuffix treeなどを構築してマッチングを求めれば最長、最右一致はほぼ線形時間で求まりますが、全履歴、少なくとも100MB分ぐらいはみたいということでメモリ量がかなりシビアです。

この問題はまさに私が先日発表した手法で解けそうなのですが、いくつかまだ壁があるところで、時間を見つけてはちまちまやってます。

# データ圧縮では最近ずっとpaqが強いです。ここのサイトでは圧縮率だけではなく速度に特化したものとかいろいろあっておもしろいです。圧縮率の向上は日進月歩maximum compression.
 ただ、ここまでくるとテストセットに過適応しているようなきもする

| | Comments (149) | TrackBack (0)

« September 2008 | Main | November 2008 »