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

はじめに

（この記事で言う）圧縮ツールとは何か

圧縮ツールという呼び名は正確ではない（はず）です。平たく言えば、gzipやbzip2、xz、lz4などですが、人によっては、tarの裏側としてしか使ってなくて、聞いたこともないかもしれませんね。そういうときはまずgzipのmanpageとか読んでください。
しかし、そういうツールを何と呼べばいいのかわからないので、ここでは圧縮ツールと呼んでいます。

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

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

圧縮率と速度

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

性能測定

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

公平性を保つために、こういうある程度大きいファイルに対する圧縮だと、高圧縮率を謳うツールが有利になることは明記しておきます。小さいファイルに対する測定は下のほうにあります。

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	581	92.7	2,909,567
bzip2	879	332	2,154,279
patch-bzip2	760	333	2,154,279
xz	5890	177	1,941,000	近似
lzo	43.3	32.1	4,358,309
lz4	55.9	10.7	4,303,903
brotli	26100	34.9	2,022,000	近似
zstd	102	28.6	2,778,682	デフォルト(-3)
zstd(-11)	530	23.5	2,314,311
lzturbo(-32)	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は長い圧縮時間を掛けて、わずかにgzipより高い圧縮率をgzipフォーマット(deflate)で達成するgoogle製のツールです。あくまでgzipフォーマットなので、httpでの配信最適化やpngファイル等の最適化で利用されます
cloudflare/zlib、intel/zlib、zlib-ngはzlibの近代化改修版で、現代的な環境ではより高速に動作します。これも主にhttpでの配信最適化用ですね。なお、gzipコマンドはzlibを使っていない（内包している）ので、gzipの差し替えに使うにはちょっと工夫が必要です
- どのzlibがどんな特性かを比較した資料がこちらにあります
マルチスレッド版はpigzで、たぶんパッケージシステムにあります

bzip2

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

だいたいgzipの2倍以上圧縮が遅いんですが、非公式ながらこちらの高速化パッチのおかげで若干速くなって幸せになれます。

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://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互換なのもいいところです。

使い方

# 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を見ていただくのが一番です。

次世代型の圧縮ツール brotli, lzfse, zstd

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

brotli

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

使い方

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

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

インターネットで

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

lzfse

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

Zstandard(zstd)

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

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

facebookからリリースと言われると実際そうでもなんか微妙な気持ち（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はクローズドソースですが、公式でworld's fastestを名乗るとおり、おおむね最速で動作します。早い段階でFSEを実装し、（lzturboの実装上の工夫はあるにせよ）FSEを高速なアルゴリズムとして世に広め、ベンチマークで競う環境を作った立役者だと考えられるので、紹介しておきます。

benchmark(結果)
https://github.com/powturbo/TurboBench

プリセット辞書(preset dictionary)について

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

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

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

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

zlibではこのようなツールがあります。

[English] Improving compression with a 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はまさに汎用と言えるさすがの性能です

おわり

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