圧縮アルゴリズムZopfliとBrotli

(2017-11-03)

どちらもGoogleが開発した圧縮アルゴリズム。

puppetter-lambda-starter-kitissueに 現在使っているgzipと、Zopfli、Brotliを比較したデータが上がっていたので調べてみた。

Zopfli

出力としてDeflateに対応している。

Deflate

LZ77(実際は改良版のLZSS)とハフマン記号による可逆圧縮アルゴリズム。 zip、zlib、gzip、pngなどで使われていて、これらはヘッダーやフッターが異なる。 LZSSはバイト列を見ていって同じ部分を発見したらそこを参照するように置き換えていく。

a b c a b c a b c d d d
=> a b c (距離3, 長さ6) d (距離1, 長さ2)

このLZSSにあたる部分をZopfliはがんばってやるので圧縮時間が結構かかるがサイズは小さくなるらしい。 展開は通常のDeflate通り。上げてくれたデータを見ても大体そんな感じだ。

Brotli

LZ77、ハフマン記号に加えて2nd order context modelingというのを使って圧縮する Deflateではない可逆圧縮アルゴリズム。 Safari以外のモダンなブラウザで既に対応しているか対応しているところ。 対応している場合、Accept-EncodingContent-Encodingヘッダに含まれるのはbr。 圧縮率も展開時間もかなり良さそう。

Nodeにもblotliのライブラリがあって、 圧縮はEmscriptenで本家のC++コードから変換し、 展開は手で移植しているようだ。

$ npm install blotli
const fs = require('fs');
const brotli = require('brotli');
const TARGET = process.env.TARGET;
const MODE = process.env.MODE;

const compress = () => {
  const target = fs.readFileSync(TARGET);
  const compressed = brotli.compress(target, {
    quality: 11,
  });
  fs.writeFileSync(`${TARGET}.br`, compressed);
};

const decompress = () => {
  const target = fs.readFileSync(TARGET);
  const decompressed = brotli.decompress(target);
  fs.writeFileSync(`${TARGET.replace('.br', '')}`, decompressed);
};

(async () => {
    if (MODE === 'decompress') {
        decompress();
    } else {
        compress();
    }
})();

ただ、これで大きなファイルを圧縮しようとすると以下のようなエラーが出て失敗する。 設定を変えてコンパイルするのも面倒なので、圧縮はCLIでやることにした。

$ TARGET=headless_shell node compress.js 
Cannot enlarge memory arrays. Either (1) compile with  -s TOTAL_MEMORY=X  with X higher than the current value 318767104, (2) compile with  -s ALLOW_MEMORY_GROWTH=1  which adjusts the size at runtime but prevents some optimizations, (3) set Module.TOTAL_MEMORY to a higher value before the program runs, or if you want malloc to return NULL (0) instead of this abort, compile with  -s ABORTING_MALLOC=0 

リポジトリをcloneしてきてmake installする。

$ git clone https://github.com/google/brotli.git
$ mkdir out && cd out
$ ../configure-cmake
$ make
$ make test
$ make install
$ brotli --version
brotli 1.0.1

デフォルトで最高レベル(11)で圧縮することもあり、かなり時間がかかる。

$ time brotli headless_shell
$ time brotli headless_shell

real	18m41.814s
user	18m6.485s
sys	0m7.906s

gzipだと最高レベルで圧縮しても43MBまでのところ、33MBまで圧縮できた。

131M headless_shell
33M  headless_shell.br

展開はすぐ。むしろgzipより速い。

$ time TARGET=aaaa.br MODE=decompress node compress.js

real	0m5.850s
user	0m4.626s
sys	0m1.030s

対応版を出そうとしたけど謎のエラーがすぐに解決できなかったので後でやる。

参考

Deflate

Zopfliで高圧縮gzip・PNGほか - Qiita