Deflate圧縮の効率 - 七誌の開発日記

以前、F#でDeflateアルゴリズムの圧縮・展開プログラムを作りました。

http://d.hatena.ne.jp/n7shi/20101004/

先日のZIP実装会 Part.018でよやさんと圧縮についてお話させていただき、ハッシュについて実験していたことを思い出しました。せっかく実験したので記録を残しておきます。

Deflateではデータの前方32KBから一致パターンを探すのですが、原始的にリニアサーチするととんでもなく時間が掛かります。ヒッパルコス星表で実験したところ、1時間以上掛かって23.7MBに圧縮できました（固定ハフマン）。

http://ihepdb.ihep.ac.cn/browsall/heasarc/dbase/dump/heasarc_hipparcos.tdat.gz
※gzを展開したもの（81.2 MB）を圧縮対象としています。

リニアサーチはやめてハッシュを試みました。Deflateでは繰り返しの長さが3バイト以上となっているため、ハッシュのキーも3バイトとしました。適当に作った式で0～4095にハッシュします。ハッシュの範囲が小さいため頻繁に衝突します。そのためハッシュ先をリストにしてデータが失われないようにしています。

let inline getHash (buf:byte[]) pos =
    ((int buf.[pos    ]) <<< 4) ^^^
    ((int buf.[pos + 1]) <<< 2) ^^^
    ( int buf.[pos + 2]       )

以下の3つのアルゴリズムを実装して比較しました。

規格上許される距離（32KB）すべてのデータを保持する。
最初の2バイトが同一のものを排除した上で、規格上許される距離（32KB）すべてのデータを保持する。
最初の2バイトが同一のものを排除した上で、1つのハッシュにつき16のスロットを用意して循環リストとする（4096 * 16 = 65536）。スロットが一巡するとデータが上書きされるため、ほとんど近距離のデータしか保持できない。

私が実装したのは固定ハフマンのみです。先ほどのヒッパルコス星表で実験した結果は以下の通りです。