5.1 資訊熵與編碼理論#

概念說明#

1948 年 Claude Shannon 發表《A Mathematical Theory of Communication》，為「資訊」下了可度量的定義：一個機率 p 的事件攜帶的資訊量是 −log₂ p 位元——越不可能的事，發生了越有資訊。整個符號源的資訊熵（entropy）定義為各符號資訊量的期望值：

H(X) = −Σ p(x) · log₂ p(x)　（單位：位元/符號）

熵直觀上是「平均不確定性」：擲公正硬幣的熵是 1 位元；若某符號機率為 1（完全確定），熵為 0。對文字而言，熵給出了無損壓縮的極限：任何把每個符號獨立編碼的方法，平均長度都不可能低於 H(X)。例如一個 4 符號源機率 {0.5, 0.25, 0.125, 0.125} 的熵恰為 1.75 位元/符號——機率是 2 的負次冪時，恰好能用 1、2、3、3 位元的編碼達成。

可唯一解碼與前綴碼（prefix code）：若一個編碼中沒有任何碼字是另一碼字的前綴，則解碼時讀到碼字末尾即可確定邊界，不需分隔符。等長編碼（如 ASCII 8 位元）當然可解碼但浪費；變長編碼必須是前綴碼才安全。前綴碼有個美麗的資料結構對應：二叉樹——碼字是根到葉的路徑（0 往左、1 往右），前綴性質等價於「碼字只能放在葉子上」。

Kraft 不等式刻畫了前綴碼的存在條件：Σ 2^(−lᵢ) ≤ 1（lᵢ 為各碼字長度）。它告訴我們哪些長度組合可行：{1,2,3,3} 時 1/2+1/4+1/8+1/8 = 1，恰好填滿二叉樹。Shuffman 之前，Shannon 與 Fano 已提出 Shannon-Fano 編碼，但它在某些機率下達不到最佳；Huffman（1952）證明其貪婪法在「符號獨立、機率已知」的前提下給出最佳前綴碼，平均長度滿足 H(X) ≤ L < H(X)+1。

對真實文字，還有兩個重要事實：其一，一階（單字元）熵遠非文字的真實壓縮極限——考慮條件熵 H(X|Y)（已知前一符號後的不確定性）通常低得多，這是上下文建模（如 PPM、神經語言模型）能超越單字元統計的原因；其二，英文文字的一階熵約 4.1～4.5 位元/字元，而加入上下文後可低於 2，大型語言模型甚至能逼近 1 位元以下——壓縮與預測在本質上是同一件事。

演算法步驟#

統計輸入中每個符號的出現次數，計算機率 pᵢ = nᵢ / n。
計算熵 H = −Σ pᵢ log₂ pᵢ，作為壓縮比的天花板參考。
檢查碼長設計：欲用的碼長 lᵢ 是否滿足 Kraft 不等式 Σ 2^(−lᵢ) ≤ 1。
（下一節）用 Huffman 貪婪法產生滿足 Kraft 等式的最佳碼長。

Python 程式碼範例#

import math
from collections import Counter

def entropy(text):
    n = len(text)
    cnt = Counter(text)
    return -sum(c / n * math.log2(c / n) for c in cnt.values())

def kraft(lengths):
    return sum(2.0 ** -l for l in lengths)

zh = "喜馬拉雅山是亞洲的高山，喜馬拉雅山脈綿延數千公里。"
en = "the algorithm processes the string with the algorithm"

for name, s in [("中文", zh), ("英文", en)]:
    H = entropy(s)
    fixed = 8 if False else math.ceil(math.log2(len(Counter(s))))  # 等長編碼
    print(f"{name}: {len(s)} 符號, {len(Counter(s))} 種字元, "
          f"熵={H:.2f} bits, 等長編碼={fixed} bits, "
          f"ASCII 原始=8 bits")
# 熵明顯低於等長編碼 => 有壓縮空間

print(kraft([1, 2, 3, 3]))   # 1.0  可行（剛好填滿）
print(kraft([1, 1, 3, 3]))   # 1.25 不可行（會撞前綴）

複雜度分析#

熵計算：O(n + |Σ|)（Counter 統計 + 一次加總）。
理論意義：熵是壓縮比下界的「量尺」；等長編碼需 ⌈log₂|Σ|⌉ 位元，熵更低表示可省 log₂|Σ| − H 位元/符號。
延伸複雜度：條件熵估計需維護上下文計數表，成本 O(n × 上下文階數)。

練習#

對中、英文各取一段 1000 字以上的真實文字，計算一階熵；再以「前一個字元」為上下文計算二階條件熵，比較兩者差距並解釋原因。
證明（手寫推導）：若四符號機率為 {0.5, 0.25, 0.125, 0.125}，碼長 {1,2,3,3} 的平均長度恰等於熵；再舉一組機率使任何前綴碼的平均長度都嚴格大於熵。
實作 Shannon-Fano 編碼（遞迴把符號按機率切成兩半），與下一節的 Huffman 在同一份文字上比較平均碼長，找出一個 Shannon-Fano 非最佳的例子。