ハフマン符号の基礎から実装・応用まで: データ圧縮の定番プレフィックス符号を徹底解説

2025年11月22日 最終更新日時 : 2025年11月22日 エバープレイ編集部

ハフマン符号とは

ハフマン符号（Huffman coding）は、1949年にデヴィッド・ハフマンが提案した可変長の符号化方式で、与えられた記号集合とそれぞれの出現頻度（または確率）に基づいて、平均符号長を最小にするプレフィックス符号（どの符号語も他の符号語の接頭辞にならない）を構成します。これは可逆（復号可能）な可変長符号の代表的手法であり、情報圧縮アルゴリズムの基礎理論および実装で広く使われています。

基本的な考え方

ハフマン符号の直感は単純です。出現頻度の高い記号ほど短いビット列を割り当て、出現頻度の低い記号には長いビット列を割り当てることで、全体の平均ビット長を小さくします。ハフマンのアルゴリズムは「貪欲法」によってこの割り当てを行い、常に最も頻度の低い2つの記号（または部分木）を結合して新しい内部ノードを作る操作を繰り返します。

アルゴリズムの手順（静的ハフマン符号）

  • 入力：各記号とその出現頻度（または確率）
  • 1. 各記号を葉ノードとする森林を作り、ノードの重みをその頻度とする。
  • 2. 最も重みの小さい2つのノードを取り出し、それらを子とする新しいノードを作る。新ノードの重みは子の重みの和。
  • 3. 新しいノードを森林に戻す。
  • 4. 森が1本の木になるまで、2〜3を繰り返す。
  • 5. 完成した二分木の各枝に0/1を割り当て、葉までのビット列を各記号の符号語とする。

実装上は、重みの小さいノードを効率よく取り出すために優先度付きキュー（ヒープ）を用い、計算量は典型的に O(n log n)（n は記号数）となります。既に重みがソートされている場合はO(n)で構築できる手法もあります。

プレフィックス性とデコード

ハフマン符号はプレフィックス符号であるため、受信ビット列を左から順に読み進めるだけで一意にデコードできます。具体的には、符号木の根からスタートしてビットに応じて左右の子へ移動し、葉に到達したら対応する記号を出力して再び根に戻ります。この性質により、ビット単位で逐次的に復号が可能です。

最適性の概要

ハフマン符号は「与えられた記号ごとの重み（確率）が既知であり、かつ各記号を独立に符号化する（記号毎に符号長を割り当てる）という制約の下で、平均符号長を最小化するプレフィックス符号」を構成します。最適性の証明は貪欲法の正当性を示す交換論法（exchange argument）や帰納法に基づいています。概略としては、最小の重みを持つ2つの記号を同じ深さにすることは最適解の一部となっており、これを再帰的に行うことで全体の最適解が得られる、という構成です。

例（簡単な手計算）

例として、記号と頻度が次のように与えられたとします：A:5, B:9, C:12, D:13, E:16, F:45。
手順：

  • 最小の2つ 5 (A) と 9 (B) を結合して14を作る。
  • 集合は 12,13,14,16,45 となる。次に 12 (C) と 13 (D) を結合して25。
  • 集合は 14,16,25,45。14 (A+B) と 16 (E) を結合して30。
  • 集合は 25,30,45。25 と 30 を結合して55。
  • 最後に 45 と 55 を結合して根 (100) を得る。

この木を上からビット（例えば左=0, 右=1）を割り当てると、F は最も短く 0、C は 100、D は 101、A は 1100、B は 1101、E は 111 となります（※ビット割り当ての左右向きは任意に決められるため実装により表現は異なります）。

実装上の工夫と応用

  • ヘッダ（符号表）をどのように保存するかが実用では重要です。符号語そのものを保存すると大きくなるため、各記号の符号長だけを保存する「カノニカルハフマン符号（canonical Huffman）」が使われます。カノニカル方式では長さ情報から規則的にコード語を再生成できるため、ヘッダのサイズと復号速度が改善されます。
  • DEFLATE（gzip, zlib）、PNG、JPEG（ベースラインJPEGのハフマン符号）はハフマン符号（あるいはその派生）を使用しています。多くの実装はカノニカルハフマンを採用します。
  • 動的（適応）ハフマン符号：メッセージの統計が事前に分からない場合には、走行中に頻度を更新して符号を適応的に変更するアルゴリズム（FGK, Vitter のアルゴリズムVなど）があります。ただし実装が複雑で、圧縮効率や計算コストの面で現代では代替として算術符号（arithmetic coding）やレンジ符号（range coding）が選ばれることも多いです。
  • 長さ制約つきハフマン符号（length-limited Huffman）：実装上、最大符号長を制限したい場合があります（例：JPEGでは符号長の上限）。この場合はパッケージマージ法（package-merge）などの手法で最適解を求めます。

利点と限界

  • 利点：理論的にシンプルで実装が比較的容易。プレフィックス性により逐次復号が可能。カノニカル化によりヘッダが小さく、高速に復号できる。
  • 限界：ハフマン符号は各記号を独立に扱う「記号ごと符号化（symbol-by-symbol）」方式であるため、真のエントロピー（情報量）に対して1ビット以内のオーバーヘッドにしか最適化できないことが知られています。連続するビット列を非整数長で最適化できる算術符号は、平均符号長をさらに低くできることがあります。また、短いデータ列ではヘッダのオーバーヘッドにより圧縮効率が悪化する場合があります。

実装の注意点

  • 頻度がゼロの記号は通常符号表に含めないか、特別扱いする（ただし復号側で符号表にない記号は扱えない）。
  • 同じ頻度の記号の扱いはアルゴリズムによって異なり、結果のコード長分布は同じでもビット列は変わる。互換性が必要なら規則（例えばシンボル順）を決めておく。
  • ビット単位の入出力、パディング、バイト境界処理、バイトオーダーに注意する。特にストリーム圧縮では部分バイトの取り扱いが重要。
  • 大きなアルファベット（例えば符号化対象がバイト列なら256）の場合、符号長テーブルやデコード用のルックアップテーブル（最大長kに対するテーブル）を用いて高速化する。

発展と代替

  • 算術符号（Arithmetic coding）・レンジ符号（Range coding）：確率モデルに基づき非整数平均長によりエントロピー限界により近づける。ハフマンより高圧縮だが計算がやや重く、かつ実装時の丸め誤差等に注意が必要。
  • 文脈モデルを使う：文脈ごとにハフマン木や算術符号を使うことで、統計的依存（局所的な頻度変化）を利用してさらに圧縮率を上げる手法がある（例えば PPM、コンテキストモデル＋算術符号など）。
  • 長さ制約やメモリ制約を考慮した最適化問題には専用アルゴリズムがある（package-merge、Hu–Tucker など）。

まとめ

ハフマン符号は、与えられた記号ごとの頻度に基づいて平均符号長を最小化する古典的かつ実用的な圧縮手法です。実装の単純さ、逐次復号可能という利点から多くの圧縮フォーマットで使われてきました。一方で、非整数ビット長による最適性限界やヘッダオーバーヘッドなどの実務上の制約があり、より高効率を狙う場合には算術符号や文脈モデルとの組合せが検討されます。実装時はカノニカル化、デコードテーブル、長さ制限といった細部の設計が性能に大きく影響します。

参考文献

カテゴリー
IT
前の記事
ゴースト（Ghost）徹底ガイド：プロフィール・来歴・サウンド特徴・世界観・代表曲とライブ演出New!!
2025年11月22日
次の記事
ゴーストのアナログ盤徹底ガイド：おすすめレコードとプレスの選び方、コレクター必携New!!
2025年11月22日