bzipへの賛辞：現代のエンジニアに語り継ぎたい「古き良き圧縮ツール」の功績

本投稿は、かつてデータ圧縮の世界で重要な役割を果たした「bzip」への敬意を表したものです。現在ではbzip2や他のモダンなアルゴリズムに取って代わられましたが、その設計思想や歴史的背景を振り返り、改めてその価値を称賛する内容となっています。

bzip2って、めちゃくちゃいい仕事してるのに誰からも評価されない同僚みたいな圧縮アルゴリズムだよな。一方でgzipは「まあこれで十分でしょ」って感じで評価を独り占めしてる。

どうしても少しでもスペースを節約したいってわけじゃないなら、zstd使っとけばいいよ。bzip2とxzは圧縮速度がめちゃくちゃ遅いからさ。

記事の序盤でxzやzstdの方がbzipより人気が出たって言ってるけど、素人考えかもしれないけど、圧縮時間と全体の圧縮率のトレードオフで彼らの方が優秀だってことだよね。パフォーマンスのセクションではgzipとbzipのエンコード性能をかなり詳しく議論してるけど、見落としてなければ、xzやzstdについてはデコード時間がたぶん似たようなもんだろう、っていう適当な流し方しかしてないよね。

個人的な感想としては、この記事はbzipとgzipをどう比較するかについては技術的な洞察が深いけど、なぜbzipの人気が落ちて、ここ数年でより人気の選択肢になった非gzip代替案へ流れたのかっていう本当の理由を説明しきれていない気がする。

言っておくけど、bzip3はbzip2とほとんど関係ないからね。別の著者が作った、別のBWT実装と別のエントロピーコーデックを使ったものだよ（GitHubの説明にも「BZip2のより優れて強力な精神的後継」って書いてあるし）。

いい機会だから書いておくけど、Go用の klauspost/compress パッケージに含まれる gzhttp が、サーバーハンドラとクライアントトランスポートの両方で zstd をサポートしたよ。変なのは、API面を広げてデフォルトの動作まで変えてるのに、マイナーバージョンじゃなくてパッチバージョンで追加されたことだね。

https://github.com/klauspost/compress/releases/tag/v1.18.4

個人的な意見だけど、未来は特定のフォーマットに合わせて最適化された専用コンプレッサー（ https://openzl.org/ など）が主流になるんじゃないかな。

テキストやコードを圧縮する場合、自分の経験とこの記事は合わないな。

bzipは汎用圧縮フォーマットとしては最適じゃないかもしれないけど、テキストやコードには最高だよ。bzipの「b」は「best」の頭文字って言ってもいいくらいだ。

試しに1GBのSQLファイルでやってみたけど、bzip2 -9で83MBになったのに対し、zstd -19 --longなら52MBになったよ。

他の人もLinuxカーネルで圧縮を試してるけど、bzip2の方がzstdより15%くらいサイズが大きくなる結果が出てる。

BWTは変装したPPM（Prediction by Partial Matching）みたいなもんだよ。

「bananarama」を考えてみて。

（回転の結果、各行の末尾文字は同じ行の先頭文字からコンテキストを得る。）

でも、ソートした結果として、予測される（最後の）文字に対するコンテキストが連続しなくなるし、長い依存関係が壊れちゃうんだ。その壊れた長い依存関係のせいで、暗黙的にシンボルの直接的な統計をZipfの法則のような統計に変換するMTFが、BWTの出力をうまくエンコードできるっていうわけ。

[1] https://en.wikipedia.org/wiki/Zipf%27s_law

そう考えると、著者はPPMベースの圧縮機の方が圧縮性能は高いと感じるかもしれないね。Large Text Compression Benchmark [2] がまさにそれを証明していて、PPMを使った謎の圧縮機の方がBWTより3分の1くらい優秀だったりする。

アルゴリズムの話としては面白いけど、ストリーミング以外のパフォーマンスを気にするなら、xzやgzipには並列バージョンがあるってことを完全に無視してるね（pxzipは分割点のメタデータを互換性のある形式でエンコードするから、xzでデコードできるし、コア数も自由に使わせてあげられる）。ディスクイメージ系のOSインストーラーには最高なんだけどね（そもそも自分がこれをベンチマークしてた理由なんだけどさ。5年前のことだから、今でも上流に取り込まれてるのかはわからないけど…）。