Huffman 符号 (1952) — MIT の学期末レポートが生んだ最適圧縮アルゴリズム

1948 年、Bell Labs の Claude Shannon が発表した論文「A Mathematical Theory of Communication」は情報理論の基礎を築きました。この論文で Shannon はエントロピーという概念を定義します:

H = -Σ p(x) log₂ p(x)

エントロピーは「情報源から出るメッセージを符号化するのに必要な最小平均ビット数」を表します。これは理論的な下限であり、いかなる無損失圧縮もエントロピー未満には圧縮できません (Shannon の情報源符号化定理)。

Shannon 自身もエントロピーに近い符号を構成する方法を提案しましたが、それは最適ではありませんでした。MIT の Robert Fano も独立に同様の手法 (トップダウンで確率を二分割) を開発し、これが Shannon-Fano 符号と呼ばれます。しかし Shannon-Fano は特定の確率分布で最適にならないケースがありました。

MIT で Fano の情報理論の授業を受講していた大学院生 David Huffman は、学期末に選択を迫られました: 期末試験を受けるか、最も効率的な二進符号を見つけるレポートを書くか。

Huffman はレポートを選びましたが、何ヶ月も取り組んでも Shannon-Fano 符号を超える方法が見つかりませんでした。締め切り直前、諦めて試験を受けることにしたその瞬間 — 自分のノートを捨てようとしたときに、ボトムアップで木を構築するアイデアが閃いたと言われています。

このアイデアは Shannon-Fano を含む他のすべてのプレフィックス符号より常に最適 (または同等) であることが証明でき、Huffman はレポートとして提出。1952 年 9 月、Proceedings of the IRE, Vol. 40, No. 9, pp. 1098-1101 にわずか 4 ページの論文として掲載されました。教授の Fano 自身の手法を、自分の学生が超えたのです。

Huffman 符号の構築は貪欲法 (greedy algorithm) です。手順は驚くほどシンプル:

1. 各シンボルをその出現頻度 (確率) とともにリストに入れる
2. リストから最小頻度の 2 つを取り出す
3. 2 つを子ノードとする新しい内部ノードを作り、頻度を合算してリストに戻す
4. リストにノードが 1 つだけになるまで繰り返す
5. 完成した二分木の左枝に 0、右枝に 1 を割り当てると、各シンボルの符号が得られる

例: A=45%, B=13%, C=12%, D=16%, E=9%, F=5%

Step 1: E(9) + F(5) → EF(14)
Step 2: B(13) + C(12) → BC(25)
Step 3: EF(14) + D(16) → DEF(30)
Step 4: BC(25) + DEF(30) → BCDEF(55)
Step 5: A(45) + BCDEF(55) → root(100)

結果:  A=0, B=101, C=100, D=111, E=1101, F=1100
平均: 0.45×1 + 0.13×3 + 0.12×3 + 0.16×3 + 0.09×4 + 0.05×4 = 2.24 bit/symbol
エントロピー H ≈ 2.23 bit/symbol (ほぼ最適)

結果はプレフィックス符号 (prefix-free code) になります。どの符号語も他の符号語の先頭部分にならないため、区切り記号なしで連結しても一意にデコードできます。

Huffman 符号が最適であることの直感的な説明:

• 出現頻度の高いシンボルに短い符号、低いシンボルに長い符号を割り当てる
• ボトムアップ構築により、最も頻度の低い 2 シンボルが最長の符号を持ち、かつ同じ長さになる
• この「最も低い 2 つを先に結合する」手順は、各ステップで平均符号長の増加を最小化する

原論文で Huffman は帰納法による厳密な最適性証明を与えました: n シンボルの場合に最適なら、n+1 シンボルでも最適、という構造です。

ただし重要な制約があります: Huffman 符号は各シンボルに整数ビット長の符号語を割り当てる前提での最適です。もしシンボルに非整数のビット長 (例: 2.3 ビット) を割り当てられるなら、算術符号 (Arithmetic Coding) の方がエントロピーにさらに近づけます。

DEFLATE は RFC 1951 (May 1996) で定義された圧縮アルゴリズムで、LZ77 + Huffman 符号の 2 段構成です:

1. LZ77: テキスト内の繰り返しパターンを (距離, 長さ) のペアに置換
2. Huffman 符号: LZ77 の出力 (リテラルバイト + 距離/長さペア) を可変長ビット列に符号化

DEFLATE は gzip (.gz)、zlib、PNG 画像、ZIP アーカイブ、HTTP の Content-Encoding: gzip など、あらゆる場所で使われています。Web サーバーが HTML を gzip で圧縮して送信するたびに、内部で Huffman 木が構築・適用されています。

DEFLATE は「動的 Huffman テーブル」と「固定 Huffman テーブル」の 2 モードを持ちます。動的モードではデータの統計に基づいてテーブルを構築して圧縮率を最大化し、固定モードは RFC 1951 に定義された固定テーブルを使って処理速度を優先します。

JPEG (ISO/IEC 10918-1) は以下のパイプラインで画像を圧縮します:

1. 色空間変換 (RGB → YCbCr)
2. 8×8 ブロックに分割
3. DCT (離散コサイン変換) で周波数成分に変換
4. 量子化 (高周波成分を丸める — ここが非可逆)
5. エントロピー符号化 (Huffman 符号)

ステップ 5 で、量子化された DCT 係数を Huffman 符号で可変長ビット列に変換します。JPEG 規格は算術符号もサポートしていますが、算術符号には当時特許問題があったため、事実上すべての JPEG 実装が Huffman 符号を使用しています。

HPACK は RFC 7541 (May 2015) で定義された HTTP/2 のヘッダ圧縮方式です。HTTP ヘッダのフィールド名と値を静的 Huffman テーブルで圧縮します。

RFC 7541 の Appendix B には 256 シンボル + EOS (End of String) に対する固定の Huffman テーブルが掲載されています。このテーブルは HTTP ヘッダに出現する文字の頻度分布から事前に構築されたもので、小文字アルファベットや数字が短い符号 (5-7 ビット)、制御文字が長い符号 (20-30 ビット) を持ちます。

例: 'a' = 5 ビット、':' = 5 ビット、'A' = 6 ビットなど。HTTP ヘッダの大部分は小文字の ASCII なので、8 ビット固定より大幅に圧縮されます。

HPACK は Huffman 符号 + 静的テーブル + 動的テーブル (ヘッダの辞書) を組み合わせた三層構造で、HTTP/1.1 と比べてヘッダサイズを 85-90% 削減できます。

Huffman 符号の限界はシンボル単位で整数ビット長を割り当てる点にあります。あるシンボルの理想的な符号長が 2.3 ビットでも、Huffman では 2 か 3 ビットにせざるを得ません。

算術符号 (Arithmetic Coding) は 1976 年に IBM の Jorma Rissanen が提案し、1979 年に Rissanen & Langdon が実用化した手法で、メッセージ全体を 1 つの小数として符号化します。シンボル単位の整数制約がないため、エントロピーにより近い圧縮率を達成できます。

現在の使い分け:

2010 年代以降、Jarek Duda が提案した ANS (Asymmetric Numeral Systems) が算術符号の圧縮率と Huffman の速度を両立する手法として注目され、Facebook の Zstandard (zstd) や Apple の LZFSE で採用されています。

• Shannon (1948): エントロピーが無損失圧縮の理論下限、Shannon-Fano 符号は最適ではない
• Huffman (1952): MIT の学期末レポートとして最適プレフィックス符号を発見、原論文わずか 4 ページ
• アルゴリズム: 最小頻度の 2 シンボルをボトムアップで結合する貪欲法
• 最適性: 整数ビット長のプレフィックス符号として証明済みの最適解
• DEFLATE (RFC 1951): LZ77 + Huffman、gzip / PNG / ZIP の基盤
• JPEG: DCT + 量子化後のエントロピー符号化に使用
• HPACK (RFC 7541): HTTP/2 ヘッダの静的 Huffman テーブルで 85-90% 圧縮
• 限界: シンボル単位の整数制約 → 算術符号や ANS がさらに高圧縮率