Huffman 符号化 (1952)（ハフマンフゴウカ）
David A. Huffman が MIT 在学中の 1952 年に発明した可変長符号化アルゴリズム。出現頻度の高い文字に短い符号を、低い文字に長い符号を割り当てる「最適接頭符号」を生成し、ZIP・PNG・JPEG・MP3 など現代主要フォーマットの基礎技術となった。
概要
Huffman 符号化は、David A. Huffman が MIT 在学中の 1952 年に発明した可変長符号化アルゴリズムで、出現頻度の高い文字に短い符号を、低い文字に長い符号を割り当てる「最適接頭符号 (Optimal Prefix Code)」を生成する画期的な技術です。当時 MIT の Robert Fano 教授が出題した「最適な可変長符号」問題に対する Huffman の解答として誕生し、それまでの Shannon-Fano 符号化を改良してエントロピー限界に漸近する最適性が情報理論的に証明されています。ZIP・PNG・JPEG・MP3・gzip・bzip2 など現代主要フォーマットの基礎技術として、データ圧縮分野で最も影響力のあるアルゴリズムの一つとして 70 年以上活躍し続けています。
主な特徴・仕組み
- 発明: 1952 年 David A. Huffman (MIT 大学院生)
- 論文: "A Method for the Construction of Minimum-Redundancy Codes" (1952)
- 入力: 文字の出現頻度 (確率分布)
- 構築方法: 最小頻度 2 文字をマージして親ノード生成、繰り返し
- 符号生成: Huffman 木の根から葉までのパス、左 0・右 1 で符号
- 最適性: 接頭符号として平均符号長最小、エントロピー限界に漸近
- 可変長: 高頻度文字 1-3bit、低頻度文字 10+bit
- 接頭符号: どの符号も他符号の接頭辞でない、復号一意
- 適用: 静的 Huffman (固定確率) と動的 Huffman (適応的) あり
- 限界: 整数 bit のみ、Arithmetic Coding は分数 bit でさらに高圧縮
スペック比較表
| 符号化方式 | 年 | 平均符号長 | 用途 |
|---|---|---|---|
| 固定長 (8bit) | - | 8bit | ASCII 標準 |
| Shannon-Fano | 1948 | やや劣る | Huffman 前身 |
| Huffman | 1952 | エントロピーに近い | ZIP/PNG/JPEG/MP3 |
| Arithmetic | 1976 | エントロピー限界 | JPEG2000/H.265 |
| ANS (Asymmetric Numeral Systems) | 2009 | 限界に近い | Zstd/lz4 |
具体例・対応技術
- ZIP/Deflate (1989): LZ77 + Huffman 符号化、現代標準圧縮
- PNG image (1996): Deflate ベース、画像圧縮
- JPEG (1992): DCT + Huffman、写真圧縮の世界標準
- MP3 (1993): Huffman 符号化を最終段で利用、音声圧縮
- gzip (1992): Deflate ベース、UNIX 系標準圧縮
自作PCでの選び方・注意点
Huffman 符号化は現代のあらゆるファイル圧縮・画像圧縮・音声圧縮で内部的に動作しており、エンドユーザーが直接意識する場面は少ないですが、性能チューニングの場面で意識すべき技術です。ZIP/gzip/PNG ファイルを開く際の CPU 負荷の大部分が Huffman 復号、CPU クロック数・キャッシュサイズに影響を受けます。Intel/AMD 最新 CPU には Huffman 復号支援命令 (BMI2 の PDEP/PEXT 命令等) が組み込まれ、第 12 世代 Intel Core (Alder Lake) 以降・Ryzen 7000 シリーズで顕著な高速化が見られます。Web 開発で Gzip 圧縮の応答速度を最適化したい場合、サーバ CPU の Huffman 復号性能・帯域とのバランス検討が重要。
関連用語との違い
- LZ77/LZ78: 辞書ベース、Huffman とは別系統、両者組合せ (Deflate) が最強
- Arithmetic Coding: 算術符号化、分数 bit で Huffman より高圧縮率
- ANS (Zstd の基盤): 2009 年新世代、Huffman の現代後継
よくある質問（FAQ）
Q1: Huffman と Shannon-Fano の違いは? A: 両方とも可変長符号だが、Huffman は最適性が証明済み、Shannon-Fano は近似的。Huffman の方が圧縮率が高い、現代主流。
Q2: Huffman 符号化だけでファイル圧縮できる? A: 可能だが圧縮率は LZ77 (辞書ベース) との組合せに大きく劣る。実用的な圧縮ツールは両者を組み合わせる (Deflate = LZ77 + Huffman)。
Q3: なぜ 70 年も使われ続けてる? A: シンプルさ・最適性証明・実装容易性のバランスが優れている。Arithmetic Coding はわずかに高圧縮だが特許問題と実装複雑性で Huffman が依然主流。
まとめ
- Huffman 符号化 = 1952 年 David Huffman 発明、最適接頭符号
- 出現頻度で符号長を可変、エントロピー限界に漸近
- ZIP/PNG/JPEG/MP3/gzip など現代主要フォーマットの基礎
- 70 年以上現役、CPU 命令 (BMI2) でハードウェア支援も進む