地特四等
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
如果在建構這棵樹的過程中，我們希望整篇訊息的總長度達到最短，那麼你認為出現次數最頻繁的字元（例如 A），應該被安排在靠近「樹根」的位置，還是遠離樹根的末端位置？這樣的安排對它的二進位編碼長度會有什麼影響？
🤖
AI 詳解
AI 專屬家教
恭喜你正確完成了這道題目的計算！這代表你對於**霍夫曼編碼（Huffman Coding）**這種基於貪婪演算法（Greedy Algorithm）的變動長度編碼技術已有紮實的掌握。這類題目在計算機科學與工程領域中非常經典，核心觀念在於透過頻率的高低來分配編碼長度：出現頻率越高的元素，其路徑越短（位元數越少），反之則越長，以此達成數據壓縮的目的。
霍夫曼樹的構建與路徑計算
在本題中，我們依序合併頻率最低的節點。首先將 $D(6)$ 與 $B(20)$ 合併為 $26$；接著將 $C(25)$ 與該節點合併為 $51$。同時，次低的 $T(28)$ 與 $E(33)$ 合併為 $61$。隨後，將頻率最高的 $A(45)$ 與之前的 $51$ 合併為 $96$。最後，將 $61$ 與 $96$ 合併形成根節點。根據此樹狀結構，我們可以推導出各字母的編碼長度：
▼ 還有更多解析內容