Zopfli - naoyaのはてなダイアリー

Googleが今日（米国時間2/28）、オープンソースの新しい圧縮アルゴリズムZopfliをローンチした。今の標準圧縮技術であるzlibライブラリに比べて5〜8%圧縮率が高いといわれ、また解凍アルゴリズムは今のWebブラウザが現用しているもので間に合うため、Webサーバがこれを採用すれば、データの伝送速度が上がり、Webをやや速くすることができるだろう。

Google が出力が deflate 互換の圧縮アルゴリズムをオープンソースにしたというので、ちょっとタイムラインで話題になっていた。圧縮アルゴリズム周りにはまってた頃から結構時間が経ってしまって色々忘れてしまったけど、少しニュースを捕捉してみようと思う。

Zopfli は deflate 互換なので、deflate アルゴリズムを解釈できる実装なら伸張できる。当然ブラウザが持ってる deflate 実装で伸張できるので、エンドユーザーは通信路を流れるデータが圧縮されているかどうかを気にせず Zopfli 圧縮されたコンテンツを受け取ることができる。

deflate の互換だけれども Zopfli で圧縮したものは zlib や gzip なんかで圧縮したものよりもう少し小さくなる。その代わり圧縮の計算コストが大きい。つまり圧縮に時間がかかって、伸張はほぼいっしょ。で、サイズが小さい。

圧縮アルゴリズムにはいろいろな物があるけど、deflate は圧縮伸張ともにコストが小さめでバランスが良いので汎用性があり、ウェブサーバーやブラウザなんかに採用されるに至っている。そのかわり圧縮サイズもそこそこ。

一方、この手の圧縮側の計算コストを結構上げてしまって圧縮サイズをもっと小さくなるように頑張っちゃおうという類もある。代表的なものが Linux カーネルのソースコードアーカイブの圧縮なんかに使われている LZMA。(いま kernel.org の ftp 見たら最近使われてない? よくわからない) LZMA は 7-zip というツールなんかに実装されている。LZMA は圧縮にかなり計算コストがかかるがサイズは小さいし伸張は速い。なのでソースコードのように、一度圧縮してしまったらそれを配布すれば良いだけ、みたいな対象にとても向いている。当然、毎回内容が変わって都度圧縮しなければいけない動的コンテンツには向かない。

Zopfli も考え方としてはそれに近い。ただ、LZMA の出力は Deflate と互換性がないのに対して Zopfli の出力にはある。なので既存の Deflate アルゴリズムを解釈できる実装なら、そのまま Zopfli を伸張できるということころがウリ。

従って、例えば静的ドキュメントだけどブラウザで直接表示してもらいたいようなコンテンツを配布する場合なんかに Zopfli は使えるということだと思う。また、圧縮コストが高いといっても論文を見る限りそこまででもないので、キャッシュできるようなものなら静的なものでなくても適用できる場合もあるだろう。

https://zopfli.googlecode.com/files/Data_compression_using_Zopfli.pdf

この論文では幾つかのコーパスを対象に gzip -9、7-zip、kzip、Zopfli と Deflate 互換のアルゴリズムを比較しているけど、Zopfli はそのいずれよりもサイズが小さくなっている。とはいえそんな劇的なものではないので Techcrunch でも「やや速くする」と控えめな表現になっているんだと思う。しかし、たかが 5 〜 8% でも Google くらいの規模になると全体としては相当な転送量、I/O そのほかの軽減になるので十分意味がある。

Zopfli 自体がどうやってその圧縮率を達成しているかは、ちょっと調べただけだとよくわからなかった。WebP の画像圧縮からインスパイアされたとか、TechCrunch にある "Vandevenneは今日の発表声明で、“この徹底的で容赦のない圧縮アルゴリズムは、エントロピーモデルの反復と最短経路アルゴリズムを駆使し、可能なすべてのデフレート表現のグラフ中にビットコストの低い経路を見つける”、と述べている。" という記述くらいかな。Deflate の詳細もだいぶ記憶があやふやなのだけど、ざっくりいうと圧縮に使う辞書か木かわからないけれどもその構成を最適化問題として捉えて、最短経路発見によって最適化するってことなんじゃないかなーと推測します。そこの部分に計算コストを多めにとって精度を上げてやっている･･･と。

追記

前述のとおりdeflateアルゴリズムはLZSSの後にハフマン符号化する。LZSSは部分文字列が既出の場合はその位置と長さに置き換えることで圧縮する。この部分文字列をどのくらいの長さに取ればよいかというのが問題で、後にハフマン符号化するのでグリーディに最長部分文字列をとらないほうが結果的に圧縮率が高い可能性がある。
これを解決するために最初にグリーディに最長一致でLZSSをしてハフマン符号化して、その符号に合わせた部分文字列長でLZSSしてハフマン符号化して、というようにLZSSとハフマン符号化を繰り返すことで最適な符号に収束するようにしているみたい。

なるほどなるほど。