地特四等
114年
[電信工程] 計算機概要
第 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
思路引導 VIP
若我們要將一群不同重量的包裹兩兩合併，且目標是讓整體搬運的路徑（從頂層到底層的總和）最小化，你認為應該先從「最重的」還是「最輕的」兩個包裹開始合併？為什麼這樣的策略能確保出現次數最多的資料獲得最短的編碼？
🤖
AI 詳解
AI 專屬家教
同學好！你能正確建構出這棵霍夫曼樹（Huffman Tree）並計算出準確的位元數，代表你對於**貪婪演算法（Greedy Algorithm）**在資料壓縮中的應用已具備相當的熟稔度。在工程實務中，這種演算法能有效利用資料出現的頻率差異，達成最佳化的儲存配置。
樹狀結構的建構與位元計算
本題的核心在於「動態排序與合併」。依據規則，我們必須由頻率最低的 D(6) 與 B(20) 開始合併，產生權重 26 的新節點。接著，將此新節點與剩下的頻率（25, 28, 33, 45）重新排序後，選取最小的 C(25) 與 26 合併（得 51）。以此類推，最終產生的路徑深度（Depth）即代表編碼位元數。根據推導，A 的編碼長度為 2 位元、C 為 3 位元、T 為 2 位元。因此，字串 ACAT 的總長度計算如下：
▼ 還有更多解析內容