エントロピー圧縮の理論と実装：情報量から実用アルゴリズムまで徹底解説

2025年12月12日 2025年12月12日

エバープレイ編集部

はじめに：エントロピー圧縮とは何か

エントロピー圧縮は、情報理論における「エントロピー（情報量）」の概念を基礎に、データを可能な限り短く表現する手法の総称です。ここでいうエントロピーは、シャノンの定義する平均情報量（シャノンエントロピー）を指し、データの統計的不確実性が小さいほど圧縮が効くことを示します。本稿では、エントロピーの理論的下限、代表的なエントロピー符号化アルゴリズム、モデル（確率推定）の重要性、実装上の注意点、そして現代の実用圧縮技術での位置づけまで、幅広く深掘りします。

情報エントロピーと符号長の下限

離散確率分布 p(x) に対するシャノンエントロピー H は次式で定義されます。

H = -Σ p(x) log_2 p(x)

シャノンの源符号化定理（Shannon’s source coding theorem）は、十分大きなブロック長では期待符号長が H に限りなく近づけられることを示します。任意の可逆（復号可能）な符号の平均符号長は H 未満にはできず、接頭辞符号（prefix code）であればハフマン符号は与えられたシンボル確率に対して最小の平均長を実現します。ただし、ハフマン符号はシンボル単位の独立モデルに基づくため、より複雑な依存性を持つデータでは最適とは限りません。

代表的なエントロピー符号化アルゴリズム

ここでは歴史的にも実用的にも重要な符号化手法を紹介します。

ハフマン符号（Huffman coding）：各シンボルの出現確率に基づいて二分木を構成し、前置コードを生成します。実装が簡単で高速ですが、確率が小数で分散が大きい場合や長いコンテキストを扱うと非効率になることがあります。
シャノン–ファノ符号（Shannon–Fano）：確率を分割して再帰的に符号を割り当てる手法。ハフマンより理論的に劣る場合があるため、現代ではあまり使われません。
算術符号化（Arithmetic coding）/レンジ符号化（Range coding）：シーケンス全体を一つの実数区間で表現することで、期待符号長をエントロピーに非常に近づけられます。特に確率モデルが連続的に変化する場合や、非常に多い記号集合を扱うときに有利です。実装では高精度演算あるいはレンジ符号化のような整数版が用いられます。
非対称数値体系（ANS: Asymmetric Numeral Systems）：算術符号化と同等の圧縮効率を保ちつつ、演算を簡素化して高速化した方式。Jarek Duda による提案以降、FSE（Finite State Entropy）などの実装が普及し、実用ライブラリ（例：Zstandard）の核として使われています。
コンテキストモデルとPPM：Prediction by Partial Matching は過去の文脈（直近の符号列）から次シンボルの確率を推定し、それを算術符号化などで符号化します。高い圧縮率を出せますが、メモリと計算コストが大きくなりがちです。

確率モデル（モデリング）の重要性

符号化アルゴリズムそのものは符号長を与える最終段ですが、実際の圧縮効率の大部分は「どれだけ現実のデータ分布を正確に推定できるか」に依存します。単純な固定確率モデルでは符号化効率に限界があるため、実用システムでは以下のような技術が用いられます。

文脈モデリング：直近の k 個のシンボル（Markov モデル）を使った確率推定。
可変長のコンテキストと背面オーダー：PPM やコンテキスト混合（context mixing）による多階モデルの統合。
変換と前処理：差分符号化、Burrows–Wheeler Transform（BWT）やMove-to-Front（MTF）変換などでデータの局所的冗長性を高め、エントロピー符号化の効率を向上させる。
適応モデル：データの統計が時間とともに変化する場合、オンラインで確率を更新する（adaptive）方式を使う。

実用的圧縮方式とエントロピー符号化の組合せ

現代の多くの圧縮アルゴリズムは、局所的冗長性の検出（例えば LZ77 のマッチ参照）と、それに続くエントロピー符号化の二段構えで構成されます。

DEFLATE（gzip、zlib）: LZ77 によるマッチ列の検出と、それらをハフマン符号で符号化。
bzip2: Burrows–Wheeler Transform → Move-to-Front → RLE → ハフマン。
LZMA: LZ 系の辞書手法にレンジ符号（算術的近似）を組合せ、高圧縮率を実現。
Zstandard（zstd）: LZ77 に続き、Finite State Entropy（ANS 系）を採用。高速かつ高効率。
メディア符号化（JPEG、H.264 等）: 変換（DCT 等）→量子化（損失要素）→エントロピー符号化（JPEG はハフマン、JPEG 2000 は算術符号化、H.264 は CABAC（算術的近似の文脈適応））。

理論的限界と計算複雑性

シャノンエントロピーは平均符号長の下限を示しますが、実際にはいくつかの制約が効いてきます。

ブロック長・遅延：理論的最適化には大きなブロック長が必要であり、遅延やメモリ制約とトレードオフになる。
モデル誤差：真の分布が未知であり、モデル誤差は余分な符号長（冗長度）を生む。
計算資源：高精度算術符号化や大規模コンテキストモデルは計算コストとメモリを要する。
アルゴリズムのオーバーヘッド：ヘッダや辞書情報の記録、符号化の汎化のための追加情報が小さくない場合がある。

実装上の注意点と落とし穴

実用実装でよく遭遇する課題は以下の通りです。

数値安定性と精度：算術符号化は浮動小数点や高精度整数の扱いで注意が必要。レンジ符号化やANSは実装を単純化する代替手段です。
適応性のバランス：学習を早くしすぎると初期データが過度に影響し、遅すぎると変化に追従しない。
未知シンボルの扱い：エスケープシンボルや辞書更新ルールの設計が必要（特にP PM系）。
セキュリティとプライバシー：圧縮はサイドチャネル（例：HTTP 圧縮を利用した情報漏えい攻撃）になる可能性がある。また、暗号化前の圧縮はパターンを露呈するため注意。

応用領域と最近のトレンド

エントロピー圧縮はファイル圧縮に限らず、ネットワーク転送、ストレージ、音声・画像・映像コーデック（損失部の後にエントロピー符号化を適用するのが一般的）など幅広い分野で用いられます。近年のトレンドとしては：

ANS を用いた高速で効率的な実装（例：FSE の普及）。
機械学習を用いた確率モデル：ニューラルネットワークで次シンボル分布を予測し、算術符号化やビットバック法と組み合わせる研究が進む。
圧縮と学習の共同設計：モデル容量と通信コストを同時最適化する研究が活発。

まとめ：理論と実装の橋渡し

エントロピー圧縮は「どのようにデータの確率をモデル化するか」が最重要です。ハフマンや算術符号化、ANS といった符号化器は手段であり、真に差を決めるのはモデルの精度、計算資源、遅延要件、実装上の工夫です。実務では LZ 系の冗長削減と ANS/レンジ符号化の組合せが現実的な高性能を生み出しており、今後は学習ベースの確率推定がより広く使われるようになると見込まれます。