> 算術編碼 | 分數位 | 最佳化 <
// 算術編碼 - 使用分數位元、接近資訊熵極限的編碼
接近最佳
壓縮效率接近理論上的資訊熵極限。
分數位元
依據符號機率使用分數位元進行編碼。
串流處理
可在資料抵達時逐步編碼與解碼。
>> 技術資訊
算術編碼的運作原理:
算術編碼將整段訊息表示為 [0,1) 區間中的單一數值。每個符號會依其機率縮小該區間。最終得到的區間再以二進位小數形式編碼，達到非常接近熵極限的壓縮效果。
編碼流程範例:
文字: "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) 區間內的任意數值 二進位: 0.010011...
為什麼要使用算術編碼:
- >更高的壓縮比
- >接近資訊熵極限
- >支援任意機率分佈
- >應用於 JPEG2000、H.264 等標準
- >相關專利已到期（2024）
>> 常見問題
什麼是算術編碼？
算術編碼是一種熵編碼技術，會將一串符號轉換成單一分數值。不同於僅使用整數位元的 Huffman 編碼，算術編碼可以對每個符號使用分數位元。
為什麼它比 Huffman 更好？
算術編碼可以達到任意接近熵極限的壓縮效果，而 Huffman 編碼受限於每個符號必須使用整數個位元。在機率分佈高度偏斜的情況下，算術編碼通常有明顯優勢。
精度參數是什麼？
精度決定內部計算中使用的位元數。較高的精度可以編碼更長的訊息，但也需要更多記憶體。對於短文字，一般 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
>> 更多問題
問：為什麼算術編碼通常比霍夫曼編碼更好？
答：霍夫曼為每個符號分配整數個位元（至少 1 位）。算術編碼把整條訊息編碼為 [0, 1) 內的一個分數，接近熵極限，即使機率超過 50% 的符號在霍夫曼下也要占 1 位。
問：ABC 區間範例是怎麼算的？
答：設 A=0.5、B=0.25、C=0.25，每個符號都會縮小區間：[0,1) → [0,0.5) → [0.25, 0.375) → [0.34375, 0.375)。區間內任一數，如二進位 0.01011（=0.34375），就能用 5 位元編碼「ABC」，恰為熵。
問：算術編碼用在哪裡？
答：用於 H.264/HEVC 的 CABAC、JPEG 2000 與 JBIG2 的 MQ 編碼器，以及 range coding（AV1）和 ANS（zstd、JPEG XL）等變體。早期專利曾阻礙普及，現在大多已過期。