圧縮アルゴリズム勉強メモ

2013-08-02 Software Design

ハフマン符号化やランレングス符号化は知ってたけど、じゃあ実際にzip形式とかどうなの？というのが気になったので、少し調べてみた。
まとまりがないけど、自分用まとめ。

データ圧縮の種類

エントロピー符号と辞書式の2種類がある。実際には、両者を組み合わせて使用される。

エントロピー符号

以下のように、データの出現頻度の偏りを利用してデータを圧縮する。

よく登場するデータ列は短いビット列で表現できるようにする
あまり出現しないデータ列は長いビット列で表現できるようにする

具体的には、ハフマン符号化などがある。

辞書式

圧縮するデータ中に、あるデータ列が複数回出現する場合、2回目以降は以前に登場した箇所を参照する方式。
具体的には、ランレングス符号化、LZ77、LZSSなどがある。

Deflateアルゴリズム

LZSSとハフマン符号化を組み合わせたものを、Deflateアルゴリズムと呼ぶ。
一般的に使われる圧縮方式で、zip形式やgzip形式ではこのアルゴリズムが使われている。

ストリーム処理についての考察

「ストリーム処理」という言い方が正しいか分からないけど、要は「入力データ全体が確定していなくても、逐次出力を確定していけるのか」ということが気になっていたので考えてみた。

伸張のストリーム処理について

これはおそらくできる。
というのも、Linuxでgzファイルをlessで開くと伸張の途中でも表示してくれているようなので。

圧縮のストリーム処理について

こちらはおそらく難しい。
気になったのは3点。

1点目はファイルのデータフォーマット。
これは、工夫次第でどうとでもなりそうな気がする。
「入力データ全体が分からないと確定できない情報は、圧縮後のデータ末尾に格納する」ようにすれば、問題ないと思う。
具体的には、圧縮するデータ全体のサイズや、そのCRCなど。
gzipのファイルフォーマットをざっと見た感じ、実際そのようになっているようだ。

2点目はLZSS。
ただしこれも問題なさそう。
LZSSではスライド窓という概念があり、この窓の中でデータに冗長性があるか（あるデータ列が複数回出現するか）をチェックしている。
スライド窓はデータの先頭から順に処理していくため、入力データ全体が確定していなくても処理ができる。¹

3点目はハフマン符号化。
問題があるとしたらここ。
データ列の出現頻度の偏りはデータ全体を見ないと傾向がわからないので。

参考

ただし、窓のサイズが入力データよりも小さければ ↩︎

IT is my life