ファイル圧縮の仕組み：Huffman Coding・LZ77・DEFLATE を徹底解説
開発者ならば必ず圧縮ファイルを扱う。パッケージを展開し、gzip 圧縮されたレスポンスを配信し、PNG をエクスポートする——その陰で圧縮は常に動いている。しかし多くのチュートリアルが避けている問いがある。なぜ機能するのか？ 500 KB のテキストファイルを 1 バイトも失わずに 180 KB に縮められるのはなぜか。一方、ZIP ファイルをもう一度圧縮してもほとんど効果がないのはなぜか。
答えは情報理論と少数の洗練されたアルゴリズムにある。本記事では、シャノン・エントロピーから Huffman 木、そして ZIP・gzip・PNG を支える DEFLATE 形式に至るまで、実際のメカニズムを解説する。
ファイルが圧縮できる理由
ファイルが圧縮できるのは、冗長性——パターン、繰り返し、予測可能なシーケンス——を含んでいるからだ。これらは生のバイト数が示すよりも少ない情報しか運んでいない。
単純な例を考えよう。文字列 AAAAAAAAAA（A が 10 個）は ASCII で 10 バイト占める。しかし情報量は微々たるものだ——「A が 10 個」と完全に表現できる。圧縮アルゴリズムはまさにそれを行う——冗長で長ったらしいデータをより短い記述に置き換える。
実際のファイルにはこの種の冗長性が溢れている：
- 日本語テキストは同じ単語や文字の組み合わせを繰り返し使う。「です」「ます」「する」などは非常に高頻度で現れる。
- ソースコードは深く反復的な構造を持つ：
function、return、const、インデント、空行。 - ビットマップ画像は水平方向に同一またはほぼ同一のピクセルが連続する——特に無地の領域。
- ログファイルはタイムスタンプ、ホスト名、ステータスコードを何千回も繰り返す。
データが冗長であるほど圧縮しやすく、ランダムに近いほど圧縮は難しくなる。
エントロピー：圧縮の絶対的な限界
Claude Shannon が 1948 年に発表した論文 A Mathematical Theory of Communication は、情報量を正確に測る方法——エントロピー（ビット単位）——を提唱した。
シャノン・エントロピーが答える問いは：このデータソースの 1 シンボルを表すために、平均で実際に何ビット必要か？
シンボル s₁, s₂, ..., sₙ と確率 p₁, p₂, ..., pₙ を持つ情報源に対する公式は：
H = -Σ pᵢ × log₂(pᵢ)
実際に何を意味するか見てみよう。A（90%）と B（10%）の 2 文字しかないファイルがあるとする。
H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 ビット/シンボル
単純な符号化では 1 ビット/シンボル（A→0、B→1）を使う。しかしエントロピーは、理論上の最小値が 0.469 ビット/シンボル——半分以下——だと告げている。優れた圧縮アルゴリズムはこの限界に近づく。
次に、各バイト値（0〜255）が等確率（1/256）で現れる完全にランダムなファイルを考える：
H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 ビット/バイト
1 バイトあたり 8 ビット——最大エントロピー。利用できる冗長性がない。これが ZIP ファイルをこれ以上圧縮できない理由だ：すでに最大エントロピーに近い。すべてのビットが情報を運んでいるため、排除できるパターンが残っていない。
ランレングス符号化：最もシンプルな形式
より重いアルゴリズムに入る前に、ランレングス符号化（RLE）でコアとなるアイデアをわかりやすく示す。
RLE は繰り返しシンボルの列をカウントとシンボルで置き換える：
元の文字列： AAABBBBBCCDDDDDD
RLE： 3A 5B 2C 6D
元：16 文字。符号化後：8 文字。50% の削減。
RLE はファクシミリ伝送（CCITT Group 3/4）、BMP ファイル、より複雑なフォーマット内のサブステップで使われる。弱点は明白だ——長い繰り返しのないデータには機能しない。文字列 ABABABAB には繰り返しがなく、RLE は至る所に 1 のカウントを付加することで大きくしてしまう。
この弱点こそが、より洗練されたアプローチを生む動機となっている。
Huffman Coding：頻度の高いシンボルに短い符号を
標準の ASCII では、出現頻度に関わらずすべての文字が 8 ビットを受け取る。Huffman Coding はその前提を崩す。頻繁に現れるシンボルは短い符号を、稀なシンボルは長い符号を割り当てられる。平均符号長が下がり、ファイルが小さくなる。
Huffman 木の構築
文字列 AABBBCCCC（9 文字）を使おう。頻度を数える：
ステップ 1. 各シンボルを頻度で重み付けされた葉ノードに置く。
[A:2] [B:3] [C:4]
ステップ 2. 最も重みが小さい 2 ノードを繰り返し、重みの和を持つ親ノードに結合する。1 本の木になるまで続ける。
[A:2] と [B:3] を結合 → 親 [AB:5]：
[AB:5]
/ \
[A:2] [B:3]
[C:4]
[C:4] と [AB:5] を結合 → 根 [ABC:9]：
[ABC:9]
/ \
[C:4] [AB:5]
/ \
[A:2] [B:3]
ステップ 3. 木を辿って符号を割り当てる：左辺 = 0、右辺 = 1。
ビット節約の計算
Huffman 符号で AABBBCCCC を符号化するコスト：
A × 2 回 × 2 ビット = 4 ビット
B × 3 回 × 2 ビット = 6 ビット
C × 4 回 × 1 ビット = 4 ビット
合計 = 14 ビット
固定 8 ビット ASCII では：
9 文字 × 8 ビット = 72 ビット
14 ビット対 72 ビット——このトイ例では 81% 削減。実際の削減は小さいが、原理は同じだ。
重要な洞察：Huffman 符号はプレフィックスフリーだ。どの符号も別の符号のプレフィックスにならないため、デコーダは区切り文字なしで元のストリームを一意に復元できる。木の構造自体は圧縮ファイルのヘッダに格納され、デコーダが再構築できるようにする。
LZ77 と LZ78：繰り返しシーケンスの活用
Huffman Coding は個々のシンボルの頻度に作用する。しかしそれは、より大きな冗長性のクラスを見逃す：繰り返しシーケンス。ソースコード中の function という単語は毎回 8 バイト占める。2 回目以降の出現を最初の出現へのポインタで置き換えられれば、大幅な節約になる。
Abraham Lempel と Jacob Ziv は 1977 年と 1978 年の論文でまさにそれを説明し、LZ77 と LZ78 を生み出した。
LZ77：スライディングウィンドウ圧縮
LZ77 はスライディングウィンドウ——最近見たデータのバッファ——を維持する。エンコーダは新しいデータを処理しながら、ウィンドウを逆向きに検索して次に来るものと最長一致を探す。見つかれば、リテラルバイトの代わりにバック参照 (オフセット, 長さ) を出力する。
文字列のエンコードを考えよう：
abcabc
abc の処理：過去の履歴なし、リテラル a、b、c を出力。
2 番目の abc の処理：エンコーダは 3 つ前の位置から始まる abc（長さ 3）を発見。3 つのリテラルバイトの代わりにバック参照 (オフセット=3, 長さ=3) を出力。
デコーダは (3, 3) を見て、出力バッファ内の 3 つ前の位置に戻り 3 バイトをコピー——abc を完全に復元する。
実際の実装では、一致検索はウィンドウサイズ（gzip は 32 KB）で制限される。ウィンドウが大きいほど多くの一致が見つかるが、メモリと検索時間のコストが増える。
バック参照 (オフセット, 長さ) は通常 2〜3 バイト。10 バイトの繰り返しシーケンスを 2 バイトの参照で置き換えると 8 バイトの節約になる。一致が長いほど比率が良くなる。
LZ78 と LZW
LZ78 はスライディングウィンドウではなく、検出済みパターンの明示的な辞書を構築する。その派生版である LZW（Lempel-Ziv-Welch）は、GIF 圧縮と Unix の compress ユーティリティのアルゴリズムとして有名になった。LZW はパターンを単一の辞書インデックスとして符号化し、エンコードとデコード中に辞書を動的に拡張する。
DEFLATE：LZ77 と Huffman Coding の組み合わせ
DEFLATE（RFC 1951 で定義）は LZ77 と Huffman Coding を順に組み合わせる：
- LZ77 パス： 繰り返しシーケンスをバック参照
(オフセット, 長さ)で置き換える。出力はリテラルとバック参照のストリーム。 - Huffman パス： そのストリームに Huffman Coding を適用する。頻繁なリテラルは短い符号、稀なバック参照値は長い符号を得る。
2 つの技術は異なる種類の冗長性を攻撃する。LZ77 は長距離の繰り返しを排除し、Huffman Coding は残りの頻度ベースの冗長性を排除する。組み合わせることで、どちらか単独では達成できない圧縮率を実現する。
DEFLATE データはブロックに組織化される。各ブロックは 3 つのモードのいずれかを使用できる：
- 非圧縮——圧縮すると出力が膨らむデータ向け（すでにランダムなデータ）
- 固定 Huffman 符号——事前合意された符号テーブルで、カスタム木を格納するオーバーヘッドを省く
- 動的 Huffman 符号——このブロック専用に最適化されたカスタム木をブロックヘッダに格納
動的モードはほとんどの圧縮可能データに使われる。エンコーダはブロックを分析し、最適な Huffman 木を構築してブロック先頭に格納し、その木を使ってデータを符号化する。
DEFLATE が実際のファイル形式に使われている場所
ZIP
ZIP ファイルは各エントリを独立して保存し、それぞれが独自の DEFLATE 圧縮ストリームを持つ。このエントリごとの圧縮により、アーカイブ全体を展開せずに 1 つのファイルを取り出せる。ZIP 形式はすでに圧縮されているファイル向けに「保存」モード（圧縮なし）もサポートする。
gzip
gzip は単一の DEFLATE ストリームをヘッダ（マジックナンバー、OS、変更日時）と CRC32 チェックサムで包む。HTTP Content-Encoding: gzip と .tar.gz アーカイブの標準圧縮形式だ。.gz 拡張子は常に単一の DEFLATE ストリームを示す。
PNG
PNG は zlib 経由で DEFLATE を使ってピクセルデータを圧縮する。圧縮前に PNG はフィルタステップを適用する：各ピクセル行を予測値との差分に変換する（デルタ符号化）。これにより LZ77 が活用できる繰り返しが劇的に増加し、圧縮率が大きく向上する。典型的なスクリーンショットやダイアグラムでは、PNG は生のピクセルデータサイズの 20〜50% に圧縮される。PNG をエクスポートする画像圧縮ツールはこのパイプラインに依存している。
zlib
zlib は DEFLATE のラッパー形式で、2 バイトのヘッダと Adler-32 チェックサムを追加する。PDF ストリームは埋め込みコンテンツの圧縮に zlib/DEFLATE を使用する（PDF 圧縮はこれらのストリームを再圧縮または削除することでファイルサイズを削減する）。HTTP、WebSockets、多くのネットワークプロトコルも zlib を使用する。
JPEG：別のアプローチ
ここで一時停止する価値がある。JPEG はまったく異なる圧縮戦略を使用するからだ——意図的にデータを失う方式だ。
JPEG は 8×8 ピクセルブロックに**離散コサイン変換（DCT）**を適用する。DCT はピクセル値を周波数成分に変換する（フーリエ変換に似ている）。高周波成分——細かいディテール——は積極的に量子化される（粗い値に丸められるか、完全に破棄される）。残りの係数は Huffman Coding で符号化されるが、写真に対して JPEG が PNG より大幅に小さい理由は、この損失量子化ステップにある。
トレードオフ：JPEG は元のピクセルを完全に復元できない。PNG はできる。これがロスありとロスなしのファイル変換の記事で詳しく扱うロスあり対ロスなしの区分だ。
写真では、品質 80 の JPEG はロスなし PNG が必要とするバイト数の 10% しか使わない可能性がある。フラットカラーとシャープなエッジを持つスクリーンショットでは、PNG が通常勝る——DCT アーティファクトが可視であり、DEFLATE はフラットな領域を非常にうまく圧縮できるからだ。
ZIP ファイルをこれ以上圧縮できない理由
よくある混乱の源だ。圧縮がパターンを見つけることで機能するなら、すでに圧縮されたファイルを圧縮してもほとんど効果がないのはなぜか？
DEFLATE が正しく仕事をしているからだ。よく圧縮された DEFLATE ストリームは統計的にランダムに見える——設計によってそうなっている。バック参照と Huffman 符号が予測可能なパターンを排除する。残っているものはデータのエントロピー限界に近い。
2 番目の圧縮ツールを通しても、繰り返し（LZ77 は長い一致を見つけられない）も頻度の偏り（Huffman はほぼ均一なシンボル分布を見る）も見つからない。エントロピーはすでに 1 バイトあたり 7.9+ ビットだ。活用できるものは何も残っていない。
これが、すでに圧縮されたメディアを圧縮すべきでない理由でもある。JPEG を ZIP で包んでも、ZIP のオーバーヘッドを払うだけでサイズの恩恵はゼロだ。MP3、MP4、HEIC についても同じ——これらはすでにエントロピーの天井近くにある圧縮形式だ。
アルゴリズム比較
すべてをつなげる
gzip 圧縮ファイルの生データから圧縮バイトへの処理チェーン：
- 入力： 生のバイトストリーム（例：テキストファイル）
- LZ77： 32 KB スライディングウィンドウでバック参照を検索し、リテラルと
(オフセット, 長さ)ペアのストリームを出力 - Huffman Coding： 2 本の木を構築——リテラル/長さ用と、オフセット用——し、LZ77 の出力を符号化
- DEFLATE ブロック： Huffman 木と符号化済みデータを 1 つ以上のブロックにパッケージ
- gzip ラッパー： gzip ヘッダを先頭に付加、CRC32 と元のファイルサイズを末尾に追加
- 出力：
.gzファイル、圧縮可能な入力では通常 30〜70% 小さくなる
展開は厳密に逆順で行われる：gzip ヘッダを解析し、ブロックヘッダから Huffman 木を読み取り再構築し、Huffman ストリームを LZ77 トークンにデコードし、バック参照を適用して元のバイトストリームを復元する。展開は常に圧縮より速い——困難な作業（最適な一致の検索、最適な木の構築）は一度だけ行われるからだ。
まとめ
- ファイルが圧縮できるのは冗長性——繰り返しパターンと偏ったシンボル頻度——を含んでいるから。
- シャノン・エントロピーは絶対的な下限を定める：真にランダムなデータはすべてのビットが既に情報を運んでいるため圧縮できない。
- RLE は繰り返しを粗く扱い、Huffman Coding は頻度の偏りを優雅に扱い、LZ77 は長距離のシーケンス繰り返しを扱う。
- DEFLATE は LZ77 と Huffman を順に組み合わせるため、どちらか単独よりも優れている。ZIP・gzip・PNG および zlib 圧縮 PDF ストリームのエンジンだ。
- JPEG は根本的に異なるアプローチを取る：ロスあり DCT 量子化に続くロスなし Huffman で、ピクセル精度を劇的なサイズ削減と引き換えにする。
- 圧縮済みファイルを圧縮しても無駄——良い圧縮はほぼ最大エントロピーの出力を生成するからだ。
これらのアルゴリズムを理解することは、形式の選択、予想外に大きなファイルの診断、圧縮パイプラインのデバッグに役立つ。次回 PDF 圧縮を使ったり、ZIP ファイルを展開したり、画像圧縮のために PNG をエクスポートするとき、ソフトウェアがあなたのビットに何をしているか正確に理解できるはずだ。