# Entropy 學習筆記 - 資料壓縮
# 1. 課程概述
這份筆記整理自「資料壓縮」課程中 Entropy（熵） 單元的投影片，主標題為 Mathematical Preliminaries for Lossless Compression（無失真壓縮的數學預備知識），共 42 頁。
核心脈絡：
- 資訊理論（Information Theory） 由 Shannon（貝爾實驗室）提出，是無失真壓縮技術發展的理論基礎。
- 對資料建模（Modeling the data） 則是設計有效編碼方案的關鍵。
投影片先建立「資訊量該怎麼量化」這件事（自資訊、熵），再說明「了解資料的結構（模型）可以降低所需的編碼位元數」，最後銜接到「編碼（Coding）」的基本概念，為後面 Huffman、算術編碼等章節鋪路。
# 2. 自資訊（Self-information）
對事件 A（發生機率為 P (A)），我們想找一個函式 i (A) 來衡量這個事件包含的「資訊量（或驚異度、不確定性）」。
三個必須成立的假設
- i (A) ≥ 0：資訊量不能為負。
- 若 A、B 為兩個獨立事件，則 i (AB) = i (A) + i (B)（資訊量可加成）。
- i (A) 是連續且單調的函數：機率不同，i (A) 也不同。
推導出對數關係
若 p_A = p_B = p，則 i (p²) = 2×i (p)；一般化後可得 i (pⁿ) = n×i (p)。進一步推廣後，可得 i (y) = (m/n)×i (y^(n/m))，這正好符合對數函數的性質。因此定義：
i(A) = log_b(1/P(A)) = −log_b P(A)
為什麼用 −log？ 因為 log (1) = 0，且 −log (x) 隨 x 從 1 降到 0 而增加。這意味著：
- 事件發生機率越低，包含的自資訊越高（越意外）。
- 事件發生機率越高，包含的資訊越低（越不意外）。
- 例子：狗吆叫、「白銀馬」探案中夜間狗沒叫反而是關鍵線索（意外度高）。
兩個獨立事件的資訊量：若 A、B 獨立，則 P (AB)=P (A) P (B)，代入後可得 i (AB) = i (A) + i (B)，驗證了假設 2。
# 3. 資訊單位與拋硬幣範例
對數的底 b 決定了資訊量的單位：
| 底數 | 單位 |
|---|---|
| 2（預設） | bit |
| 3 | trit |
| e | nat（自然對數） |
| 10 | Hartley（紀念科學家 Ralph Hartley） |
課程若未特別說明底數，一律假設是 底數 2（bit）。
範例 2.2.1：拋硬幣
設 H = 正面、T = 反面：
- 公平硬幣：P (H) = P (T) = 1/2 → i (H) = i (T) = 1 bit。
- 不公平硬幣：P (H) = 1/8，P (T) = 7/8 → i (H) = 3 bits，i (T) ≈ 0.193 bits。
重點：不公平硬幣出現「正面」這種罕見結果時，攜帶的資訊量遠大於「反面」。這說明機率低的事件一旦發生，資訊量（意外程度）反而更高，之後編碼時應該給罕見符號分配較長的碼字、給常見符號較短的碼字。
# 4. 平均自資訊與熵（Entropy）的定義
設來自實驗 / 來源 S 的一組獨立事件 Aᵢ（聯合為樣本空間 S），定義其平均自資訊：
H = Σ P(Aᵢ) i(Aᵢ) = −Σ P(Aᵢ) log_b P(Aᵢ)
這個 H 就是 熵（Entropy）。如果來源的輸出符號集合為 A，熵就是：
- 對該來源輸出編碼時，平均每個符號所需的二進位元數（bits）下限。
- 實際事件並非永遠獨立，符號間可能存在依賴關係（下文的 Markov 模型就是處理這種情況）。
這個公式可以理解為：將每個符號的自資訊 i (Aᵢ) 依其發生機率 P (Aᵢ) 加權平均，得到整個來源平均而言每個符號攜帶的資訊量。
# 5. 熵的估計範例：建模如何降低熵
範例一：直接估計
數列： 1 2 3 2 3 4 5 4 5 6 7 8 9 8 9 10
估計各符號發生機率（P (1)=P (6)=P (7)=P (10)=1/16，P (2)=P (3)=P (4)=P (5)=P (8)=P (9)=2/16），假設序列為 iid（獨立同分佈），算出熵 ≈ 3.25 bits / 符號。這也是目前最好編碼方案能達到的上限。
範例二：利用結構建模（取相鄰差值）
將相鄰符號相減得到殘差序列： 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 ，只有兩種值（P (1)=13/16、P (-1)=3/16），熵降到 0.70 bits / 符號。這說明：知道資料的結構（模型）可以大幅降低熵。（注：接收方還需知道建模方式 xn = xn−1 + rn 才能還原，這種參數固定的模型稱為 靜態模型）。
範例三：以區塊（block）降低熵
序列： 1 2 1 2 3 3 3 3 1 2 3 3 3 3 1 2 3 3 1 2 ，P (1)=P (2)=1/4、P (3)=1/2，單符號熵 = 1.5 bits。若以兩兩一組分組（12、12、33、33...），P (12)=P (33)=1/2，熵降為 1 bit / 組（即每個符號 0.5 bit）。
小結：三個範例都在說明同一件事 —— 對資料結構的假設（模型）越準確，所估計出來的熵就越低，也就能壓縮得越小。
# 6. 長序列與 n-tuple 熵的收斂
為了捕捉符號之間的依賴關係，可以看「長度 n 的序列」的聯合分佈。課程以三本書（Peter Pan、The Communist Manifesto、The Wealth of Nations）為例，列出 n=1,2,3,10 時最常見的字母序列：
- n 很小時（如 n=1,2）：只能看到英文語言本身的共通結構（如 the、of 等常用字），三本書很難區別。
- n 增大到 10 時：已可進一步辨識出是哪一本書（如 bourgeoisie 對應 Manifesto），即捕捉到更多特定文本的結構。
形式化定義
定義 n 元組的聯合資訊量：
Gn = −Σ…Σ P(X₁=i₁,…,Xn=in) log P(X₁=i₁,…,Xn=in)
每字平均資訊量 Hn = Gn /n。將 Wealth of Nations 的 Hn 對 n=1~12 作圖，會發現 Hn 隨 n 增加而逐漸收斂到一個固定值。Shannon 證明，對 穩定來源（stationary source） 而言，這個極限就是真正的熵：
H(S) = lim(n→∞) (1/n) Hn
若序列是 iid（獨立同分佈），則可簡化為 Gn = n × 單符號熵，進而得到熟悉的式子：H(S) = −Σ P(X₁) log P(X₁)，與第 4 節的定義一致。
# 7. 熵的重要性質
性質一：均勻分佈時熵最大
- 公平硬幣：熵 = 1/2×log₂(2) + 1/2×log₂(2) = 1 bit（最大可能的熵）。
- 假硬幣（P (H)=1/8，P (T)=7/8）：熵 = 1/8×log₂(8) + 7/8×log₂(8/7) ≈ 0.54 bits，比公平硬幣低。
結論：事件發生機率越均勻（不確定性越高），熵就越大；相反，若分佈們偏向某一值，熵就會變小。
性質二：Kraft 不等式與熵的下限意義
對於 瞬時、唯一可解碼碼（instantaneous uniquely decodable code） 而言，平均碼長一定大於或等於熵。換句話說：
對於無失真壓縮而言，熵是理論上能達到的最佳（最短）平均編碼長度，任何無損編碼方法都無法突破這個下限。
這就是編碼理論（變長碼、Huffman、算術編碼等後續章節）想要逐步逼近的目標。
# 8. 資料模型：機率模型 vs Markov 模型
要估計真實熵，需先對資料的統計特性做經驗觀察並建立模型，常見分類：
- 無知模型（ignorance model）：假設所有符號機率相等。
- 機率模型（probability model）：假設符號互相獨立，但機率不同。
- Markov 模型：假設符號間彼此依賴。
Markov 模型基礎（以俄國數學家 Andrei Markov, 1856–1922 命名）：
k 階 Markov 模型：P (xn | xn−1,…,xn−k) = P (xn | xn−1,…,xn−k,…)
意思是：只需知道前 k 個符號，就等同於知道整個過去歷史。最常用的是 一階 Markov 模型（只看前一個符號）。
範例：二元影像（白 / 黑像素）
定義兩個狀態 Sw（白）、Sb（黑），並定義轉移機率 P (w|b)、P (b|w)。整個有限狀態過程的熵為各狀態熵的加權平均：H = Σ P(Si) H(Si)。
範例 2.3.1（數值比較：機率模型 vs Markov 模型）
已知 P (Sw)=30/31、P (Sb)=1/31，P (w|w)=0.99、P (b|w)=0.01、P (b|b)=0.7、P (w|b)=0.3：
| 方法 | 計算 | 熵 |
|---|---|---|
| 機率模型（iid 假設） | −0.8log0.8 − 0.2log0.2 | 0.206 bits |
| Markov 模型（H (Sb)） | −0.3log0.3 − 0.7log0.7 | 0.881 bits |
| Markov 模型（H (Sw)） | −0.01log0.01 − 0.99log0.99 | 0.081 bits |
| Markov 模型綜合 | 加權平均 | 0.107 bits |
關鍵發現：利用 Markov 模型考慮符號依賴性後，熵從 0.206 bits 降到 0.107 bits，約為 iid 假設的一半。這再次驗證了：越好的模型（越能描述資料真實結構），估計出的熵就越低，壓縮效果也就越好。
# 9. 編碼基礎：碼字、唯一可解碼與前綴碼
基本名詞
- 碼（code）：將字母表（alphabet）中的符號對應到二進位序列的對應關係。
- 碼字（codeword）：每個字母對應到的二進位序列。
範例：四個字母的四種碼（P (a₁)=1/2、P (a₂)=1/4、P (a₃)=P (a₄)=1/8，熵 = 1.75 bits）
| 字母 | 碼 1 | 碼 2 | 碼 3 | 碼 4 |
|---|---|---|---|---|
| a₁ | 0 | 0 | 0 | 0 |
| a₂ | 0 | 1 | 10 | 01 |
| a₃ | 1 | 00 | 110 | 011 |
| a₄ | 10 | 11 | 111 | 0111 |
| 平均碼長 | 1.125 | 1.25 | 1.75 | 1.875 |
雖然碼 1 平均碼長最短，但 a₁、a₂ 都是 0，收到 0 時無法分辨 —— 不是唯一可解碼（碼 2 同樣不行）。
碼 3（瞬時碼）：0 總是代表碼字結束，解碼方可立即知道一個碼字已完成。
碼 4（幾乎瞬時）：只有碼字開頭才出現 0，需等到下一個碼字開始才知道上一個已結束。
碼 5（唯一可解但非瞬時）：a₁=0、a₂=01、a₃=11。雖非瞬時，但仍可唯一解碼（規則：累積位元直到看到 0，0 前一位是上一個碼字的最後一位）。
前綴碼（prefix code）：若任一碼字都不是別的碼字的前綴，就是前綴碼。前綴碼必定是瞬時碼，可以用二進樹（binary tree）表示：從根節點出發，左步 0、右步 1，碼字只對應到外部節點（葉子，無子節點），而非內部節點。
# 10. 唯一可解碼測試與 Kraft-McMillan 不等式
懸域後綴（dangling suffix）測試步驟
- 列出所有碼字。
- 檢查每對碼字，看是否有一個是另一個的前綴；若是，將剩下部分（懸域後綴）加入清單。
- 重複此過程，直到：
- 出現一個懸域後綴本身就是碼字 → 不是唯一可解碼（如碼 6：a₁=0、a₂=01、a₃=10，最終會得到碼字 0）。
- 不再有新的懸域後綴出現 → 是唯一可解碼（如碼 5：a₁=0、a₂=01、a₃=11，最終只循環出現 1）。
Kraft-McMillan 不等式
對任何非前綴但唯一可解碼的碼，都可以找到一個碼長完全相同的前綴碼來取代它。因此限制自己只用前綴碼並不會損失任何壓縮效率。形式化條件：
若碼 C 有 N 個碼字，長度分別為 l₁,…,l_N，若 C 為唯一可解碼，則：K(C) = Σ 2^(−lᵢ) ≤ 1
這是碼長設計的必要條件：若一組碼長滿足這個不等式，就一定存在對應的前綴碼。
# 重點總結
- 自資訊 i (A) = −log₂ P (A)：機率越低、資訊量越高。
- 熵 H = −Σ P (Aᵢ) log₂ P (Aᵢ)：來源的平均資訊量，也是編碼每符號所需位元數的理論下限。
- 建模越準確，估計出的熵就越低（殘差、分組、Markov 模型都是實例），壓縮效果也越好。
- 均勻分佈時熵最大，分佈越偏斜熵越小。
- 瞬時 / 唯一可解碼的平均碼長 ≥ 熵，熵是無損壓縮的理論極限。
- 前綴碼既能保證唯一可解碼又能瞬時解碼，而且不會牽制碼長（Kraft-McMillan 保證），所以實作上編碼器（如 Huffman）都只需考慮前綴碼。
這些概念是後續 Huffman 編碼、算術編碼等實際壓縮技術的理論基石。
