次世代の高速圧縮ツール「bzip3」：圧縮効率と速度を両立する新定番

「bzip3」は、従来のbzip2アルゴリズムを大幅に改良し、モダンな計算環境で最高のパフォーマンスを発揮するように設計された新しい圧縮ツールです。高い圧縮率を維持しながら、現代のマルチコアCPUの能力を最大限に引き出し、高速な処理を実現しています。既存の圧縮形式からの移行や、大規模データのアーカイブを効率化したいエンジニアにとって、今注目すべきソリューションの一つです。

前回の振り返り:

「ハイ、ツールの作者です」という、bzip3で使われているBWT（Burrows-Wheeler変換）についての分かりやすい解説: https://news.ycombinator.com/item?id=42902407

「bzip3はまだ大規模テキスト圧縮ベンチマークに掲載されていない」→掲載されました: https://mattmahoney.net/dc/text.html

(2年前、コメント176件) https://news.ycombinator.com/item?id=42899713

(4年前、コメント104件) https://news.ycombinator.com/item?id=31324439

このベンチマークは作為的というか、都合の良いデータだけ選んでいるように見えるね。bzip3のブロックサイズは512MBに設定されているのに、zstdのウィンドウサイズはデフォルトのまま（高圧縮レベルでも8MBだよね）になってる。だから、Perlの全ソースコードを結合した今回のコーパスでは、ウィンドウが小さすぎてファイル間の重複をうまく見つけられていないんだ。
それに、長大な繰り返しがあるコーパスは、BWTベースの圧縮ツールにとってまさに最高の環境だしね。

zstdのウィンドウサイズをbzip3に合わせると、結果は劇的に変わるよ:

    % gzcat *.gz | time zstd -T8 -16 | wc -c  # ベースライン
     2819113884
    zstd -T8 -16  2054.50s user 3.47s system 783% cpu 4:22.80 total

    % gzcat *.gz | time zstd -T8 -16 --long=29 | wc -c
     196405076
    zstd -T8 -16 --long=29  1083.06s user 2.41s system 783% cpu 2:18.55 total

ベースラインより約15倍も小さくなるし、bzip3と比べても2倍以上小さい。しかもCPU時間も半分になってる（ロングマッチが早期に見つかるから、処理負荷が減るんだね）。

（ベースラインの数値が少し違うのは、作者が使ったPerlのバージョンと完全に同じものを持っていないからだよ）

あと、lrzipを使ったベンチマークならウィンドウサイズの影響はもっと少ないはずなのに、それと比較すらされていないね。

zstd側でウィンドウサイズを大きくしたり、long range modeを使ったベンチマークも加えるべきだと思う。たぶん、彼らが使ったウィンドウサイズって個別のバージョンのtarファイルより小さいだろうから、それじゃ有効な圧縮なんてできないよ。

とはいえ、アルゴリズムの複雑さ、特に極めて低い確率でしか発生しないような特殊なケースがコード内に存在することで、プログラム内にバグが残っている可能性を排除できない。

それ、形式検証とAIを組み合わせるための良いテストケースになるんじゃないかな？

面白い「意図しないベンチマーク」として、https://github.com/iczelia/bzip3/releases に行って、bzip3が自身のリリースアーカイブをどれくらい圧縮できているか見てみるといいよ。あと、https://github.com/iczelia/bzip3/blob/master/.github/workflows/release.yml#L23 を見れば、他の圧縮ツールにどんなオプションが選ばれているかも確認できる。

最近圧縮済みの.jsonl（JSON Lines形式）ファイルを処理していたんだけど、lzmaの方がgzipやbzip2より圧倒的に圧縮率が高くて、アーカイブコストの面では助かるんだよね。ただ、ソフトウェア側のサポートがなくて扱うのが大変。普段DuckDBで処理してるんだけど、あれはgzipを透過的にサポートしてる。bzip2用には拡張機能があるけど、lzmaやbzip3用はないんだ。

結局、自分が使うツールで一番サポートが手厚くて、今後導入するソフトでも使えそうなgzipで落ち着いた。でも、試した中では一番圧縮率が低かったんだ。bzip3の数字を見ると、使えなくてFOMO（取り残される不安）を感じるよ……。

openzlとの比較も見てみたいな。

bzipのオリジナルの作者が作ったわけでもないのに、そんな名前を付けるのは感心しないな。なぜかオープンソース開発者は、ユニークな名前を考える代わりに商標侵害になりそうな名前をつけたがるよね。

圧縮アルゴリズムは、LLMを使えば大幅に改善できる余地があると思う。閉じたループで評価できるし、AIエージェントに色々試させるには理想的な問題だよ。