ソース符号化を徹底解説：理論・代表アルゴリズム・実装上の注意点と応用

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

イントロダクション：ソース符号化とは何か

ソース符号化（source coding）は、情報源が出力するデータをできるだけ短いビット列に変換する処理全般を指します。目的は伝送や記憶の効率化で、復号時に元データを（完全に）復元する「可逆（無損失）符号化」と、許容される誤差の範囲で圧縮率を高める「非可逆（損失）符号化」に大別されます。通信理論の基礎を築いたクロード・シャノンの情報理論は、ソース符号化の限界と設計指針を与えます。

基礎理論：エントロピーとシャノンの符号化定理

エントロピーH(X)は確率分布を持つ離散情報源Xの平均情報量を表す指標で、最小平均ビット長の下限を与えます。シャノンの源符号化定理は、独立同分布（i.i.d.）の情報源に対して、長ブロック符号化を行えば平均符号長がエントロピーに任意に近づけられることを示します。つまり、任意のε>0について十分大きなブロック長nを用いれば平均ビット長はH(X)+εを下回れる、というものです。

無損失符号化で用いられる重要な性質には次が含まれます：

  • クラフト不等式（Kraft inequality）：任意のプレフィックス符号の符号長{l_i}は sum 2^{-l_i} ≤ 1 を満たす必要があり、逆にこの条件を満たせば適切なプレフィックス符号が存在します。
  • ハフマン符号の最適性：既知の記号確率に対して、記号単位のプレフィックス符号で平均符号長を最小化する最適解を提供します（同率確率の取り扱いに注意）。
  • 可逆性（一意復号可能性）：符号語の集合が前置条件を満たすことで、復号が一意に行えることを保障します。

代表的な無損失符号化アルゴリズム

ハフマン符号

ハフマン符号は確率に基づく二分木を用い、最も頻出する記号に短い符号語を割り当てる方式です。計算量はソートや優先度付きキューにより O(n log n) 程度。短いブロックでは最も効率的ですが、確率モデルに依存するためモデル誤差や符号語長の整数制約でエントロピーとの差が残ります。

算術符号化（Arithmetic Coding）

算術符号化はシンボル列全体を区間にマッピングする手法で、任意精度でエントロピーに近づけられます。長い列を扱うと非常に効率的ですが、実装では有限精度の整数演算や区間の再スケーリングが必要となります。動画・画像標準（例：H.264のCABACは算術的手法の一種）でも採用され、高圧縮率を実現します。

範囲符号化とANS（Asymmetric Numeral Systems）

範囲符号化（range coding）は算術符号化の実装上の改良で、実際のエンコーダに適した形式です。近年はANSが性能（速度・圧縮率）で注目を集めています。ANSは特定の確率モデルに対し効率よく近似エントロピーの符号化を行い、ソフトウェア実装で高速性を発揮します。

Lempel-Ziv 系（LZ77/LZ78/LZW）

辞書ベースの手法で、出現したパターンを辞書に登録して参照に置き換えます。符号は統計モデルを明示的に作らず、逐次的に辞書を構築するため「普遍符号化（universal）」に分類され、特にテキストや繰り返しの多いデータで有効です。gzip（DEFLATE）はLZ77とハフマンの組み合わせです。

損失符号化（非可逆）の基礎：レート-ゆがみ理論

非可逆符号化はデータを近似して格納/伝送する手法で、レート（ビット数）とゆがみ（復元誤差）をトレードオフします。最良の理論限界はレート-ゆがみ関数R(D)で与えられ、これは与えたゆがみ許容度Dで到達可能な最小平均ビット率を示します。実用的符号化では変換（例：DCT, MDCT）、量子化、エントロピー符号化の組み合わせが典型です（JPEGは8x8 DCT + 量子化 + ハフマン/算術符号化）。

モデル化と文脈依存性：圧縮性能の鍵

符号化の効率は符号アルゴリズムだけでなく、どれだけ良い確率モデル（または予測モデル）を用いるかに大きく依存します。文脈モデリング（コンテキストに基づく確率推定）、線形予測（音声符号化）や機械学習を使った確率推定は、エントロピーに近い符号長を実現するための重要な要素です。近年はニューラルネットワークを用いた確率モデルやエンドツーエンドの学習ベース符号化も活発に研究・実装されています。

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

  • 計算資源と速度：高圧縮率を追求すると算術符号化や複雑なモデルが必要で、計算負荷が増加します。リアルタイム用途では高速なANSや単純なハフマンが選ばれることが多いです。
  • 精度と数値問題：算術符号化は区間の管理で精度問題やオーバーフローに注意が必要です。範囲符号化や整数ベース実装で対処します。
  • 特許とライセンス：歴史的に算術符号化や一部の符号化手法は特許対象でした。現在多くは期限切れですが、利用時はライセンス状況を確認してください。
  • 適応性：確率分布が未知または非定常の場合、適応モデル（オンライン更新）や普遍的符号化が有効です。

実世界での応用例

  • 画像圧縮：JPEG（DCT + 量子化 + エントロピー符号化）、JPEG2000（ウェーブレット変換）
  • 音声・音楽圧縮：MP3/AAC（MDCT + 量子化 + ハフマン/算術符号化）
  • 動画：H.264/H.265（予測・変換・量子化・コンテキスト適応算術符号化CABAC）
  • 汎用圧縮：gzip（LZ77 + ハフマン）、bzip2（ブロックソート+ハフマン）、zstd（LZ + Huffman + ANS 等）

まとめ：設計の観点と将来展望

ソース符号化は理論（エントロピー、レート-ゆがみ）と実装（ハフマン、算術、ANS、LZ系）の双方が重要です。良い符号化は優れた確率モデルと適切なアルゴリズムの組み合わせによって得られます。近年はニューラル符号化（学習ベースの生成モデルやエンドツーエンド圧縮）が注目を集めており、特に非可逆符号化分野で実用化が進んでいます。また、ANSのような新しい算術的手法は実用面での性能を改善し続けています。

参考文献

カテゴリー
IT
前の記事
ハフマン符号化の原理と実装 — 最適符号化、変種、実用上の注意点
2025年12月12日
次の記事
音楽制作におけるプラグイン完全ガイド：形式・使い方・音質改善テクニックと注意点
2025年12月12日