學習目標
- 理解霍夫曼編碼的原理和應用
- 掌握霍夫曼樹的建構過程
- 能夠根據字元頻率建立霍夫曼樹並產生編碼
- 理解霍夫曼編碼的優點和特點
1. 資料壓縮的基本概念
1.1 為什麼需要資料壓縮？
- 節省儲存空間: 減少檔案大小
- 節省傳輸時間: 減少網路傳輸時間
- 節省頻寬: 減少網路頻寬使用
1.2 編碼方式
固定長度編碼: 每個字元使用相同位元數 - 例如: ASCII 碼，每個字元 8 位元
可變長度編碼: 不同字元使用不同位元數 - 常用字元用較短編碼 - 不常用字元用較長編碼 - 目標: 總編碼長度最小
1.3 霍夫曼編碼
霍夫曼編碼 (Huffman Coding) 是一種無損資料壓縮演算法，根據字元出現的頻率，為每個字元分配一個可變長度的二進位編碼。
核心思想: 出現頻率高的字元使用較短的編碼，出現頻率低的字元使用較長的編碼。
2. 霍夫曼編碼的原理
2.1 基本步驟
- 統計頻率: 計算每個字元出現的頻率
- 建立節點: 為每個字元建立一個樹節點
- 建構霍夫曼樹: 重複合併頻率最小的兩個節點
- 產生編碼: 從根節點到葉節點的路徑即為編碼
- 編碼資料: 使用產生的編碼替換原始字元
2.2 霍夫曼樹的性質
- 二元樹: 每個節點最多有兩個子節點
- 葉節點: 代表原始字元
- 內部節點: 代表合併的節點，頻率為子節點頻率之和
- 前綴碼: 沒有任何編碼是另一個編碼的前綴（保證解碼唯一性）
3. 建構霍夫曼樹的詳細過程
3.1 範例 1: 基本範例
字元頻率: A(11), B(8), C(9), D(20), E(31), F(14), G(10)
步驟 1: 建立初始節點
將每個字元及其頻率視為一個獨立的樹節點（葉節點）：
A(11) B(8) C(9) D(20) E(31) F(14) G(10)
步驟 2: 第一次合併
選擇頻率最小的兩個節點：B(8) 和 C(9)
建立父節點，頻率 = 8 + 9 = 17
(17)
/ \
B(8) C(9)
剩餘節點：A(11), (17), D(20), E(31), F(14), G(10)
步驟 3: 第二次合併
選擇頻率最小的兩個：A(11) 和 G(10)
建立父節點，頻率 = 11 + 10 = 21
(21) (17)
/ \ / \
A(11) G(10) B(8) C(9)
剩餘節點：(21), (17), D(20), E(31), F(14)
步驟 4: 第三次合併
選擇頻率最小的兩個：(17) 和 F(14)
建立父節點，頻率 = 17 + 14 = 31
(31) (21)
/ \ / \
(17) F(14) A(11) G(10)
/ \
B(8) C(9)
剩餘節點：(31), (21), D(20), E(31)
步驟 5: 第四次合併
選擇頻率最小的兩個：(21) 和 D(20)
建立父節點，頻率 = 21 + 20 = 41
(41) (31)
/ \ / \
(21) D(20) (17) F(14)
/ \ / \
A(11) G(10) B(8) C(9)
剩餘節點：(41), (31), E(31)
步驟 6: 第五次合併
選擇頻率最小的兩個：(31) 和 E(31)
建立父節點，頻率 = 31 + 31 = 62
(62) (41)
/ \ / \
(31) E(31) (21) D(20)
/ \ / \
(17) F(14) A(11) G(10)
/ \
B(8) C(9)
剩餘節點：(62), (41)
步驟 7: 最後合併
合併最後兩個節點：(62) 和 (41)
建立根節點，頻率 = 62 + 41 = 103
(103)
/ \
(62) (41)
/ \ / \
(31) E(31)(21) D(20)
/ \ / \
(17) F(14) A(11) G(10)
/ \
B(8) C(9)
步驟 8: 標示邊緣並產生編碼
從根節點開始，為所有左分支標示為 0，右分支標示為 1：
(103)
0/ \1
(62) (41)
0/ \1 0/ \1
(31) E(31)(21) D(20)
0/ \1 0/ \1
(17)F(14)A(11)G(10)
0/ \1
B(8) C(9)
步驟 9: 產生編碼表
從根節點到每個葉節點的路徑：
| 字元 | 頻率 | 路徑 | 編碼 |
|---|---|---|---|
| E | 31 | 右 | 1 |
| D | 20 | 右右 | 11 |
| A | 11 | 右左右 | 101 |
| G | 10 | 右右右 | 111 |
| F | 14 | 右左左 | 100 |
| B | 8 | 左右左左 | 0100 |
| C | 9 | 左右左右 | 0101 |
3.2 範例 2: 等頻率字元
字元頻率: A(1), B(1), C(1), D(1), E(1), F(1), G(1), H(1), I(1), J(1)
當所有字元頻率相同時，會建立一個平衡的二元樹。
建構過程（簡化）
由於頻率都相同，可以任意選擇合併順序。最終會得到一個接近平衡的樹。
可能的編碼結果:
| 字元 | 編碼 | 字元 | 編碼 |
|---|---|---|---|
| A | 0000 |
F | 1000 |
| B | 0001 |
G | 1001 |
| C | 0010 |
H | 1010 |
| D | 0011 |
I | 1011 |
| E | 0100 |
J | 11 |
注意: 當頻率相同時，編碼長度可能不完全相同，但總長度會接近最優。
4. 編碼與解碼
4.1 編碼過程
使用編碼表將原始字串轉換為二進位編碼。
範例: 使用範例 1 的編碼表編碼字串 "EDD"
- E →
1 - D →
11 - D →
11
編碼結果: 11111
4.2 解碼過程
從左到右讀取編碼，根據霍夫曼樹進行解碼。
範例: 解碼 11111
- 讀取
1→ 對應到 E - 讀取
11→ 對應到 D - 讀取
11→ 對應到 D
解碼結果: "EDD"
注意: 由於霍夫曼編碼是前綴碼，解碼過程是唯一的。
5. 霍夫曼編碼的優點
5.1 最優前綴碼
在給定字元頻率的情況下，霍夫曼編碼產生的編碼長度總和是最小的（或接近最小）。
5.2 無損壓縮
解碼後可以完全還原原始資料，不會有任何損失。
5.3 適應性
可以根據實際資料的頻率分佈調整編碼，對不同類型的資料都有良好的壓縮效果。
5.4 前綴碼特性
沒有任何編碼是另一個編碼的前綴，保證了解碼的唯一性和正確性。
6. 霍夫曼編碼的缺點
6.1 需要頻率資訊
在編碼前需要先統計字元頻率，需要兩次掃描資料。
6.2 編碼表需要傳輸
解碼時需要知道編碼表，編碼表本身也需要儲存或傳輸。
6.3 對小資料集效果有限
如果資料量很小，編碼表的開銷可能大於壓縮節省的空間。
7. 複雜度分析
7.1 時間複雜度
- 建構霍夫曼樹: O(n log n)，其中 n 是不同字元的數量
- 編碼: O(m)，其中 m 是原始資料的長度
- 解碼: O(m)
7.2 空間複雜度
- 儲存霍夫曼樹: O(n)
- 編碼表: O(n)
8. 實際應用
8.1 檔案壓縮
- ZIP 檔案格式
- GZIP 壓縮
- 許多壓縮工具都使用霍夫曼編碼或其變體
8.2 影像壓縮
- JPEG 影像格式使用霍夫曼編碼
- 用於壓縮 DCT 係數
8.3 通訊協定
- 網路傳輸中的資料壓縮
- 減少傳輸時間和頻寬使用
9. 練習題
練習題 1
根據以下字元頻率建立霍夫曼樹並產生編碼： A(5), B(2), C(3), D(7), E(1)
解答：
步驟 1: 初始節點
A(5) B(2) C(3) D(7) E(1)
步驟 2: 合併 E(1) 和 B(2) → (3)
(3) A(5) C(3) D(7)
/ \
E(1) B(2)
步驟 3: 合併 (3) 和 C(3) → (6)
(6) A(5) D(7)
/ \
(3) C(3)
/ \
E(1) B(2)
步驟 4: 合併 A(5) 和 (6) → (11)
(11) D(7)
/ \
A(5) (6)
/ \
(3) C(3)
/ \
E(1) B(2)
步驟 5: 合併 (11) 和 D(7) → (18) [根節點]
標示邊緣（左=0, 右=1）：
| 字元 | 頻率 | 編碼 |
|---|---|---|
| D | 7 | 0 |
| A | 5 | 10 |
| C | 3 | 111 |
| B | 2 | 1101 |
| E | 1 | 1100 |
練習題 2
使用練習題 1 的編碼表編碼字串 "DACB"。
解答：
- D → 0
- A → 10
- C → 111
- B → 1101
編碼結果: 0101111101
練習題 3
為什麼霍夫曼編碼是前綴碼？這有什麼好處？
解答： 霍夫曼編碼是前綴碼，因為每個字元的編碼對應到霍夫曼樹的一個葉節點，而從根到葉的路徑是唯一的。沒有任何編碼是另一個編碼的前綴，因為如果一個編碼是另一個的前綴，那麼在樹中一個節點會是另一個節點的祖先，但葉節點不能是其他葉節點的祖先。
好處: 1. 解碼唯一性: 可以從左到右逐位解碼，不需要回溯 2. 解碼效率: 解碼過程簡單快速 3. 即時解碼: 可以邊接收邊解碼，不需要等待完整編碼
10. 考試重點提醒
- 建構過程: 要能清楚地展示每一步的合併過程
- 編碼產生: 理解如何從樹的路徑產生編碼
- 前綴碼: 理解為什麼霍夫曼編碼是前綴碼
- 頻率統計: 記住要先統計頻率
- 編碼表: 要能以表格形式清晰呈現編碼結果