bzip3: BZip2の後継がテキスト圧縮で驚異の結果、全Perlソースを546MBに圧縮

最近、圧縮された.jsonlファイル（JSON lines形式）を処理していました。lzmaはgzipやbzip2よりもはるかに圧縮率が良く、アーカイブのコスト削減に役立ちますが、ソフトウェアのサポートが不足していて扱いにくいです。私はduckdbで処理していますが、gzipは透過的にサポートされています。bzip2用の拡張機能はありますが、lzmaやbzip3用はありません。

結局、私が使っているソフトウェアで最もサポートが良く、今後採用するソフトウェアでもサポートされる可能性が高いため、gzipを使いました。しかし、試した選択肢の中で圧縮率は最悪でした。これらのbzip3の数値を見ると、確かにFOMO（取り残される恐怖）を感じます...

ベンチマークは不誠実で、都合の良い結果だけを選んだように見えます。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は比較さえされていません。

興味深い偶然のベンチマークとして、https://github.com/iczelia/bzip3/releases にアクセスして、bzip3が自身のリリースアーカイブをどの程度圧縮するかを見ることができます。また、https://github.com/iczelia/bzip3/blob/master/.github/workflo... にアクセスして、他の圧縮機にどのオプションが選ばれているかを見ることもできます。

これは、より大きなウィンドウとロングレンジモードを備えたzstdのベンチマークを含めるべきだと思います。彼らが使用したウィンドウが個々のバージョンのtarファイルよりも小さい場合、有用な圧縮が妨げられるでしょうから、驚かないでしょう。

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

これは、形式化+AIの良いテストケースになるかもしれませんね。

圧縮アルゴリズムは、LLMによって大幅に改善される可能性が高いと思います。クローズドループ評価で実行できる理想的な候補問題であり、エージェントに試行錯誤させることができます。

bzipの作者が作成したわけではないのに、そのような名前を使うのは不快です。どういうわけか、オープンソース開発者は、独自の名前を考える代わりに、商標侵害になりそうな名前を使うのが好きです。