5.3 算術編碼#

概念說明#

Huffman 編碼有個先天限制：每個符號至少占 1 個位元（碼是二叉樹上的整條路徑）。當某符號機率高達 0.9 時，理想碼長是 −log₂0.9 ≈ 0.15 位元，Huffman 卻只能給 1 位元，壓縮效率大跌。算術編碼（arithmetic coding）徹底跳脫「整數位元、一符號一碼」的框架：把整篇訊息編成一個 [0,1) 區間內的小數，訊息的機率越大，最終區間越寬，所需的小數位數越少——位元數可以精確到任意小數，理論平均長度可逼近熵的極限到幾個位元以內（Huffman 通常差到 1 位元以上）。

核心概念：[0,1) 依各符號機率按序切成子區間。編碼每讀一個符號，就把當前區間縮小到「該符號對應的子區間」內（區間寬度乘以該符號機率）。讀完全部符號後，輸出最終區間內任意一個用足夠位元表示的二進位小數。解碼時反向操作：持同一張機率表，看當前小數落在哪個子區間就推出哪個符號，然後把區間縮小、繼續。

例：符號 {a:0.5, b:0.3, c:0.2}，編 "ab"：初始 [0,1) → 讀 a 取 [0,0.5) → 讀 b 取 [0,0.5) 內的 b 段 [0.15,0.3) → 最終輸出 [0.15,0.3) 內的小數，如 0.001（0.125 也在內？不行，需落於 [0.15,0.3)，用 0.01₂=0.25 即可），共 2 位元，而理想資訊量是 −log₂(0.5×0.3) ≈ 2.74……此例位元數因對齊而略省；整體期望上，長訊息的位元數會收斂到 Σ −log₂ pᵢ。

實作上有兩大工程問題與解法：

浮點精度：區間會指數級縮小，浮點數幾十個符號就耗盡精度。解法：用固定整數寬度（如 32 位元）表示區間，每當區間頂端與底端最高位元相同，就輸出該位元並左移（區間重整 renormalization）；區間過窄時用 E3 條件（底下 1/4 的情況）計數 pending 位元。
自適應建模：機率表不必預先傳送——編解碼兩端用同一套自適應規則（如按已出現頻率即時更新），每編一個符號同步更新統計。這讓壓縮器能隨資料「學習」分布，也是現代壓縮（如 LZMA 的 context modeling、zstd 的 FSE）的共同思想。

算術編碼在 1980 年代由 Rissanen、Witten 等人工程化（CACM 1987 經典實作），曾因專利受限，2004 年後專利到期已自由使用；JPEG 的 QM-coder、H.264/H.265 的 CABAC、zstd 的 ANS 皆是其思想後裔。

演算法步驟（整數版概念流程）#

兩端共享機率模型：每個符號有累積機率區間 cum[c] ≤ x < cum[c]+p[c]，總寬 2^P。
初始化 low = 0、high = 2^P − 1。
對每個符號 c：把 [low, high] 縮到 cum 對應的子區間（子區間寬 = 當前寬 × p[c]）。
重整：若 [low, high] 完全落在上半（≥ 2^(P−1)）或下半（< 2^(P−1)），輸出最高位元（1 或 0），low、high 各左移一位並補 0/補 1；若落在中間 1/4 重疊區（E3），左移但記 pending，之後一次輸出「0 後接 pending 個 1」或反之。
全部符號編完後，輸出足夠定位 [low, high] 的位元。
解碼：維護同樣的 [low, high] 與一個「目前值」暫存器，每步比較值落在哪個符號子區間即輸出該符號並同步縮區間、重整。

Python 程式碼範例#

import math
from collections import Counter
from fractions import Fraction

def arithmetic_encode(text):
    """教學版：用 Fraction 展示區間概念（無精度問題，但非工程實作）"""
    cnt = Counter(text)
    n = len(text)
    probs = []
    cum = Fraction(0)
    table = {}
    for s, c in cnt.items():
        table[s] = (cum, cum + Fraction(c, n))
        cum += Fraction(c, n)
    low, high = Fraction(0), Fraction(1)
    for ch in text:
        width = high - low
        lo, hi = table[ch]
        high = low + width * hi
        low = low + width * lo
    return low, high, table

def bits_to_represent(low, high):
    """找最短二進位小數落於 [low, high)"""
    k = 1
    while True:
        m = Fraction(math.ceil(low * (1 << k)), 1 << k)   # 向上取整才可能 ≥ low
        if low <= m < high:
            return format(int(m * (1 << k)), f"0{k}b"), k
        k += 1

text = "banana"
low, high, table = arithmetic_encode(text)
bits, k = bits_to_represent(low, high)
print(f"理論資訊量: {-sum((c/len(text))*math.log2(c/len(text)) for c in Counter(text).values())*len(text):.2f} bits")
print("位元串:", bits)

複雜度分析#

時間：教學版每符號 O(|Σ|)（區間查表可用累積表二分到 O(log|Σ|)）；工程版每符號均攤 O(1)（重整均攤每位元一次）。
壓縮率：總位元數 < Σ −log₂ pᵢ + 2 位元——幾乎精確達到熵；對高偏斜分布（某符號 p→1）遠勝 Huffman。
空間：機率表 O(|Σ|)；自適應版與解碼端共用模型，免傳碼表。
代價：實作複雜（整數重整、E3 處理、位元 I/O）；專利歷史曾阻礙普及；單位元錯誤會毀掉其後整個訊息（區間一縮就回不來），對傳輸容錯較敏感。

練習#

把教學版延伸成自適應算術編碼：機率表初始為均勻，每編/解一個符號後兩端同步 +1 更新；驗證解碼正確，並在英文文本上比較「靜態表＋傳表」與「自適應免傳表」的總位元數。
手動推導：符號 {a:0.8, b:0.2} 編 "aaaa"，理想資訊量 0.64 位元；用教學版程式實際編出，觀察位元數與理想值的差距，並解釋為何 Huffman 在此例需要 5 位元。
研究 ANS（非對稱數字系統）：閱讀 zstd 的 tANS/FSE 簡介，寫 300 字說明它如何以更簡單的表格達到與算術編碼相近的壓縮率，這也是 zstd 快速普及的關鍵。