GoogleがZopfliという新しい圧縮アルゴリズムを開発していたことをたまたま知りましたが、仕組み的にも興味深いものでした。
「新しい」圧縮アルゴリズム
2013年2月、Google社が新しい圧縮アルゴリズムを発表しました。gzipと比較して、圧縮率は3〜8%程度向上するものの、圧縮時間は数十倍かかることもある、とのことでした。
gzipの圧縮率を上回るような圧縮形式も、7z、bzip2、xzと出ている中で、この程度の改善では、さして魅力がないように映るかもしれません。
deflate互換、の意味
ただし、Zopfliには大きな特徴があります。それは、「解凍がDeflateで行える」ということです。Deflateは実装がzlibとして普及していることもあり、
- gzip
- PNG
- ZIP
など、各種の形式の圧縮アルゴリズムとして採用されています。つまり、Zopfliでこれらのデータを、互換性を保ったままさらに小さくできる、ということになります。Webの世界でも、画像に使われるPNGや、HTTPでのgzip転送などDeflateを使う場面が多くありますので、従来のエコシステムを何も変えず、データだけ小さくできることになります。
なお、そのような性質上、解凍時間はふつうのDeflateとほぼ同じです。
どうしてそんなことができるの？
まず、通常のgzipにも圧縮率オプションがあって、サイズの違う圧縮ファイルができることからもわかるように、同じファイルに復元できる圧縮ファイルは何通りも存在します。
Deflateの中で使われている「LZSS」というアルゴリズムは、今までに出てきたのと同じデータが出てきた時に、それを「あった位置、長さ」のペアに置き換えることで圧縮を行います。これを探すための戦略のとり方で圧縮効率が違ってくるわけですが、通常のDeflateではほどほどな方法ですぐ終わらせてしまうのに対して、Zopfliでは何度も何度も同じファイルを処理して、より効率のいい変換を探す、という方法で高圧縮を目指します。
高圧縮の代償
上で書いたように、何度も何度も処理を続けるので、時間はかかってしまいます。コマンドラインツールでは、何回処理を行うか引数で指定できるようになっていますが、1000回回すと時間が相当にかかってしまいます。15回程度でもかなり圧縮率が改善しますので、どうしても1バイトが惜しい場面以外ではその程度で充分でしょう。
また、処理負荷を考えるとサーバサイドプログラムの動的な出力をgzip転送する、という用途にも向きません。Webでは、事前に圧縮可能な静的ファイルや、そうそう変化しないPNGファイルなどが使用場面となるでしょう。