**ビジップへの賛歌** ビジップ、力強き圧縮器 そのアルゴリズムは揺るがず確か。 生のデータの絡まった網から 静かに隠れたパターンを抽出し。 各バイトブロックで最頻符号を先に見つけ、 エントロピーと秩序の舞いを繰り広げ、 騒音を整然とした構造へ変える。 二十四キロバイトのスライディングウィンドウで ストリームを滑らせ、繰り返しを合わせテーブルを作り、 さらにフムマン符号で圧縮を深める。 出力は小さく速度は安定し、 それでも情報は一つとして残さない。 ファイルサイズの静かな守護者、 ビジップよ、あなたの揺るぎない働きを讃えます。

2026年3月12日 – Reddit

物語はこう始まります。ComputerCraft はマインクラフトにプログラミングを追加するモッドです。Lua のコードを書き、専用のインタプリタがワールド API にアクセスしながら実行します。つまり、楽しむ代わりにコードを書いている状態です。コンピュータはディスク容量が限られており、私の

/nix

フォルダは制御不能ほど拡大しています。そこでコードを圧縮する必要があります。

最も手軽な選択肢は LibDeflate ですが、そのデコーダーは圧縮による利点より大きく、また私がコピーできるコード量の個人的上限を超えてしまいます。したがって問われるのは「最短で最も単純、かつ比率効率の高い圧縮アルゴリズムとは何か？」です。

初めは多くのトレードオフがある複雑な問題だと考えていましたが、実際には明確に答えが出ました。私の回答は bzip です。xz や zstd が人気になる以前から批判され続けてきたこのアルゴリズムですが、私はそれを選びます。

327 KB の Lua コードファイル（コメントやドキュメントに散在する英語テキスト）を圧縮しています。重要なのは、bzip がバイナリよりもテキストのようなデータで優れているという点です。結果は他のコードベースでも再現可能で、パーセンテージはこのカテゴリ内ではほぼ一定に見えます。

圧縮比較

フォーマット	サイズ（バイト）
未圧縮	327 005
gzip	75 882
zstd –22 –long –ultra	69 018
xz –9	67 940
brotli –Z	67 859
lzip –9	67 651
bzip2 –9	63 727
bzip3	61 067

bzip 系列は大きく勝っています。lzip（「lzip –9 はほとんどのファイルを bzip2 より圧縮できる」とされている）をも上回ります（コードは「ほとんどのファイル」ではないので）。どうやって実現しているのでしょうか？ それは、bzip が他とは違うからです。

他の人気圧縮アルゴリズムは核として同じ構造を持っています。すべて LZ77 に基づき、繰り返しテキストを以前出現した箇所への短いリンクに置き換える仕組みです。主な違いは文字列とバックリファレンスがビットストリームとしてエンコードされる方法で、非常に非自明です。リンクのオフセットや長さ、頻度は場所によって大きく異なるため、良いアルゴリズムはこれらのパラメータを予測し簡潔にエンコードする必要があります。

bzip は LZ77 を使わない という点が鍵です。bzip は Burrows–Wheeler Transform（BWT）を利用します。これはテキスト内の文字を並べ替えて文脈ごとにグループ化し、類似した以前の出現箇所に基づく予測ではなく、最後数文字だけを見ることでエンコードできるようにします。そして驚くべきことに、BWT の順序では各文字がどこから来たかを保存する必要さえありません。

例として hello がテキスト中で複数回出現するとしましょう。LZ77 ならそれぞれの出現箇所で新しい参照を検索・挿入します。一方 BWT では「hell」の続きがまとめられ、結果として連続する多くの “o” が並びます。このような場合、単純なランレングス符号化（RLE）だけで十分です。

BWT の欠点もあります。異なる英語方言（例：color vs colour）のテキストを結合すると、“colo” の続きが予測不可能に混ざり合い、奇妙な “rs” と “us” の列をエンコードする必要があります。LZ77 なら最近の履歴を優先します。この問題は入力をフォーマットごとに分離すれば解決できますが、一貫したデータ（例えばコード）ではそのままでも十分機能します。

bzip2 と bzip3 は両方とも BWT をベースにしており、主な違いは BWT 出力の圧縮方法です。bzip2 は RLE の変種を使用し、bzip3 はより賢明であることを試みます。性能上の理由から bzip2 に焦点を当てますが、多くの結論は bzip3 でも同様に適用されます。

BWT に関してもう一つ興味深い事実があります。bzip3 を呼び出すときに

-9

のようなパラメータを渡さない理由です。 それは bzip3 がそのようなオプションを受け取らないからです。実際、bzip2 に

-9

を付けてもほとんど影響がありません。LZ77 ベースの手法では検索コストが時間消費になるため圧縮レベルを調整します。一方 BWT は完全に決定論的でヒューリスティックを持ちません。

さらに、バックリファレンスの長さとオフセットを効率的にエンコードする自由度は存在しません。BWT にはそれらがないため、ランレングスだけが残ります。それは単一の数値で、典型的なオフセットよりも小さいです。

要するに、bzip2 パイプラインを理解すれば、微調整やエッジケースを心配せずに同様の圧縮比を得ることができます。私の非最適化でアドホックな bzip2 ライクエンコーダは、約 67 KB に圧縮し、lzip を上回り、改善の余地も明確です。

デコーダサイズ

ここまで圧縮フォーマットを説明しましたが、デコーダのサイズはいかにでしょう？ Lua ターゲットでは ELF のサイズ測定は意味がなく、LibDeflate などの Lua ライブラリは自己解凍アーカイブ用にコードサイズを最適化していません。読者をおしゃれな語句や少女数学で遠ざける恐れがありますが、bzip2 を除いてすべてについて概算します。

自己解凍実行ファイルは全てのアーカイブをデコードする必要はありません ― 1 つだけです。サニティチェックやヘッダーを省略し、メタデータをコードにインライン化し、フォーマットを簡易化すればよいので、ここではコア解凍ループのみを見ることにします。

• gzip, zstd, xz, brotli, lzip は全て LZ77 から始まります。コピー・トークンの評価はシンプルなループで済みます。違いはそれらがビットへどのようにエンコードされるかです。

  • gzip は軽量前処理後にハフマン符号化を適用し、トークンに一意のビット列を割り当て、頻度分布に基づいて総長さを最適化します。ハフマンコードは約 250 バイトでパースでき、ビット trie は ~700 バイト、余剰部分は ~500 バイト ― 合計で約 1.5 KB。
  • xz はトークンをビット単位でエンコードし、確率を動的に調整してテーブルを埋め込まずに良好な比率を実現します。ビット単位の解析は通常より多くスペースを要しますが、テーブルを省略できる点が大きい利点 ― 約 1 KB。
  • lzip は xz とほぼ同じですがトークンエンコードをわずかに変更。結果も約 1 KB。
  • zstd は前処理を複雑化し、ハフマンではなく有限状態エントロピー（FSE）を使用します。これはトークンを分数ビット長でエンコード可能にしますが、大きなテーブルが必要 ― ストアとパースに約 2 000 バイト。追加の余剰で ~3 KB。
  • brotli はハフマン符号化を維持しつつ、コンテキストに応じて複数の静的ハフマンテーブルを飛行中に切り替えます。正確なカウントは不明ですが入力では 7 テーブルが出現 ― パーサは約 500 バイト、各テーブルで ~100 バイト、合計で約 2.2 KB。

• bzip デコーダ：BWT は約 250 バイトで処理できます。独自部分として

  • bzip2 は BWT 出力を MTF + RLE + ハフマンで圧縮します。デフォルトの 6 テーブルでは全ハフマン関連コードとデータに ~1.5 KB、MTF, RLE と余剰に ~400 バイト。
  • bzip3 は XZ ライクなビット単位符号化をコンテキスト混合で行い、前者は約 1 KB、後者は ~500 バイト。

標準ファイルフォーマットの互換性を捨てることでデコーダをさらに小さくできます。数値は多少誤差があるかもしれませんが、大きな変化はないでしょう。

bzip スタイル手法は中間くらいですが、実際には誤解を招くことがあります。bzip2 は通常 6 テーブルを使用しますが、私は 1 テーブルだけで良好な圧縮結果を得ました。その場合 bzip スタイルデコーダは約 1.5 KB に収まり、xz や lzip を除けばすべてより小さく、しかも高速です。

速度対比率

bzip は遅いとよく言われますが、微妙な違いがあります。圧縮をハードリミット回避に使う場合、bzip と gzip の差は起動時間の速さではなく「起動できるかどうか」です。initrd を解凍する際に 0.5 s が必要であっても 0.3 s より大きいだけで、起動不能になるほど重大ではありません。

この視点から見ると、「bzip は gzip より遅い」と言うのは質問を投げかけるようなものです。gzip は最適化された出力を簡単に作れないため、ヒューリスティックで以前の出現箇所を検索し、時間対比率トレードオフを設定します。gzip が高速なのは設計上ではなく「速さ」を重視した結果です（-9 でも同様）。良い比率が欲しいなら zopfli を使う必要がありますが、zopfli は bzip よりずっと遅く、出力も劣ります。

デコード側では、BWT の逆転にはランダムアクセスが必要なため遅くなることがあります。Lua などの高水準言語ではすべての操作が遅いので、この点は大きな問題ではありません。この状況で最も一般的な圧縮手法よりもさらにコストがかかるケースです。gzip は bzip2 より速くデコードできますが、zstd と brotli は速度面で近いでしょう。

実際に bzip3 を使用したことはありませんが、ビット単位でトークンを解析する必要があるため、bzip3 のデコードは bzip2 よりかなり遅くなると予想します。bzip3 ライクな比率をこの要件なしで達成できるかは検討の余地があります。

結論

結局のところ私の答えは 「カスタム圧縮アルゴリズムではなく、バズビットにワイッスルを付けたもの」 です。もし私について何か知っていれば、新しいものを発明しないことが驚くべきと思われるでしょう。実際試してみましたが、成功率はばらつきます。

---

演習

テキスト圧縮の核となる考え方は「テキストは繰り返しである」ため、毎回 repeat を書く代わりに、以前出現した repeat への参照をエンコードする（できれば短い）というものです。例えば文字列：

Rust is an iron oxide, a usually reddish‑brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture.

…は次のようにエンコードできます。

Write Rust is an iron oxide, a usually reddish-brow
Copy 7 bytes from 31 bytes ago (n oxide)
Write  formed by the
Copy 3 bytes from 24 bytes ago ( re)
Write acti
Copy 4 bytes from 60 bytes ago (on o)
...

テキストを圧縮する際、繰り返し部分は単語であると期待されますが、この例ではしばしば音節やランダムな文字列になります。コード構造に基づく圧縮を試みると、個々のトークンしか圧縮できず、困難です。

事前処理して bzip を適用すれば余分な利益は得られますが、デコーダを複雑化し、比率も大きく改善されません。例えば Luz は gzip でこれを行い、比率に影響なしに数キロバイトのデコードオーバーヘッドを生み出します。

これはデータ圧縮の一般的な体験です：実世界データは人間が簡単に推測できない構造を持ちますが、コンピュータはリアルタイムで認識できます。改善はアルゴリズムを複雑化するよりも、データを再構成し、より強力な汎用手法を適用することで実現します。

機械学習に似ていると感じるなら、正解です。2009 年の記事 Rationale for a Large Text Compression Benchmark ではこの関係が詳細に説明されています。今日では素朴に聞こえるかもしれませんが、Large Text Compression Benchmark のトップコンテンダーは nncp（NN は何の略か想像できます）です。

bzip は一般的な圧縮フォーマットとして最適とは言えないものの、テキストとコードには優秀です。b が「best」を意味するとまで言えるでしょう。bzip エンコーダは LZ77 ベースのエンコーダよりヒューリスティックや設計上の誤差が少なく、圧縮比に大きく影響します。

bzip のデコードは高水準言語で実装するとかなり高速です。