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 年代に主要特許が失効し、現在は広く利用可能です。
| 方式 | 年 | 符号長 | エントロピー乖離 | 用途 |
|---|---|---|---|---|
| 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 |
算術符号化は 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 の最適化で活用される傾向。
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 進算術符号化の拡張版。コンテキスト依存で確率モデルを動的調整、圧縮率を更に向上。