Deflateの固定ハフマンに限る

昨日、SPIフラッシュからのプログラムロードが遅いかも。

という話で圧縮というのも考えるのかもしれないと書いたが、

簡単な圧縮方法はないものかと調べたら、Deflateに条件を付ければ簡単そう。

その条件とは固定ハフマンである。


Deflateと言えばZIPやらGZIPやらの圧縮アルゴリズムとして使われている。

圧縮性能はそれなりによいので、面倒そうだなと思う。

実際、けっこう面倒そうなのだが、意外とそうでもない部分もある。

7shi/Deflate (Slideshare)

Deflateはハフマン符号化とLZの2つのアルゴリズムを組み合わせている。

LZというのは繰り返しを表現するもので、

1~32768byte前に3~258byteの一致があることを0x101~0x11Dの符号で表す。

そういう都合のよい一致がない場合は0x00~0xFFで1byteのデータ、

そして最後は0x100の符号で終わるという仕組みである。

で、これ見てもわかるのだけど、0x00~0x11Dの285種類の符号を使う。

中途半端な気がするが、それで問題ないのはその後にハフマン符号化があるからで、

発生頻度の高い物は短い符号長、低いものは長い符号長を割りあてる。

これにより効果的な圧縮ができるわけである。


ただ、短いデータの圧縮だと、符号の定義でサイズが大きくなってしまう。

そこで固定ハフマン符号ということで既定の符号が存在している。

0x00~0x11Dを7~9bitの可変長の符号で表すというもの。

ある程度発生頻度は考慮されているらしい。

これを使う前提ならばハフマン符号の解析はある程度決め打ちでできる。

固定ハフマンを使って圧縮するというのはPythonでこんな風にかける。

import zlib
zc=zlib.compressobj(strategy=zlib.Z_FIXED)
ifile=open('c:/work/input.bin','rb')
idata=ifile.read()
ifile.close()
ofile=open('c:/work/deflated.bin','wb')
ofile.write(zc.compress(idata))
ofile.write(zc.flush())
ofile.close()

コンソールで殴り書きしたのをコピペしただけなのでご勘弁を。

ポイントはstrategy=zlib.Z_FIXEDってところで、これで固定ハフマンを使うことを表している。

1079kBのCSVを圧縮して254kB、本気で圧縮して206kBだから、

確かに劣るけど、これはこれで悪くない数字ではないかと思う。


固定ハフマンに限れば解析は容易になりそうだが、

ちょっと面倒なのは可変長符号の都合、下位ビットがMSBになっていること。

愚直に1bitずつコピーしてシフトして処理しては展開に時間がかかりそうだし

あらかじめ固定ハフマンを解析する用のテーブルでも作っておくのがよいのだろうか?

ただ、あらかじめ用意したテーブルを使えるのは固定ハフマンのメリットではないか。


圧縮に既存のツールが使えるなら少し助かった気がする。

展開側は書かないといけないのかもしれないけど、

まぁ実現性はありそうだなと思った。

やりたくはないけど、結構厳しそう。