エントロピー符号化の基礎から最新手法まで徹底解説：Huffman・算術・ANSを中心に実務適用と比較
エバープレイ編集部エントロピー符号化とは — 概要と基本概念
エントロピー符号化（entropy coding）は、情報源の確率分布（符号化対象データの統計）に基づいて不均等長のビット列を割り当て、データを効率的に表現する可逆圧縮技術の総称です。ここでいう「エントロピー」はシャノンの情報理論におけるエントロピー H を指し、理想的には平均符号長はエントロピーに近づけられることが目標になります。
代表的な手法にはハフマン符号（Huffman coding）、シャノン–ファノ符号（Shannon–Fano）、算術符号（arithmetic coding）、範囲符号（range coding）、そして近年普及している非対称数体系（ANS, Asymmetric Numeral Systems）などがあります。多くの実用圧縮アルゴリズムは、まず入力の冗長性を取り除くためにモデル化（例えば LZ77 のような辞書化や文脈モデル）を行い、最後の段でエントロピー符号化を適用してビット列に変換します。
情報量とエントロピーの数学的定義
離散確率分布 {p_i} に対して、シャノンエントロピーは次のように定義されます（対数は2を用いれば単位はビット）：
H(X) = -Σ_i p_i log2 p_i
エントロピーは1シンボルあたりの最小平均情報量（理論限界）を与え、任意の可逆符号の平均符号長 L は情報理論上 H ≤ L が成り立ちます。さらに、適切な符号化手法を用いることで L を H に限りなく近づけることが可能です。
主なエントロピー符号化方式
ハフマン符号（Huffman coding）
最も古典的で広く使われる方法。各シンボルに対して可変長のビット列を割り当て、頻度の高いシンボルは短い符号語を、低頻度のシンボルは長い符号語を割り当てます。接頭辞符号（prefix-free）であり、受信側はビット列を一義的に復号できます。
特徴：実装が比較的簡単で、高速。最適な接頭辞符号を作れる点が利点（確率が既知のとき、最小の平均符号長を実現）。ただし符号長は整数ビット長に制約されるため、理論上の最小（エントロピー）からは最大で +1 ビット/シンボルの差が生じます。
シャノン–ファノ符号（Shannon–Fano）
シンボルを確率順に分割して木を作る手法。ハフマンと似ていますが必ずしも最適にならない場合があります。歴史的に重要ですが、実用ではハフマンに置き換えられることが多いです。
算術符号（Arithmetic coding）
シンボル列全体を [0,1) の実数区間の部分区間に対応付け、その区間を精度に応じてビット列で表す手法です。個々の符号語が整数ビット長に束縛されないため、平均符号長をエントロピーに非常に近づけることができます。特に長いブロックや良好なモデルを組み合わせると、エントロピー限界にほぼ到達可能です。
実装上は無限精度の実数を使えないため、整数演算で区間を操作する range coder やビット列の正規化（renormalization）を行う技術が使われます。算術符号は文脈モデル（PPM など）と組み合わせて高い圧縮率を実現してきました。
範囲符号（Range coding）
算術符号の実装上の効率化バリエーションで、整数のみの演算で算術符号と同等の性能を実現します。特にエンコーダ・デコーダの速度向上を目的に採用されることが多いです。
ANS（Asymmetric Numeral Systems）
Jarek Duda によって提案された比較的新しい方法。算術符号と同等かそれ以上の圧縮率を維持しつつ、非常に高速に動作する点が特徴です。FSE（Finite State Entropy）などの派生は実用的な高速エントロピー符号器として Zstandard や Facebook の圧縮ライブラリなどで採用されています。
符号の最適性と不等長符号の性質
接頭辞符号（あるコードを他のコードの先頭にしてはいけない）については Kraft–McMillan の不等式が成り立ちます：
Σ_i 2^{-l_i} ≤ 1 （l_i は各シンボルのコード長）
また、十分長いブロック長やブロック符号化を用いると、平均符号長をエントロピーに近づけられる（情報源符号化の基本定理）。ハフマン符号のような最適な接頭辞符号は、確率が既知で独立同分布（IID）な場合に平均符号長を最小化しますが、符号長が整数であるため H ≤ L < H + 1 のような評価が成り立ちます。一方、算術符号や ANS は非整数長に相当する表現が可能なため、理論限界により近づけます。
モデル化（モデリング）と符号化の分離
実用的な圧縮システムでは「モデル化（統計推定）」と「符号化（エントロピー符号化）」を分離して考えます。多くの場合、符号器自身の最適化よりも、より良い確率モデルを作ることの方が圧縮効率に大きく寄与します。例えば PPM（Prediction by Partial Matching）や文脈ベースのモデルは、算術符号と組み合わせることで非常に高い圧縮率を達成します。
実際の用途とフォーマットでの採用例
PNG や DEFLATE（gzip）は LZ77 に続いてハフマン符号を使います（RFC 1951）。
JPEG（baseline）はハフマン符号を用いますが、標準内で代替の符号化手法が使われる場合もあります。多くの画像・映像フレームワークでは算術符号や CABAC（H.264 の文脈適応算術符号）などの高効率手法が用いられます。
Zstandard は FSE（ANS 派生）を使って高速かつ高効率なエントロピー符号化を行います。Brotli や modern compressors でもハフマンや ANS 系の技術が使われます。
算術符号・範囲符号の実装上の注意点
精度と正規化：区間を小さくしていくと下位桁の情報が失われる危険があるため、定期的にビットを出力して区間を正規化する必要があります。整数演算ベースで実装する際にアンダーフロー問題や桁あふれを回避するための工夫（レンマ、キャリー処理など）が必要です。
計算量と遅延：算術符号は高効率だが、初期の実装では計算コストが高く速度面で不利だったため、range coder や ANS による高速化が進められました。ストリーミング性（逐次エンコード・デコード）や低遅延が必要な用途では実装上のトレードオフが生じます。
符号表の管理（ハフマン）：ハフマンでは符号語表を送る際の手間を減らすため canonical Huffman（符号長のみを送って復元する形式）がよく使われます。これにより実装が簡潔でデコーダの高速化も可能です。
適応型（アダプティブ）符号化と単語（ブロック）符号化
確率分布が既知でない場合、実用的には以下のような手法があります：
- 静的符号：事前に統計を集計して固定の符号表を生成（データをスキャンしモデルを作る）。
- 適応符号（Adaptive Huffman、Adaptive Arithmetic）：符号化の途中でモデルを更新しながら符号化する。追加のヘッダ情報が不要でストリーミングに向く。
- ブロック符号化：ある長さのブロックに対して全体で符号化を行うことで、符号化効率を上げる（ブロック長が長いほど理論限界に近づくがメモリ・遅延のコストが増大）。
性能指標と評価
エントロピー符号化の性能評価は主に次の観点で行われます：
- 平均符号長（ビット/シンボル）とエントロピーとの差（余分に必要なビット数）
- 圧縮・伸張の速度（スループット）
- メモリ使用量と実装の複雑さ
- エラー耐性（ビット誤りが沿った場合の影響）と同期のしやすさ
一般に、より複雑で高効率な符号（算術、ANS 系）は圧縮率が良いが実装コストや計算リソースが増える傾向があります。一方でハフマンやカノニカルハフマンは実装が単純で高速かつランダムアクセスやデータの分割に強いという利点があります。
実務上の注意点・歴史的な背景
- 算術符号は1980〜1990年代に特許・ライセンスの問題が取りざたされたため、特に画像圧縮分野ではハフマンが採用されることが多かったという歴史があります。後に多くの特許は期限が切れるか標準団体を通じたライセンス管理が行われ、算術符号やその派生は広く使われるようになりました（ただし映像標準に関わる特許プールは今日も存在します）。
- 実際の圧縮効果は「符号化方式」自体よりも「どのような確率モデル（文脈など）を使うか」が大きく影響します。したがって、同じエントロピー符号化器を使ってもモデル次第で圧縮率は大きく変わります。
まとめ — いつどの方式を選ぶか
- 高速で実装容易、かつストリーミングやランダムアクセスに強い：カノニカルハフマンや固定長テーブル方式。
- 圧縮率を最大化したい（長いブロック・高品質モデルが使える）：算術符号や ANS（FSE）がおすすめ。
- モデルの更新をオンラインで行いたい、遅延を抑えたい：適応符号化（adaptive arithmetic、adaptive Huffman）を検討。
- 実装複雑さ・ライセンス・エラー耐性などの要件を総合的に勘案して選択する。
参考文献
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", 1952
- C. E. Shannon, "A Mathematical Theory of Communication", 1948
- I. H. Witten, R. M. Neal, J. G. Cleary, "Arithmetic Coding for Data Compression", Communications of the ACM, 1987
- J. Duda, "Asymmetric Numeral Systems", arXiv (多くの論文・実装が公開されています)
- Zstandard (FSE, ANSによる実装)、GitHub リポジトリ
- RFC 1951 (DEFLATE compressed data format specification)
- Wikipedia: Arithmetic coding（実装上の課題や歴史がまとめられています）
- Wikipedia: CABAC（H.264/AVC の文脈適応算術符号化）
投稿者プロフィール
