跳轉到

5.3 算術編碼與通用壓縮#

導言：兩個遺留問題，一次解決#

Huffman 編碼留下了兩個問題（5.2 節）：

  1. 整數碼長的浪費：極端分佈（ \(p = 0.99\) ）下每符號仍需至少 1 bit。
  2. 分佈未知：真實信源（文字、影像）的統計結構複雜且時變，無法預先知道 \(p_i\) 。

算術編碼（arithmetic coding）解決第一個問題——它把「編碼」變成「把訊息編成一個區間中的實數」，碼長可為任意小數，理論上無限逼近熵。通用壓縮（Lempel–Ziv 家族）解決第二個問題——不假設任何分佈，靠字典學習重複模式，漸近達到熵率。兩者合流於 DEFLATE（ZIP）、LZMA（7z）、Zstandard 等現代格式，構成今日數位世界的壓縮基礎設施。

算術編碼#

核心思想：區間細分#

依各符號機率把 \([0,1)\) 劃分為子區間；每編一個符號，就把當前區間縮小為「對應符號的那一段」。訊息 \(x_1 x_2 \cdots x_n\) 對應一個長度為 \(\prod_i p(x_i)\) 的區間。輸出該區間內任何一個以足夠位元表示的二進位小數。

編碼 \(n\) 個符號後，區間長度為 \(2^{-\sum I(x_i)}\) ；表示此區間需約

\[ \log_2 \frac{1}{\prod_i p(x_i)} = \sum_i -\log_2 p(x_i) = \text{累積自資訊} \]

個位元。碼長精確等於自資訊之和，沒有整數化浪費——這是算術編碼的數學本質：它實現了 2.2 節自資訊的逐符號加總。

例題：手算兩符號#

信源 \(p(a) = 0.8\) 、 \(p(b) = 0.2\) 。編碼訊息 ba：

步驟 區間（前） 符號 子區間 區間（後）
1 \([0, 1)\) \(b\) \(b\) 佔 \([0.8, 1.0)\) \([0.8, 1.0)\)
2 \([0.8, 1.0)\) \(a\) \(a\) 佔前 80% \([0.8, 0.96)\)

輸出區間 \([0.8, 0.96)\) 內的二進位小數： \(0.8 = 0.11001100\ldots_2\) ，取 4 位元 1100 \(= 0.75\) ？不行， \(0.75 < 0.8\) 。取 1101 \(= 0.8125 \in [0.8, 0.96)\) ✓。故碼為 1101，4 bits。

理論下界： \(I(b) + I(a) = -\log_2 0.2 - \log_2 0.8 = 2.322 + 0.322 = 2.644\) bits。實際 4 bits（需區間端點可分辨的整數位元），超額 1.36 bits——因為只編了 2 個符號，捨入損失大。隨訊息變長，超額趨於常數（約 2 bits），平均每符號趨近熵 \(H = 0.722\) bits。Huffman 對同分佈需每符號 1 bit（0/1），差距巨大。

實作：範圍編碼器#

直接操作無限精度小數不可行；實際用範圍編碼（Rissanen & Langdon, 1979；Witten–Neal–Cleary, 1987 的 CACM 實作）維護低位數（low）與範圍（range）的整數暫存器，逢進位輸出位元。複雜度 \(O(1)\) /符號，配合上下文模型 \(p(x_i \mid \text{上文})\) ，即得逼近熵率的自適應壓縮器。

上下文模型：把條件熵吃乾抹淨#

英文的熵率約 1.5 bits/字母（3.2 節），遠低於單符號熵 4.18。實現：用前 \(k\) 個符號（或前 \(k\) 個字）作為上下文，對每個上下文維護自己的符號機率表（隨資料學習），算術編碼器以這些條件機率驅動。PPM（Prediction by Partial Matching, 1984）是經典實作；現代語言模型 + 算術編碼 = 最先進壓縮器——2020 年代的 lm-based 壓縮（如 ts_zip）已把英文壓到約 0.7 bits/字母。壓縮即預測，預測即模型——這是本節最深的一句話。

通用壓縮：Lempel–Ziv 家族#

動機：免模型的壓縮#

算術編碼仍需一個機率模型。1977–1978 年，以色列電機學者 Abraham Lempel 與 Jacob Ziv 提出完全不建模的方案：

  • LZ77（1977）：滑動視窗字典。輸出（偏移、長度、下一字元）三元組，指向「前面出現過的同款字串」。
  • LZ78（1978）：顯式字典樹，逐條目學習新片語。
  • LZW（Welch, 1984）：LZ78 的改良（先輸出後學習），用於 GIF、UNIX compress。

例題：LZ77 壓縮#

字串 abracadabra，滑窗內容逐步匹配：

位置 已編碼 當前片段 字典匹配 輸出
1 — a 無 (0,0,a)
2 a b 無 (0,0,b)
3 ab r 無 (0,0,r)
4 abr a 位置1 a (3,1,c)
6 abrac ad 無 (0,0,a)+...

第二個 abra（位置 8 起）完全比中位置 1 的 abra：輸出 (7, 4, 結束)。原本 11 字元壓成約 6 個 token——重複結構被字典捕捉，無需任何機率模型。

定理：LZ 的漸近最優性#

Ziv 與 Lempel 證明（1977、1978；Wyner–Ziv 1989 給出機率論證）：對平穩遍歷信源，LZ78 的每符號壓縮率幾乎必然收斂到熵率 \(H(\mathcal{X})\) ：

\[ \lim_{n \to \infty} \frac{\text{壓縮長度}}{n} = H(\mathcal{X}) \]

不需要知道信源模型，只要信源是平穩遍歷的，LZ 就漸近最優。這是「通用（universal）」一詞的含義：一個演算法同時對所有平穩信源漸近最佳。這個定理使壓縮軟體可以盲目工作（不知道是英文、日文還是機器碼）而仍然有效。

LZ 與 Kolmogorov 複雜度#

LZ 的壓縮率是演算法資訊量的可行上界：Kolmogorov 複雜度 \(K(x)\) （最短描述長度，10.3 節）不可計算，LZ 是可計算的近似。機器學習中的「LZ 距離」被用於 DNA 序列與文本的無模型相似度度量。

DEFLATE：兩者合流#

1991–1993 年 Phil Katz 在 PKZIP 中定義 DEFLATE = LZ77 + Huffman：

  1. LZ77 把字串化為（偏移、長度）對與字面值。
  2. 對這些符號套 Huffman 編碼（利用其頻率不均）。
  3. 碼表本身再用 Huffman 壓縮。

DEFLATE 是 ZIP、gzip、PNG 的核心。後繼者：

格式/工具 年代 演算法 特點
compress (LZW) 1985 LZ78 系 GIF 同款，專利爭議
DEFLATE 1993 LZ77 + Huffman 開放無專利、無所不在
LZMA (7z) 1998 大字典 LZ + 範圍編碼 高壓縮率
Brotli 2015 LZ + 上下文混合 + 範圍編碼 網頁傳輸
Zstandard 2016 LZ + FSE（ANS） 兼顧速度與比率（10.3 節 ANS）

歷史前因後果#

誰、何時、為什麼#

  • 1948 Shannon：熵與極限（一切的前提）。
  • 1949 Huffman：整數碼長最優（5.2 節）。
  • 1968 Kolmogorov：演算法資訊理論，提出「最短描述」的哲學目標。
  • 1976 Rissanen（Jorma）：算術編碼的理論化（後續 1979 與 Langdon 落地）；同一人提出 MDL（最小描述長度）統計推論原則。
  • 1977–1978 Lempel–Ziv：免模型字典壓縮與通用性定理。
  • 1984 Welch：LZW 標準化（後因 Unisys 專利引發 1994 年 GIF 危機，間接促成 PNG 誕生——資訊理論史上的法律插曲）。
  • 1987 Witten–Neal–Cleary：算術編碼的經典實作論文。
  • 1993 Katz：DEFLATE，壓縮界的 HTTP。
  • 2007–2014 Duda：ANS（非對稱數字系統），把算術編碼的速度問題解決。

解決了什麼問題#

  1. 最後 1 bit：算術編碼消滅整數碼長浪費，逼近條件熵率。
  2. 免模型：LZ 讓壓縮器對未知信源漸近最優。
  3. 普及：DEFLATE 等格式使壓縮成為作業系統與網路的預設功能——沒有它，全球網路流量將多出數倍。

引發什麼新問題#

  1. 上下文爆炸：高階上下文模型記憶體指數成長——PPM 用逃脫機率、神經模型用嵌入向量緩解。
  2. 專利與開放：LZW 與算術編碼早期專利（IBM）推動了範圍編碼與 ANS 的誕生——法律塑造演算法史。
  3. 壓縮與學習的統一：AIXI 與 Solomonoff 歸納（10.3 節）把「最佳壓縮 = 最佳預測 = 通用智慧」推到極限，是理論與哲學的交界。
  4. 神經壓縮：2018–2026 年間語言模型成為最強的壓縮前處理器，「壓縮即智慧」由口號變成工程。

與其他領域的關聯#

機率與統計#

算術編碼的每一步是條件機率的逐點應用（2.3 節）；上下文模型的學習是線上統計估計；MDL 把模型選擇化為「模型描述長度 + 資料殘差編碼長度」的資訊準則（10.3 節）。

演算法與資料結構#

LZ77 需要字串匹配資料結構（後綴樹、雜湊表）；Ziv–Lempel 定理的證明用組合計數（不同字串模式的成長率 ≤ 指數 \(nH\) ，即 3.1 節典型集的組合版）。

計算理論#

Kolmogorov 複雜度、Chaitin 不完備定理（Ω 常數）、Solomonoff 先驗——演算法資訊理論把壓縮、證明與歸納統一（10.3 節）。

神經科學與語言#

「壓縮即理解」假說（Hutter Prize 以壓縮維基百科為智慧測試）；人類語言的層級結構使熵率遠低於字母熵（3.2 節），神經語言模型正是學這個層級結構。

小結與思考題#

算術編碼把「碼長 = 自資訊之和」變成精確實現；LZ 家族證明免模型也可漸近最優；兩者合流為現代壓縮基礎設施。壓縮的終點不是演算法，而是預測——誰能更好地預測下一個符號，誰就壓得更小。

思考題

  1. 用 \(p(a) = 0.8, p(b) = 0.2\) 編碼 ab：算出最終區間與碼，並與 \(I(a) + I(b)\) 比較。
  2. 對字串 abababab 做 LZ77，估計壓縮率；為什麼純 Huffman 對此字串效果差？
  3. 證明（概述）：LZ78 的字典條目數 \(c(n)\) 滿足 \(c(n) \log c(n) \le n\) （用 Kraft 式的計數論證），從而得到壓縮率上界。
  4. 為什麼「語言模型 + 算術編碼」是目前最強的文字壓縮器？熵率的角度（3.2 節英文 1.3–1.5 bits）如何支持這一點？
  5. ANS 為什麼能兼顧算術編碼的效率與 Huffman 的速度？（提示：表驅動、單狀態機。）

第 5 章完成。下一章轉向通道編碼——資訊送出去之後，如何對抗雜訊。