以前、F#でDeflateアルゴリズムの圧縮・展開プログラムを作りました。
先日のZIP実装会 Part.018でよやさんと圧縮についてお話させていただき、ハッシュについて実験していたことを思い出しました。せっかく実験したので記録を残しておきます。
Deflateではデータの前方32KBから一致パターンを探すのですが、原始的にリニアサーチするととんでもなく時間が掛かります。ヒッパルコス星表で実験したところ、1時間以上掛かって23.7MBに圧縮できました（固定ハフマン）。
リニアサーチはやめてハッシュを試みました。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）。スロットが一巡するとデータが上書きされるため、ほとんど近距離のデータしか保持できない。
私が実装したのは固定ハフマンのみです。先ほどのヒッパルコス星表で実験した結果は以下の通りです。
- 7分15秒 23.7MB
- 57秒 24.8MB
- 35秒 27.9MB
【追記】更に高速化しました ⇒ http://7shi.hateblo.jp/entry/2012/04/18/011748
1は時間が掛かる割に圧縮率はあまり向上していません。ヒッパルコス星表に限れば2で十分のようです。ちなみに1はリニアサーチによる圧縮と出力が完全に一致して、固定ハフマンによる理論上最高値だと思われます。遅すぎて実用には耐えないレベルですが、それでもリニアサーチよりかなりましです。
比較として7zipで動的ハフマン圧縮してみました。
- ZIP形式(Deflate) 標準圧縮: 31秒 16.8MB
- ZIP形式(Deflate) 超圧縮: 3分54秒 16.6MB
固定ハフマンの限界をあっさり超えています。超圧縮がどういう風にアルゴリズムを変えているのかは調べていませんが、時間が掛かる割にあまり圧縮率は向上していないので、この辺がDeflateの限界のようです。ヒッパルコス星表のデータに限って言えば、標準圧縮の方がコストパフォーマンスが良いです。
なお、参考までに別アルゴリズムですがLZMAの結果も載せておきます。
- 7z形式(LZMA) 標準圧縮: 1分27秒 13.6MB
一応フォローしておくと、LZMAは圧縮は重めですが展開は高速です。
