ハフマン符号化の原理と実装 — 最適符号化、変種、実用上の注意点

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

はじめに

ハフマン符号化（Huffman coding）は、有限アルファベット上のシンボル列を可逆的にビット列へ変換し、期待符号長を最小化するための古典的かつ実用的な手法です。1952年にデイヴィッド・ハフマン（David A. Huffman）が発表したアルゴリズムは、情報理論と実用圧縮の接点に位置し、ZIP/DEFLATE、PNG、JPEG（ベースライン）など多くの圧縮フォーマットで利用されています。本稿では理論的背景、アルゴリズムの詳細、実装上の工夫、変種（適応型・長さ制限型・カノニカル化）および実用上の注意点まで幅広く解説します。

基礎理論：最小冗長性符号と接頭語性

ハフマン符号は「接頭語（prefix）符号」として設計されます。接頭語符号とは、ある符号語が他の符号語の先頭部分になることがない符号系であり、その性質により符号語の境界を一意に復元できます。任意の接頭語符号の符号長の組はクラフト・マクミランの不等式（Kraft–McMillan inequality）を満たします。

ハフマンの目的は、与えられたシンボルの出現確率（または出現回数）に基づいて、期待符号長 E[L]=Σ p_i l_i を最小化することです。ハフマンアルゴリズムは貪欲法に基づき、最も出現確率が小さい2つのシンボルを結合してツリーを構築することで最適解を与えることが証明されています（交換論法により示される）。ただしこれはビット単位の符号長（整数長）を前提とした最適性です。

標準的なハフマンアルゴリズム（静的ハフマン）の手順

  • 入力：各シンボルの周波数（重み）w_i。
  • 手順：
    • 全てのシンボルを葉ノードとして最小ヒープ（優先度付きキュー）に挿入する（キーは重み）。
    • 最小の2つのノードを取り出し、合成ノード（重みは和）を作成して再びヒープへ挿入する。
    • ヒープ内のノードが1つになるまでこれを繰り返す。最後に得られた木がハフマン木。
    • 木を根から走査し、左枝を0、右枝を1（または任意）と決めて符号語を割り当てる。
  • 出力：各シンボルに対応するビット列（接頭語符号）。

計算量は n 個のシンボルに対し、ヒープを用いると O(n log n) です。全メッセージ長に対する符号化は O(m)（m は入力シンボル数）、復号は符号長に依存しますがツリーベースでの逐次復号は実用的です。

例（簡単な手順）

シンボルと頻度： A:45, B:13, C:12, D:16, E:9, F:5 とすると、最小2つ（E:9, F:5）を結合→(E+F):14、次に C:12 と (E+F):14→26、B:13 と D:16→29、… を繰り返してツリーを作ります。得られる符号は一例として A:0, B:101, C:100, D:111, E:1101, F:1100 のようになります（分岐の割当てによって0/1は逆になる場合があります）。

カノニカルハフマン符号（Canonical Huffman）

カノニカル化は実装やストレージ上の利点が大きい変法です。カノニカルハフマン符号では符号語自体ではなく各シンボルの符号長のみを保存しておき、符号長の情報から一意に符号語を復元します。これによりシンボルテーブルの転送量が削減され、符号語の割り当てが決定的になるためデコードテーブルの再構築や高速化（テーブル駆動デコード）が容易になります。DEFLATE（ZIP/PNG）などで採用されています。

長さ制限付きハフマンとパッケージマージ

実戦では符号長に上限を課す必要がある場合があります（デコーダの制約や規格上の制限）。長さ制限付きハフマン問題は単純なハフマンでは最適解を与えない場合があるため、パッケージ・マージ（package-merge）アルゴリズムなどの手法が用いられます。パッケージ・マージは符号長制約付きで最適な符号長分配を計算できます。

適応型（動的）ハフマン符号

入力データを1回スキャンできない、または確率が事前に不明な場合は適応型ハフマンが有用です。代表的な手法にFGK（Faller-Gallager-Knuth）やVitterのアルゴリズムがあります。これらは符号化の最中に頻度を更新し、ツリーを動的に再構成することで逐次的に符号化を行います。ただし適応型は静的ハフマンに比べて圧縮率や実装の複雑さにトレードオフがあります。

デコード手法と高速化

復号は基本的にビットストリームをツリーに沿って走ることで行いますが、ツリー探索を毎ビット行うと遅くなります。高速復号には次の手法があります。

  • ルックアップテーブル：最大kビットを先読みしてテーブルで直接復号。テーブルサイズは 2^k。
  • カノニカルコード＋ビット長テーブル：ビット長→シンボル配列を用い、可変長でも定数時間に近い復号を実現。
  • ビットストリーム操作の最適化：ワード単位で読み込み、ビット反転やシフトを工夫して処理。

ハフマンと算術符号化（Arithmetic Coding）の比較

ハフマン符号はシンボルごとに整数ビットの符号長しか出力できないため、エントロピー（情報量）に対して若干の冗長が残る場合があります。一方で算術符号化やレンジ符号化は非整数平均ビット長に近づけるため高効率です。ただし算術符号化は実装が複雑で過去に特許問題があり、また演算精度や速度の面での配慮が必要でした。実務ではハフマンのシンプルさと速度、符号語表送信の容易さから採用されるケースが多く、必要に応じて算術符号化へ移行します。

実用上の注意点とトレードオフ

  • 辞書（コードブック）のオーバーヘッド：短いデータ列では辞書の送信コストが圧縮効果を打ち消す。
  • シンボル集合が大きい場合のメモリ：ヒープやテーブルのメモリ使用量に注意。
  • 確率推定の精度：確率分布が変化するデータには適応型が有利だが、学習コストが必要。
  • 符号長の不均衡：非常にまれなシンボルに長い符号が割り当てられ、実装上のエッジケースになることがある。

実装のチェックリスト

  • 周波数計算を正しく行う（符号化前に1パスで集計）。
  • 最小ヒープやソートによりノードの結合を実装し、安定した結合順を決める（同重みの処理は規格に依る）。
  • 符号長を得たらカノニカル化を検討し、符号語のストレージ量とデコード性能を最適化する。
  • 復号ルーチンは安全なバッファ境界チェックとシビアなビット操作を行う。
  • 必要に応じて長さ制限付き最適化（パッケージ・マージ）や適応アルゴリズムを選定する。

代表的な採用例

  • DEFLATE（ZIP, gzip, PNGの内部圧縮）: LZ77とハフマン符号の組合せ（RFC 1951）。
  • JPEG（ベースライン）: DCT係数のエントロピー符号化にハフマン符号を利用（ITU T.81）。
  • MP3/オーディオコーデック: 一部でハフマン符号が使用される場面がある（可変長符号化テーブル）。

まとめ

ハフマン符号は理論的に整った最小冗長性符号を実現する手段であり、単純さと高速性、規格化された運用方法（カノニカル化や長さ制限手法）があるため広く利用されています。一方で符号長が整数ビットに制約される点や、確率情報が不正確な場合の扱いなど実運用上の注意点もあります。本稿で述べた実装技法や変種を理解すれば、用途に応じた最適な設計が可能になります。

参考文献

カテゴリー
IT
前の記事
VSTとは何か：歴史・仕組み・制作現場での使い方を徹底解説
2025年12月12日
次の記事
ソース符号化を徹底解説：理論・代表アルゴリズム・実装上の注意点と応用
2025年12月12日