> 算術符号化 | 分数ビット | 最適 <
// 算術符号化 - エントロピー限界に近づく分数ビット符号化
ほぼ最適
圧縮効率のために理論上のエントロピー限界にきわめて近づきます。
分数ビット
確率に基づいて、記号を分数ビットで符号化します。
ストリーミング
データが到着するのに合わせて逐次エンコード／デコードできます。
>> 技術情報
算術符号化の仕組み:
算術符号化では、メッセージ全体を区間 [0,1) 内の 1 つの数として表現します。各記号は、その確率に応じてこの区間を狭めます。最終的な区間を 2 進分数として符号化することで、エントロピー限界に非常に近い圧縮を実現します。
エンコード手順:
テキスト: "AAB" 確率: A=0.67, B=0.33 1. 開始: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) 出力: [0.30, 0.45) の任意の数 2 進数: 0.010011...
算術符号化を使う理由:
- >高い圧縮率
- >エントロピー限界に近づく性能
- >任意の確率分布に対応
- >JPEG2000 や H.264 などで利用
- >特許切れ（2024 年）
>> よくある質問
算術符号化とは何ですか？
算術符号化は、記号列を 1 つの分数値に変換するエントロピー符号化の一種です。整数ビットだけを使うハフマン符号化とは異なり、算術符号化では 1 記号あたり分数ビットを使用できます.
なぜハフマン符号より優れているのですか？
算術符号化は、圧縮率をエントロピー限界に任意に近づけることができますが、ハフマン符号化は 1 記号あたり整数ビットに制限されます。確率分布が偏っている場合、算術符号化の方が大幅に有利になります。
精度パラメータとは何ですか？
精度は内部計算に使用するビット数を制御します。精度を高くするとより長いメッセージを符号化できますが、その分メモリも多く必要です。短いテキストには通常 16 ビットで十分です。
算術符号化はどこで使われていますか？
算術符号化は、H.264/H.265 ビデオ、JPEG2000 画像、ZIP の DEFLATE64 モードなどの最新の圧縮規格で使用されています。かつては特許で制限されていましたが、主要な特許はすでに失効しています。
// 計算例
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// コード例
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> その他の質問
Q: 算術符号化がハフマン符号化より優れていることが多いのはなぜですか？
A: ハフマン符号は各記号に整数ビット（最低1）を割り当てます。算術符号化はメッセージ全体を [0, 1) の1つの分数として符号化するためエントロピーに近づき、確率50%超の記号でもハフマンでは1ビットかかる場面を改善できます。
Q: ABCの区間の例はどう動作しますか？
A: A=0.5、B=0.25、C=0.25とすると、記号ごとに区間が狭まります：[0,1) → [0,0.5) → [0.25, 0.375) → [0.34375, 0.375)。この中の任意の数、たとえば2進で0.01011（=0.34375）が「ABC」を5ビット、つまりエントロピーちょうどで表します。
Q: 算術符号化はどこで使われていますか？
A: H.264/HEVCのCABAC、JPEG 2000やJBIG2のMQコーダー、range coding（AV1）やANS（zstd、JPEG XL）などの派生方式です。初期の特許が普及を妨げましたが、現在は多くが失効しています。