Googleの新しい圧縮アルゴリズムZopfliについて調べた。

計算機科学

Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。

Compress data more densely with Zopfli - Google Developers Blog


deflateアルゴリズム
zopfliはdeflateアルゴリズムに基づいた圧縮ライブラリ。deflateアルゴリズムはデータをLZSSというLZ77を改良した圧縮法で圧縮し、その後ハフマン符号で符号化したもの。
deflateアルゴリズムの実装としてはzlibやgzipがある。zlibとgzipの違いはヘッダとフッタの持っている情報。


使ってみる
googlecode(http://code.google.com/p/zopfli/)から取ってくる。

$$ git clone https://code.google.com/p/zopfli/
$$ cd zopfli
$$ make
$$ ./zopfli README 
$$ ll README*
-rw-r--r-- 1 echizen_tm staff 1052  3  2 00:51 README
-rw-r--r-- 1 echizen_tm staff  487  3  2 23:53 README.gz

zopfliは出力の形式としてdeflateそのまま、zlib、gzipの3形式を選択できる。デフォルトはgzip形式なので普通にgunzipで解凍できる。

$$ gunzip -c README.gz > README2
$$ ll README*
-rw-r--r-- 1 echizen_tm staff 1052  3  2 00:51 README
-rw-r--r-- 1 echizen_tm staff  487  3  2 23:53 README.gz
-rw-r--r-- 1 echizen_tm staff 1052  3  2 23:57 README2


性能について
Google Developers Blog(記事冒頭のリンク)によると普通のzlibに対して3-8%小さくなるかわりに圧縮時間は2-3桁大きくなるとのこと。圧縮に時間がかかるのは最適な符号化を探しているからで解凍にかかる時間はかわらない。なので更新が少ないコンテンツの圧縮に向いている。
論文(https://zopfli.googlecode.com/files/Data_compression_using_Zopfli.pdf)に他のdeflateアルゴリズムの実装と比較が書いてある。これは確かに遅い。というかgzipが速いのか。


アルゴリズムについて
上記論文にはアルゴリズムのことが詳しく書いてなかったのでソースコードを眺めた。ソースコードはC++・・・ではなくC。mozcのLOUDSのコードを読んだ時もCだったし私の中でgoogle=Cというイメージが出来上がりつつある。気になったのはsqueeze.c、blocksplitter.c、katajainen.cあたり。deflateアルゴリズムの実装には詳しくないのでzopfli独自のアイデアなのか他の実装でもやられてるのかはよくわかってない。


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


blocksplitter.c
データ全体で文字(と便宜上置いておく)の分布が同じとは限らない。なのでデータをブロックに分割してブロックごとにハフマン符号化することで圧縮率を上げている。この最適なブロックをblocksplitterで決定してるっぽい。


katajainen.c
ハフマン符号化する際に符号長がある長さより長くならないように符号化するminimum-redundancy length-limited prefix codeというのを用いている。@komiya_atsushiさんのツイート(https://twitter.com/komiya_atsushi/status/307326818879430656)で論文が紹介されている。


以上。調べたことをメモした。それにしてもzopfliってなんて読むんだろう。