2016年のOSS圧縮ツール選択カタログ

まだgzipで消耗し（略）
2016年、人類が待ち望んでいた、gzipを圧倒するOSS圧縮ツール[zstd(Zstandard)](http://facebook.github.io/zstd/)がリリースされたにも関わらず、なんかあんまり話題になっていなくて寂しいので、ちょろいかんじの賑やかし比較記事を書きました。圧縮ツールのカタログ的に眺めていただけるかと思います。

# はじめに
## （この記事で言う）圧縮ツールとは何か
圧縮ツールという呼び名は正確ではない（はず）です。平たく言えば、gzipやbzip2、xz、lz4などですが、人によっては、tarの裏側としてしか使ってなくて、聞いたこともないかもしれませんね。そういうときはまず[gzipのmanpage](https://linuxjm.osdn.jp/html/GNU_gzip/man1/zcat.1.html)とか読んでください。
しかし、そういうツールを何と呼べばいいのかわからないので、ここでは圧縮ツールと呼んでいます。

ややこしいですが、**アーカイバ**ではありません。アーカイブとは実態が一つのファイルになっているフォルダと考えればいいのですが、アーカイバはこれを作るソフトウェアです。tarやzipはアーカイバですが、gzipはアーカイバではありません。

**圧縮（ファイル）フォーマット**でもないところがやっかいです。基本的には1ツール1フォーマットなのですが、gzipにおけるzopfliのように別の実装で異なる圧縮率、実行速度を考えることは容易です。**各圧縮ファイルフォーマットにおけるもっとも有力な実装**というのが正しいでしょうか。

## 圧縮率と速度
圧縮率と速度については、あまり厳密ではなく、大半は私見によります。私は普段は主にテキストデータを扱っているので、プログラムファイルや画像のようなデータについてはあまり考慮していませんし、もちろんそれは状況によって異なるので、実際に使用するに当たっては実データで調査した方がよいと思います。

## 性能測定
とは言うものの先立つものがないと想像も難しいので、先に数値から。今回紹介する圧縮ツールたちの簡易測定結果は次のようになります。
たまたま手元にあった、日本語Wikipediaのダンプデータから生成された8Gの本文テキストデータをオンメモリ(tmpfs内)で圧縮/伸長したときのパフォーマンスを測定しました。

公平性を保つために、こういうある程度大きいファイルに対する圧縮だと、高圧縮率を謳うツールが有利になることは明記しておきます。小さいファイルに対する測定は[下のほう](#%E5%AE%9F%E9%9A%9B%E3%81%AB%E3%82%84%E3%81%A3%E3%81%A6%E3%81%BF%E3%81%9F%E7%B5%90%E6%9E%9C)にあります。

```
bash/timeで1回測定 user + sys
CentOS7 Intel Xeon E3-1260L 2.5GHz
# tuned-adm profile latency-performance

# gzip 1.5 / bzip2 1.0.6 / xz　5.1.2alpha / lzo 1.03 / lz4 r131 はyum (centos/baseまたはepel)
# patch-bzip2は1.0.6 + blocksort.c.diff 2008/06/04 をmarch=native付きでビルド
# brotliは2016/10/20時点のもの
# zstdはv1.1.1をmarch=native付きでビルド
# lzturbo 1.2
# zpaq v7.15はデフォルトビルド(デフォルトmarch=native付き)

# 元ファイル由来
# 20161001のjawikiダンプデータを matthewfl/mediawiki-xml2sql で-m出力されたtext.sql
## またはその先頭1Gバイトでの測定データを元にサイズ比で近似値計算
```

元ファイルサイズ 約8.1G (8,493,203K) バイト

|   |圧縮時間(秒)|伸長時間(秒)|圧縮後サイズ(KB)|備考|
|:-:|:-:|:-:|:-:|:-:|
|[**gzip**](#gzipzlib)|581|92.7|2,909,567||
|[**bzip2**](#bzip2)|879|332|2,154,279||
|[**patch-bzip2**](#bzip2)|760|333|2,154,279||
|[**xz**](#xz)|5890|177|1,941,000|近似|
|[**lzo**](#lzoplzo)|43.3|32.1|4,358,309||
|[**lz4**](#lz4)|55.9|10.7|4,303,903||
|[**brotli**](#brotli)|26100|34.9|2,022,000|近似|
|[**zstd**](#zstandardzstd)|102|28.6|2,778,682|デフォルト(-3)|
|[**zstd(-11)**](#zstandardzstd)|530|23.5|2,314,311||
|[**lzturbo(-32)**](#lzturbo)|592|48.3|2,230,301|OSSではない|
|**zpaq(-m4)**|10200|10600|1,535,000|近似|


- 全てシングルスレッド動作です
- zpaqだけはアーカイバでもあります
- snappyはコマンドラインでテストするのが面倒なので省きました
- lzfseは8Gのファイルを食わせたら何かがmallocできなくて即死したので諦めました

# スタンダードな圧縮ツール gzip, bzip2, xz
何をもってスタンダードと言うのか、と怒られそうですが、広く一般に汎用的で使われている圧縮ツールの紹介から。この3つは(GNU)tarや(GNU)lessがネイティブで対応していて、今どきのLinux環境ではほぼデフォルトで入ることが多いでしょう。

```
# tar xvzf compress.tar.gz
# less text.txt.gz
```

## gzip(zlib)
gzip, bzip2, xzの3つの中でもgzip/zlibだけは誰に怒られようともデファクトスタンダードです。tar.gzのgzですし、HTTPのdeflate/gzip転送であり、deflateフォーマットとして見たときにはzipファイル、pngファイル、pdfファイル、swfファイルなど、利用箇所は随一で、圧縮ツール/フォーマットの基本です。

基本というかもう基準のレベルなのでプログラムとしてはgzipの使い勝手をどうこう言うより、gzipと比べてどうかという話になりがちなんですが、あえて他の圧縮ツールと比較すると圧縮速度/伸長速度/圧縮率/使い勝手のバランスが良く、もっとも信頼性のあるツールです。

これまでほとんどシチュエーションを問わず最適な選択になることが多かったのですが、最近になってやっと状況が変わってきました。それでも間違いなく現役の王者です。

- http://www.gzip.org/

### 使い方
```
# gzip testfile.tst
# gzip -d testfile.tst.gz
# tar czf testtar.tar.gz testdir
```

### ファミリー
* [zopfli](https://github.com/google/zopfli)は長い圧縮時間を掛けて、わずかにgzipより高い圧縮率をgzipフォーマット(deflate)で達成するgoogle製のツールです。あくまで`gzip`フォーマットなので、httpでの配信最適化やpngファイル等の最適化で利用されます
* [cloudflare/zlib](https://github.com/cloudflare/zlib)、[intel/zlib](https://github.com/jtkukunas/zlib)、[zlib-ng](https://github.com/Dead2/zlib-ng)はzlibの近代化改修版で、現代的な環境ではより高速に動作します。これも主にhttpでの配信最適化用ですね。なお、gzipコマンドはzlibを使っていない（内包している）ので、gzipの差し替えに使うにはちょっと工夫が必要です
    * どのzlibがどんな特性かを比較した資料が[こちら](https://www.snellman.net/blog/archive/2015-06-05-updated-zlib-benchmarks/)にあります
* マルチスレッド版は`pigz`で、たぶんパッケージシステムにあります

## bzip2
昔は`gzip`より高い圧縮率と言えば`bzip2`でした。今となっては圧縮率と伸長速度で`xz`に負けてしまいましたが、`xz`より圧縮速度が速く、`gzip`より圧縮率が高いという利点があり、ファイルの配布にはいまだによく見かけます。

だいたい`gzip`の2倍以上圧縮が遅いんですが、非公式ながら[こちらの高速化パッチ](http://homepage3.nifty.com/wpage/software/index.html)のおかげで若干速くなって幸せになれます。

`xz`もそうですが、コマンドラインが高いレベルで`gzip`互換なのもいいところですね。

- http://www.bzip.org/

### 使い方
```
# bzip2 testfile.tst
# bzip2 -d testfile.tst.bz2
# tar cjf testtar.tar.bz2 testdir
```

### ファミリー
* マルチスレッド版は`pbzip2`で、たぶんパッケージシステムにあるでしょう

## xz
`xz`は圧縮速度は`gzip`や`bzip2`からすると信じられないぐらい遅いですが、`gzip`の1.5倍から2倍近い圧縮率を達成します。それでいて伸長速度は`bzip2`の2倍、`gzip`の1/2倍ぐらいと、それなりに伸長が速いのがいいところです。今どきのCPUでだいたい1コアで50MB/sぐらいの伸長速度になるので、ちょっと遅いHDDぐらいで、まあ許容できる速度です。（ちょっとずつ進化しているので、最新版を使うともうちょっと速くなったりします）

tar.xz としてよく見かける通り、配布用として徐々にシェアを伸ばしています。そのためかどうかは知らないですが、圧縮率を上げるために特定のCPUの命令バイト列を置換するオプションがあったりします。

現実的な伸長速度で最高圧縮率を求めるなら迷わず選択してよいと思います。`xz`の圧縮率を超えるツールとして[ZPAQ](http://mattmahoney.net/dc/zpaq.html)などもありますが、圧縮率の伸び以上に伸長速度が悪化するので、使いどころは限られるでしょう。

- http://tukaani.org/xz/

### 使い方
```
# xz testfile.tst
# xz -d testfile.tst.xz
# tar cJf testtar.tar.xz testdir
```
### ファミリー
* やっぱりマルチスレッド版の`pxz`が割とパッケージシステムにあるはずです。

# 速度特化型の圧縮ツール lzo, snappy, lz4
`bzip2`や`xz`は参照用にファイルを長期保存するのには向いているんですが、頻繁に圧縮するような用途には向きません。たとえばrsyncの-zやscpの-Cオプションのように、通信経路を透過圧縮するときには、圧縮率よりも圧縮も伸長も通信速度より速いことが期待されます。この目的にはまさにrsyncやscpのようにzlibが使われることが多いのですが、zlibも十分には速いとは言えません。そこで、lzoやsnappy、lz4の出番です。

## lzop(lzo)
古くから存在する高速・低圧縮率の圧縮ツールです。こういった目的でのほぼデファクトスタンダードですね。Linuxカーネルの展開などで使われてきました。`gzip`より10倍近く圧縮速度が速く、伸長も2倍近く速い割にそれなりには圧縮できるのがいいところです。

今でも`lz4`より総じて少し圧縮率がよく、圧縮速度も一線級、展開速度も困らないぐらいには速いので使われることもあります。フォーマットがlzoで、公式ツール名がlzopです。

コマンドラインがだいたい`gzip`互換なのもいいところです。

- https://www.lzop.org/
- http://www.oberhumer.com/opensource/lzo/

### 使い方
```
# lzop testfile.tst
# lzop -d testfile.tst.lzo
```

## snappy
google製でgoogle内で長い間使われており、伸長速度が`lzo`よりずっとはやくGB/s級で、ライセンスも緩い（`lzop`がGPLに対して新BSD）と言うことで盛り上がった圧縮ライブラリです。

しかし割と直後に`lz4`が有名になり、圧縮速度/伸長速度/圧縮率のすべてでおおよそ`lz4`に負けていて、微妙な位置づけになってしまいました。透過圧縮格納ブームの火付け役としての存在は大きく、未だによく組み込まれているのを見かけますが、新規に使う理由はまったくないと思います。

あとライブラリしかないので、若干使い勝手が悪いです。（出た当時に野良コマンドラインツールはいくつかあったように記憶していたんですが、今回見つけられず、測定していません）

- https://github.com/google/snappy

## lz4
もはやこの分野のデファクトスタンダードです。展開速度が`snappy`より2倍近いのに、圧縮速度・圧縮率も`lzo`並みと、もうこの分野はこれ一つでいいんじゃないかと思います。今ではlz4を知っていても、`lzo`とか`snappy`を聞いたこともないという人もいるでしょう。いろんなオープンソースでも使われています。

プログラムから使う他にも、私はよくネットワークを挟んでddするときに使っていたりします。`gzip`では100Mbpsぐらいからデータを選ばないと逆効果になったりしますが、lz4だと1Gbpsでもオーバーヘッドなしで挟めます。

- http://lz4.github.io/lz4/

### 使い方
やっぱり`gzip`になんとなく似たコマンドラインですが、奥ゆかしく、処理が完了しても元のファイルは消しません。ディスクがボトルネックになって圧縮速度を活かしきれない感があるので、あんまりファイル圧縮に使うことはないのですが、うっかり消し忘れないようにしましょう。

```
# lz4 testfile.tst
# lz4 -d testfile.tst.lz4
```

### 送受信に挟んでみる
nc（netcat）と組み合わせてどうぞ。

```
## 送信
# dd if=/dev/vda | lz4 -c | nc 192.168.0.2 4444

## 受信(192.168.0.2)
# nc -l 4444 | lz4 -cd | dd of=/dev/vdb
```
`lzo`/`snappy`/`lz4`の速度比較は[lz4のgithub](https://github.com/lz4/lz4)を見ていただくのが一番です。


# 次世代型の圧縮ツール brotli, lzfse, zstd
圧縮ツールの世界では長らく`zlib`より圧縮率を上げることと、`zlib`より速度を上げることは排他でした。これはアルゴリズム上の限界と、`zlib`が割とかなり最適化されていたところが大きいのですが、なんにせよ`zlib`はトレードオフの一つの頂点なのでした。最近になってやっとそれが崩されたのは大きなニーズ(`brotli`)とFSEと呼ばれる[アルゴリズム](https://arxiv.org/abs/1311.2540)の進化(`lzfse`,`zstd`)、実装技術の発展によるものだと言えるでしょう。

## brotli
google製で`zlib`に代わる「[インターネット用の新しい圧縮アルゴリズム](https://googledevjp.blogspot.jp/2015/11/brotli.html)」です。主目的はhttp（ただしSSLが必要）の経路圧縮用です。いきなりChromeとFirefoxに積まれ、nginxのモジュールも出ているので、強引ながら一定のシェアが見込まれます。`zlib`より圧縮速度は（かなり）遅いものの、展開速度は同じぐらいかちょっと速いぐらいで、圧縮率は`zlib`/`bzip2`より良いと、単品で見るとよいツールになりそうですが、`zlib`代替という意味で考えると、おおよその使い勝手は`zstd`に負けているので、個人的には`snappy`の末路が頭をよぎり心配になります。
ただし、小さいファイルに対する圧縮率は`xz`をもしのぐので、当面のインターネット用のアルゴリズムとしては最適であることには間違いありません。

- https://github.com/google/brotli
- [公式nginxモジュール](https://github.com/google/ngx_brotli)
- [Qiita:Google製の新しい圧縮アルゴリズム Brotli を軽く使ってみた](http://qiita.com/isaoshimizu/items/28cdc0d08c1bdb7ab6c1)

### 使い方
コマンドラインツールとしてはあまり使い勝手はいいとは言えません。

```
# bro --input testfile.tst --output testfile.tst.br
# bro --decompress --input testfile.tst.br --output testfile.tst
```

### インターネットで
インターネット上というかhttps上で動的データ配信時にbrotliとzlibをどう使い分けるかは[こちら](https://blog.cloudflare.com/results-experimenting-brotli/)によいレポートがありました。
しかし、brotli単体で試した限りだと、うかつに動的に使うとパフォーマンスがあっという間に劣化しそうなので、一般的にはせいぜい静的配信用のnginx/brotli_staticだけで十分なんじゃないか、という気がしないでもないです。

* [Qiita:新しい圧縮アルゴリズムBrotliをnginxで試す](http://qiita.com/cubicdaiya/items/cfe9ed403d286b8a9ab1)
* https://github.com/cloudflare/ngx_brotli_module


## lzfse
Apple製で、OSXに積まれているようです。mac上はこれでもいいんじゃないでしょうか。他でも使えるかと言うと微妙だと思います。覇権を握るには`brotli`と`zstd`に挟まれてあまりいいところがありません。
今回、一応試しておこうとしたらいきなり落ちたので、ツールとしての完成度もまだ微妙な気がしてきました。

* https://github.com/lzfse/lzfse
* [Apple、新しい圧縮アルゴリズムLZFSEをオープンソース化](https://www.infoq.com/jp/news/2016/07/apple-lzfse-lossless-opensource)
* [最強の圧縮アルゴリズム ZStandard を試す](http://hidekatsu-izuno.hatenablog.com/entry/2016/09/09/214350)

## Zstandard(zstd)
`lz4`を開発した[Yann Collet氏](https://github.com/Cyan4973)の新しい圧縮ツールです。気が付くと1.0がリリースされたと同時に[facebook/zstd](https://github.com/facebook/zstd)になりました。`gzip`/`zlib`より圧縮速度/伸長速度/圧縮率でおおよそ上回ることができ、また`zlib`以外のこれまでの圧縮ツールがあまりサポートしてくれていなかったプリセット辞書も持て、なんと作成機能まであるので、ポスト`zlib`としての最有力候補です。

ツールとしては圧縮レベル指定が1から21まであって、使い倒そうとするとちょっと戸惑うかもしれません。レベルは-3から-5あたりが`gzip`の-6と同じぐらいの圧縮率で快速、-11あたりが`gzip`の-6と同じぐらいの時間で高圧縮率になります。
圧縮アルゴリズムの常ですが、それ以上になると圧縮速度が悪化する割には、圧縮率はそれほどよくはなりません。最大圧縮率や最大圧縮率近くでの速度では、`bzip2`の方がよいでしょう。ただし、伸長速度は圧倒的にzstdです。

[facebookからリリース](http://jp.techcrunch.com/2016/09/01/20160831facebook-open-sources-zstandard-compression-algorithm-and-myrocks-storage-engine/)と言われると実際そうでもなんか微妙な気持ち（1.0まではYann氏の個人リポジトリだったので）ですが、なにげにfacebookで実績を積んでるという文言はありがたいですね。1.0未満の開発中時代のフォーマットを切り捨てることなくサポートしてきた姿勢も尊いので、本当にstandardになってほしいツールです。

- http://facebook.github.io/zstd/

### 使い方
--rmを付けておくと、`gzip`と同じように圧縮成功時に元ファイルを消してくれます。

```
# zstd --rm testfile.tst
# zstd --rm -d testfile.tst.zst
```

# おまけ
## lzturbo
[lzturbo](https://sites.google.com/site/powturbo/home)はクローズドソースですが、公式でworld's fastestを名乗るとおり、おおむね最速で動作します。早い段階でFSEを実装し、（lzturboの実装上の工夫はあるにせよ）FSEを高速なアルゴリズムとして世に広め、ベンチマークで競う環境を作った立役者だと考えられるので、紹介しておきます。

* [benchmark](https://sites.google.com/site/powturbo/home/benchmark)(結果)
* https://github.com/powturbo/TurboBench

## プリセット辞書(preset dictionary)について
そういえば超便利なのによくわからない扱いされることが多いので、解説しておきます。`zlib`や`zstd`にはこの機能があります。`gzip`にはありません。`gzip`から使えないのが弱点でしたが、`zstd`はコマンドラインから使える上に、`zstd`はコマンドラインで生成することすらできます。

たとえば、メールのような小さいファイルを大量に圧縮することを考えてみてください。一般的に、そういったファイルを個別に圧縮すると、tarで固めてから圧縮するよりも圧縮率は悪くなります。これは、ファイル間には共通文字列がそれなりにあるものの、ファイル内には共通文字列があまり存在しないためです。
そこで、あらかじめファイル間の共通文字列がわかっていれば、それを取り出しておいて、圧縮時に(スライド)辞書の初期値として利用できれば圧縮率を上げることができるわけです。これが、プリセット辞書と呼ばれるものです。

もちろん伸長時にもその辞書が必要になるため用途は限られますが、B-Treeのページ圧縮やVPNのような、あらかじめ辞書を作っておいて交換できる用途で圧縮率を改善することができます。

辞書を作るのは、ファイル間の共通文字列を取り出すことで行うことができますが、最適な辞書を作るのは意外に難しい問題です。(といいつつも、適当に1ファイルを辞書として使っても通常は圧縮率が改善できます）`zstd`はこの機能を内包しているので、一度試してみてはいかがでしょうか。

`zlib`では[このようなツール](https://github.com/vkrasnov/dictator)があります。

* [English] [Improving compression with a preset DEFLATE dictionary](https://blog.cloudflare.com/improving-compression-with-preset-deflate-dictionary/)

### 実際にやってみた結果
今回実験に使ったファイルの先頭1GBをさらに16KB単位でsplitして65536個のファイルを用意してみました。個別に圧縮した結果と、共通辞書を1つ用意して実行した（`zstd`のみ）のが次の結果です。

```
## 分割
# mkdir testdir; cd testdir
# cat ~/testfile.1GB.tst | split -b 16K

## 辞書作成
# zstd --train testdir/* -o ~/testdata.dic
## 辞書サイズは112640バイトでした（zstdデフォルトサイズ）

## 辞書付き圧縮/伸長
# zstd -D ~/testdata.dic --rm testdir/*
# zstd -D ~/testdata.dic -d --rm testdir/*.zst
```

元ファイル 16KB x 65536個 (総サイズ1GB = 1,048,576 KB)

|   |圧縮後総サイズ(KB)|辞書付き圧縮後総サイズ(KB)|
|:-:|:-:|:-:|
|**gzip**|419,303|-|
|**bzip2**|374,288|-|
|**xz**|390,411|-|
|**lzo**|581,879|-|
|**lz4**|590,271|-|
|**brotli**|368,486|-|
|**zstd**|450,733|397,788|
|**zstd(11)**|435,319|359,915|
|**lzturbo(32)**|485,579|-|


- zpaqは面倒なので省きました
- ちなみにlzturboはこういう処理はだいぶ苦手で、極端に遅くなります
- 新しめのツールはbrotli以外ファイルヘッダが大きそうですね
    - 逆に言うと、gzip/bzip2はまさに汎用と言えるさすがの性能です

# おわり
本記事が圧縮ツール/アルゴリズム選択の一助となれば幸いです。