阿摩線上測驗
17 為能夠在資料儲存或傳輸有更好的效率，使用壓縮技術。一個有名的技術稱為霍夫曼樹編碼（Huffman Tree Coding）。假設在一篇文章裡，出現 A 的次數是 45 次，B 是 20 次，C 是 25 次，D 是 6 次，E 是 33 次，而 T 是 28 次，以此數據建構一棵霍夫曼樹。有關編碼 ACAT 需要多少位元？
(A)7
(B)8
(C)9
(D) 10
統計： A(53), B(91), C(106), D(23), E(0) #3704760
詳解 (共 2 筆)
這是一個經典的霍夫曼編碼（Huffman Coding）問題。我們需要先根據字母出現的頻率構建霍夫曼樹，找出每個字母的編碼長度，最後計算字串 "ACAT" 的總位元數。
第一步：整理頻率並排序
首先將所有字母按照出現次數（頻率）由小到大排列：
-
D: 6
-
B: 20
-
C: 25
-
T: 28
-
E: 33
-
A: 45
第二步：構建霍夫曼樹
霍夫曼樹的構建規則是：每次選取頻率最小的兩個節點合併，形成一個新節點（權重為兩者之和），重複此步驟直到只剩下一棵樹。
過程如下：
-
取最小的兩個： D (6) 和 B (20)。
-
合併產生新節點 N1，權重為 $6 + 20 = 26$。
-
目前數列：C (25), N1 (26), T (28), E (33), A (45)
-
-
取最小的兩個： C (25) 和 N1 (26)。
-
合併產生新節點 N2，權重為 $25 + 26 = 51$。
-
注意：N2 的結構是左子樹 C，右子樹 N1 (包含 D, B)。
-
目前數列：T (28), E (33), A (45), N2 (51)
-
-
取最小的兩個： T (28) 和 E (33)。
-
合併產生新節點 N3，權重為 $28 + 33 = 61$。
-
目前數列：A (45), N2 (51), N3 (61)
-
-
取最小的兩個： A (45) 和 N2 (51)。
-
合併產生新節點 N4，權重為 $45 + 51 = 96$。
-
注意：N4 的結構是左子樹 A，右子樹 N2 (包含 C, D, B)。
-
目前數列：N3 (61), N4 (96)
-
-
最後合併： N3 (61) 和 N4 (96)。
-
合併產生根節點，權重為 157。
-
第三步：計算各字母的編碼長度（深度）
從根節點往下走，計算到達每個字母需要經過多少層（每一層代表 1 個位元）。
-
A 的路徑： Root -> N4 -> A
-
深度（編碼長度）：2 位元
-
-
C 的路徑： Root -> N4 -> N2 -> C
-
深度（編碼長度）：3 位元
-
-
T 的路徑： Root -> N3 -> T
-
深度（編碼長度）：2 位元
-
(補充：D 和 B 的長度會是 4，E 的長度是 2，但題目只需計算 ACAT)
第四步：計算 "ACAT" 的總位元數
我們要編碼的字串是 A C A T。
-
A: 2 bits
-
C: 3 bits
-
A: 2 bits
-
T: 2 bits
總和：2 + 3 + 2 + 2 = 9
答案:編碼 ACAT 需要 9 個位元。
- 首先將所有字元依照出現次數從低到高排列：
D: 6, B: 20, C: 25, T: 28, E: 33, A: 45 - 建構霍夫曼樹 (Building the Huffman Tree)：原則是：每次挑選頻率最低的兩個節點合併，直到剩下一個根節點。
- D+B -> N1: 26
- C+N1 -> N2: 51
- T+E -> N3: 61
- A+N2 -> N4: 96
- N3+N4 -> N5: 157
- 計算位元：
- A 的路徑： Root -> N4 -> A (2 層) -> 2 bits
- C 的路徑： Root -> N4 -> N2 -> C (3 層) -> 3 bits
- T 的路徑： Root -> N3 -> T (2 層) -> 2 bits
- 編碼 ACAT 的位元總數為：2+3+2+2 =9bits
