算術符号化とは？基礎原理から実装のコツまで詳解
エバープレイ編集部算術符号化とは — 概要
算術符号化（Arithmetic Coding）は、情報理論に基づく可逆圧縮手法の一つで、符号語を「固定長の記号列」ではなく、区間（実数区間）を段階的に狭めて符号化する方式です。各入力シンボルが現れる確率分布に基づいて区間を分割し、最終的に得られた狭い区間内の任意の値（通常はその値の2進表現）をビット列として出力します。
なぜ有効か（直感的な説明）
情報量（エントロピー）に近づく効率的な符号化が可能です。各シンボルに対して割り当てられる平均ビット長は、そのシンボルの -log2(確率) に近づきます。ハフマン符号のようなシンボル単位の整数ビット割当（例えば 1 ビット、2 ビット、…）よりも高い柔軟性を持ち、確率が多数の小数点以下にまたがる場合でもエントロピーにより近い圧縮率を実現できます。
基本原理（数学的な概念）
算術符号化は次のように動作します。
- 記号集合 S と、それぞれの記号 s∈S の確率 p(s)（または周波数）を用意する。
- 区間 [0,1) を各記号の確率に比例して分割する。例えば S={A,B,C} で p(A)=0.6, p(B)=0.2, p(C)=0.2 なら、A→[0,0.6), B→[0.6,0.8), C→[0.8,1.0)（累積分布の形で表現）。
- 入力シーケンスの先頭から順に、現在の区間を選ばれた記号に対応する部分区間に更新していく。各ステップで区間の幅は前の幅にその記号の確率を掛けたものになる。
- 全シーケンスを処理した後に得られる狭い区間内の任意の値の2進表現を出力する。デコーダはこのビット列から元の区間を再現し、確率分布を追跡して元のシンボル列を復元する。
簡単な数値例
例：S={A,B,C}、p(A)=0.6、p(B)=0.2、p(C)=0.2 を考え、文字列「AB」を符号化する。
- 開始区間は [0,1)。最初にAを読むと、Aに対応する部分区間は [0,0.6)。（累積確率により分割）
- 次にBを読む。現在の区間 [0,0.6) をさらに A,B,C の比率（0.6,0.2,0.2）で分割する。B に対応する部分は下端から 0.6*0.6 = 0.36、上端は 0.6*0.8 = 0.48 なので、新しい区間は [0.36,0.48)。
- よって「AB」は区間 [0.36,0.48) に対応します。この区間内の任意の実数（例えば0.4）の2進表現を使えば復号可能です。
デコーディングの流れ
デコーダはビット列を順に読み取り、現在の区間幅と累積確率を使って、ビット列が表す実数がどの記号の部分区間に入るかを判定して記号を決定します。符号化時と同じ確率モデル（静的なら事前共有、適応なら逐次更新）を使用して区間の分割を同じ手順で追跡することで完全復元が可能です。
実装上の注意点（精度、正規化、アンダーフロー）
理論上は実数での区間分割ですが、実装では無限精度は使えないため、以下の工夫が必須です。
- 整数演算への置き換え：浮動小数点の丸め誤差を避けるため、区間を大きな整数レンジ（例えば 0 〜 2^32−1）で管理する「整数算術」を用いるのが一般的です。
- 正規化（renormalization）：上位ビットが確定したときにそのビットを出力し、残りのビット列を左シフトしてレンジを拡張する操作を繰り返します。これによりレジスタのオーバーフローを防ぎながら逐次出力できます。
- アンダーフロー（underflow）処理：low と high が中央部分で反転・接近する「半分をまたぐ」状況（いわゆる E3 条件）に対する保留ビットの扱いが必要です。典型的な実装では「保留ビット」を記録し、後続の確定ビットが出たときにまとめて反転出力する方式が採られます。
- レンジ符号化（range coding）：算術符号化の実装上の複雑さ（大きな整数管理やアンダーフロー処理）を簡素化した実装手法として「レンジ符号化」がよく使われます。圧縮率は同等で、実装が高速・単純という利点があります。
モデル（確率の扱い）
算術符号化自体はあくまでエンコーディング手法であり、圧縮率は確率モデル（シンボルの出現確率の推定）に依存します。主なモデルは：
- 静的モデル：ファイル全体の統計を事前に計算し、それを符号化・復号で共有する方式。前処理が必要だが復号時は簡潔。
- 適応モデル：符号化と同時に統計を更新する方式。事前知識不要で通常はより実用的。エンコーダとデコーダは同じ更新手順を同期して行う必要がある。
- 文脈モデル（コンテキストモデリング）：直前のシンボル列から条件付き確率を推定することで、より高い圧縮効率を得る。JPEG2000 や H.264 の CABAC などでは高度な文脈モデルと組み合わせて高性能を実現している。
利点と欠点
- 利点
- 理論上エントロピーに非常に近い圧縮が可能（ハフマンより有利なことが多い）。
- 任意精度での確率割当が可能なので細かい確率差を活かせる。
- 適応モデルや文脈モデルと組み合わせることで非常に高い圧縮効率を得られる。
- 欠点
- 実装がやや複雑（正規化・アンダーフロー処理など）。
- 誤りに弱い：ビット誤りや同期のズレが生じると復号が全く追随できなくなる場合がある（誤り伝播が大きい）。
- 一時期、特許の問題で広く使われなかった経緯がある（現在は多くの実装で問題にならない）。
実世界での利用例
- 静止画像・映像符号化：JPEG2000（画像符号化）、H.264/AVC や H.265/HEVC の CABAC（Context-adaptive binary arithmetic coding）などで使われ、伝統的なハフマンより高効率を提供します。
- 文書符号化：JBIG2（白黒画像圧縮）では算術符号化が採用されている例があります。
- 汎用圧縮ライブラリ：一部の圧縮ツールや学術実装でレンジ符号化／算術符号化が参照実装として使われます。
実装のヒント（実務向け）
- まずは説明用の浮動小数点によるシンプル実装で動作原理を理解する。その後、実用化には整数ベースのレンジ符号化実装へ移行する。
- 適応モデルを使う場合はエンコーダ・デコーダの更新ルールを厳密に一致させる。累積頻度のオーバーフロー回避（スケーリング）が必要になる。
- 高速化のためにテーブル参照や量子化技術を使う例があるが、精度と設計のトレードオフに注意する。
まとめ
算術符号化は、確率モデルに基づいて区間を逐次狭めることで非常に効率的な可逆圧縮を実現する手法です。理論的な圧縮限界（エントロピー）に近づける柔軟性を持ち、特に文脈モデルや適応モデルと組み合わせることで高性能を発揮します。一方で実装の複雑さや誤りに対する脆弱性、かつての特許問題など実運用での考慮点もあります。近年はレンジ符号化などの実装容易な派生や、映像符号化（CABAC 等）での利用により広く採用されています。
参考文献
- 算術符号化 — Wikipedia（日本語）
- Arithmetic coding — Wikipedia (English)
- Context-adaptive binary arithmetic coding (CABAC) — Wikipedia
- Range coding — Wikipedia
- JPEG 2000 (公式)
- 参考文献（Arithmetic coding の英語版 Wikipedia の文献節）
投稿者プロフィール
