Huffman 符号 (1952) — MIT の学期末レポートが生んだ最適プレフィックス符号

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

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

エントロピーは、確率モデルで表した情報源の 1 シンボル当たり平均情報量です。情報源符号化定理は、長いブロックを符号化したときに達成可能な平均符号長の限界を与えます。有限の個別ファイルが必ず H ビット/シンボル以上になる、という単純な主張ではありません。

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

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

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

このアイデアは、与えられたシンボル確率に対する二進プレフィックス符号の中で平均符号長を最小にでき、Huffman はレポートとして提出しました。1952 年 9 月、Proceedings of the IRE, Vol. 40, No. 9, pp. 1098-1101 に 4 ページの論文として掲載されています。授業の選択課題やノートを捨てようとした際の着想という逸話は、後年の紹介記事による回想であり、原論文そのものに記録された経緯ではありません。

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.22 bit/symbol (平均符号長の理論的な下限)

この例の平均符号長2.24 bit/symbolはエントロピー約2.22 bit/symbolに近く、Huffman符号はこの確率分布に対する二進プレフィックス符号として最適です。「ほぼ」というのは最適性ではなく、平均符号長がエントロピー下限にどれだけ近いかを表します。

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

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

• 出現頻度の高いシンボルに短い符号、低いシンボルに長い符号を割り当てる
• 最適木は、最も頻度の低い 2 シンボルを最深部の兄弟として選べる
• この「最も低い 2 つを先に結合する」手順は、各ステップで平均符号長の増加を最小化する

最適木では確率の最も小さい2シンボルを最深部の兄弟として選べます。この2つを一つの合成シンボルへまとめると、問題をシンボル数が1つ少ない同型の問題へ縮約できます。この性質を繰り返すのが、Huffman 法の最適性を支える構造です。

ただし重要な制約があります: Huffman 符号は各シンボルに整数ビット長の符号語を割り当てる前提での最適です。算術符号 (Arithmetic Coding) は個々のシンボルへ「2.3ビット」の固定符号語を直接割り当てるのではなく、メッセージ列全体を区間として符号化します。そのため、1シンボル当たりの平均では非整数のビット長となり、モデルのエントロピーにさらに近づけます。

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

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

DEFLATE は gzip (.gz)、zlib、PNG 画像、HTTP の Content-Encoding: gzip などで使われ、ZIP では代表的な圧縮方法の一つとして定義されています。ZIP は格納のみを含む複数の圧縮方法を扱えるため、すべての ZIP エントリーが DEFLATE とは限りません。また、DEFLATE 自体も、すべてのブロックで新しい Huffman 木を構築するわけではありません。

RFC 1951 は、無圧縮ブロック、固定 Huffman 符号のブロック、動的 Huffman 符号のブロックの 3 種類を定義しています。動的モードではそのブロック用の符号長を格納し、固定モードでは RFC 所定の符号を使います。エンコーダーは入力に応じて方式を選べます。

Web で一般的な JFIF/YCbCr 系のベースライン逐次 DCT JPEG は、概ね次のパイプラインで画像を圧縮します。ただし、ISO/IEC 10918-1 が定義するのは JPEG 符号化データの仕組みであり、色空間の意味や RGB と YCbCr の変換自体は同規格の正式な一部ではありません。JFIF や ISO/IEC 10918-5 などが、実用上よく使われる色の解釈を補います。

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

ステップ 5 で、量子化された DCT 係数を Huffman 符号で可変長ビット列に変換します。JPEG 規格には算術符号化も含まれるため、「JPEG は必ず Huffman」という意味ではありません。相互運用性の高いベースライン JPEG では Huffman 符号が使われます。

HPACK は RFC 7541 (May 2015) で定義された HTTP/2 のヘッダ圧縮方式です。ヘッダフィールドを静的・動的テーブルの索引で表せるほか、文字列リテラルには固定 Huffman 符号を使うか、そのまま送るかを選べます。

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

例: RFC 7541 Appendix B では 'a' は 5 ビット、':' は 7 ビット、'A' は 6 ビットです。頻出する文字には比較的短い符号が割り当てられていますが、Huffman 化によって必ず短くなるとは限らないため、文字列ごとに使用フラグがあります。

HPACK の圧縮率は、ヘッダの反復、値の内容、接続上の動的テーブルの状態などに依存します。特定の割合をすべての通信へ一律に当てはめることはできません。

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

算術符号 (Arithmetic Coding) は、Rissanen の 1976 年の研究や Rissanen & Langdon の 1979 年の論文などを通じて現代的な方式が発展しました。メッセージ列を区間として表現し、シンボルごとに整数ビット長を割り当てる制約を避けるため、モデルに対してエントロピーにより近い平均符号長を達成できます。

現在の使い分け:

Jarek Duda は ANS を 2009 年に公開し、その後 2010 年代に実装採用が広がりました。Zstandard は Huffman 符号と ANS 系の FSE を使いますが、すべての圧縮ブロックが両方を必ず使うわけではありません。RFC 8878 では、リテラル部は raw / RLE または Huffman 圧縮を選べます。Huffman の重み列も FSE 圧縮または直接表現があり、リテラル長・オフセット・マッチ長の符号には事前定義、RLE、FSE、直前の表を再利用する各モードがあります。

• Shannon (1948): 確率的な情報源モデルに対し、エントロピーが漸近的な平均符号長の限界を与える
• Huffman (1952): MIT の学期末レポートとして最適プレフィックス符号を発見、原論文わずか 4 ページ
• アルゴリズム: 最小頻度の 2 シンボルをボトムアップで結合する貪欲法
• 最適性: 整数ビット長のプレフィックス符号として証明済みの最適解
• DEFLATE (RFC 1951): LZ77 + Huffman。gzip / PNG で使われ、ZIP では代表的な圧縮方法の一つ
• JPEG: DCT + 量子化後のエントロピー符号化に使用
• HPACK (RFC 7541): 静的・動的索引に加え、文字列リテラルでは固定 Huffman 符号を選択可能
• 限界: シンボル単位の整数ビット長制約。算術符号や ANS はこの制約を避けられる