算術符号化 (Arithmetic Coding)（サンジュツフゴウカ）
1976 年に Jorma Rissanen が IBM Research で発明したエントロピー符号化アルゴリズム。Huffman 符号化が整数 bit でしか符号化できないのに対し、算術符号化は分数 bit で符号化可能で、理論的に Shannon エントロピー限界に最も近づく。
概要
算術符号化 (Arithmetic Coding) は、1976 年に Jorma Rissanen が IBM Research で発明したエントロピー符号化アルゴリズムで、Huffman 符号化 (1952) が整数 bit でしか符号化できないのに対し、算術符号化は分数 bit で符号化可能で、理論的に Shannon エントロピー限界に最も近づく特性を持ちます。入力文字列全体を [0, 1] の区間内の単一の実数で表現する革新的なアプローチで、各文字の出現確率に応じて区間を細分割しながら符号化を進めます。JPEG2000 (2000)・H.264 (CABAC、2003)・H.265 HEVC (2013)・H.266 VVC (2020) などの最新動画/画像コーデックで標準採用され、現代の高効率圧縮の中核技術となっています。IBM・Mitsubishi・AT&T・Sharp などが 1980-2000 年代に多数の特許を保有しており、特許問題で長年普及が妨げられましたが、2010 年代に主要特許が失効し、現在は広く利用可能です。
主な特徴・仕組み
- 発明: 1976 年 Jorma Rissanen (IBM Research San Jose Lab)
- 論文: "Generalized Kraft Inequality and Arithmetic Coding"
- 理論的根拠: Shannon エントロピーに対し損失 0 で漸近的に最適
- 符号化原理: 入力文字列を [0, 1] の単一実数で表現
- 区間分割: 各文字の確率に応じて [0, 1] を細分割、繰り返し
- 出力: 最終区間に含まれる任意の実数 (最短の 2 進表現)
- 適応的版: Adaptive Arithmetic Coding、確率モデルを動的更新
- CABAC: Context-Adaptive Binary Arithmetic Coding、H.264/H.265 で採用
- 計算量: Huffman より複雑、CPU 負荷高い
- 特許: 1980-2010 年代に多数、IBM・Mitsubishi・AT&T・Sharp 保有
スペック比較表 (エントロピー符号化)
| 方式 | 年 | 符号長 | エントロピー乖離 | 用途 |
|---|---|---|---|---|
| Huffman | 1952 | 整数 bit | エントロピー +1bit 以内 | ZIP/JPEG/MP3 |
| Arithmetic | 1976 | 分数 bit | ほぼエントロピー一致 | H.264/H.265/JPEG2000 |
| Range Coding | 1979 | 分数 bit | ほぼ Arithmetic 同等 | LZMA/7-Zip |
| ANS (Asymmetric Numeral Systems) | 2009 | 分数 bit | ほぼエントロピー一致 | Zstd/lz4 |
具体例・対応技術
- JPEG2000 (2000): EBCOT + Arithmetic、JPEG の後継だが特許で衰退
- H.264 CABAC (2003): Context-Adaptive Binary Arithmetic Coding、高圧縮プロファイル
- H.265 HEVC (2013): CABAC 改良版、Blu-ray UHD・4K ストリーミングで採用
- H.266 VVC (2020): 最新コーデック、CABAC 進化版で 50% 圧縮率向上
- PAQ シリーズ (2002-): 実験的高圧縮ツール、Arithmetic Coding 集大成
自作PCでの選び方・注意点
算術符号化は H.264/H.265/VVC 動画再生で内部的に動作し、4K/8K 動画視聴時の CPU 負荷の大部分を占めます。Intel/AMD/Apple の最新 CPU・GPU には H.265 HEVC ハードウェアデコード機能 (Intel QSV・NVIDIA NVDEC・Apple VideoToolbox) が標準搭載され、Arithmetic Coding 復号も含めてハードウェア処理されます。RTX 50 シリーズ・Intel Arc B シリーズ・Apple M4 などの 2024-2025 年世代 GPU は H.266 VVC ハードウェアデコード対応を進めており、CABAC 復号性能で次世代動画体験が決まります。AI モデル圧縮 (Qwen3-Embedding 等の埋め込み圧縮) でも Arithmetic Coding が研究されており、TensorRT・ONNX Runtime の最適化で活用される傾向。
関連用語との違い
- Huffman: 整数 bit 符号化、エントロピー +1bit、Arithmetic より低圧縮
- Range Coding: Arithmetic とほぼ等価、整数演算で実装容易 (LZMA で利用)
- ANS: 2009 年新世代、Arithmetic 競合、Zstd で実用化
よくある質問（FAQ）
Q1: Huffman と算術符号化の選択は? A: 高圧縮率最優先なら算術符号化、計算速度・実装容易性なら Huffman。動画/画像コーデックでは算術符号化、ZIP/gzip では Huffman が主流。
Q2: 特許問題は今も残ってる? A: 主要特許 (IBM・Mitsubishi 等) は 2010 年代に失効。現在は H.265/H.266 など現代コーデックで自由利用可能。
Q3: CABAC とは? A: Context-Adaptive Binary Arithmetic Coding、H.264/H.265 で採用される 2 進算術符号化の拡張版。コンテキスト依存で確率モデルを動的調整、圧縮率を更に向上。
まとめ
- 算術符号化 = 1976 年 Rissanen 発明、エントロピー限界に最も近い符号化
- 分数 bit 符号化、Huffman より高圧縮率
- JPEG2000/H.264 CABAC/H.265/H.266 で標準採用
- 特許失効 (2010 年代) で広く普及、現代動画/画像圧縮の中核