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

這是一個經典的霍夫曼編碼（Huffman Coding）問題。我們需要先根據字母出現的頻率構建霍夫曼樹，找出每個字母的編碼長度，最後計算字串 "ACAT" 的總位元數。

第一步：整理頻率並排序

首先將所有字母按照出現次數（頻率）由小到大排列：

• D: 6

• B: 20

• C: 25

• T: 28

• E: 33

• A: 45

第二步：構建霍夫曼樹

霍夫曼樹的構建規則是：每次選取頻率最小的兩個節點合併，形成一個新節點（權重為兩者之和），重複此步驟直到只剩下一棵樹。

過程如下：

1. 取最小的兩個： D (6) 和 B (20)。

   • 合併產生新節點 N1，權重為 $6 + 20 = 26$。

   • 目前數列：C (25), N1 (26), T (28), E (33), A (45)

2. 取最小的兩個： C (25) 和 N1 (26)。

   • 合併產生新節點 N2，權重為 $25 + 26 = 51$。

   • 注意：N2 的結構是左子樹 C，右子樹 N1 (包含 D, B)。

   • 目前數列：T (28), E (33), A (45), N2 (51)

3. 取最小的兩個： T (28) 和 E (33)。

   • 合併產生新節點 N3，權重為 $28 + 33 = 61$。

   • 目前數列：A (45), N2 (51), N3 (61)

4. 取最小的兩個： A (45) 和 N2 (51)。

   • 合併產生新節點 N4，權重為 $45 + 51 = 96$。

   • 注意：N4 的結構是左子樹 A，右子樹 N2 (包含 C, D, B)。

   • 目前數列：N3 (61), N4 (96)

5. 最後合併： N3 (61) 和 N4 (96)。

   • 合併產生根節點，權重為 157。

第三步：計算各字母的編碼長度（深度）

從根節點往下走，計算到達每個字母需要經過多少層（每一層代表 1 個位元）。

1. A 的路徑： Root -> N4 -> A

   • 深度（編碼長度）：2 位元

2. C 的路徑： Root -> N4 -> N2 -> C

   • 深度（編碼長度）：3 位元

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 個位元。

1. 首先將所有字元依照出現次數從低到高排列：
   D: 6, B: 20, C: 25, T: 28, E: 33, A: 45
2. 建構霍夫曼樹 (Building the Huffman Tree)：原則是：每次挑選頻率最低的兩個節點合併，直到剩下一個根節點。
   1. D+B -> N1: 26
   2. C+N1 -> N2: 51
   3. T+E -> N3: 61
   4. A+N2 -> N4: 96
   5. N3+N4 -> N5: 157
3. 計算位元：
   • A 的路徑： Root -> N4 -> A (2 層) -> 2 bits
   • C 的路徑： Root -> N4 -> N2 -> C (3 層) -> 3 bits
   • T 的路徑： Root -> N3 -> T (2 層) -> 2 bits
4. 編碼 ACAT 的位元總數為：2+3+2+2 =9bits

整理初始頻率（由小到大排序）
各個字母出現的次數如下：
D: 6 次
B: 20 次
C: 25 次
T: 28 次
E: 33 次
A: 45 次
建構霍夫曼樹（步驟解析）
1. 第一次合併：挑選頻率最小的 D(6) 和 B(20)。
合併成新節點 N1 (26)。
目前剩餘節點：C(25), N1(26), T(28), E(33), A(45)。
2. 第二次合併：挑選目前最小的 C(25) 和 N1(26)。
合併成新節點 N2 (51)。
目前剩餘節點：T(28), E(33), A(45), N2(51)。
3. 第三次合併：挑選目前最小的 T(28) 和 E(33)。
合併成新節點 N3 (61)。
目前剩餘節點：A(45), N2(51), N3(61)。
4. 第四次合併：挑選目前最小的 A(45) 和 N2(51)。
合併成新節點 N4 (96)。
目前剩餘節點：N3(61), N4(96)。
5. 最後合併：合併 N3(61) 和 N4(96)。
合併成根節點 Root (157)。

A 的路徑：⁠1⁠ -＞ ⁠0⁠ （共 2 位元）
C 的路徑：⁠1⁠ -＞ ⁠1⁠ -＞ ⁠0⁠ （共 3 位元）
T 的路徑：⁠0⁠ -＞ ⁠0⁠ （共 2 位元）

最終計算：編碼 ACAT 需要多少位元？

我們將單字 ⁠ACAT⁠ 拆解：