初等考試
115年
[統計] 資料處理大意
第 12 題
給定以下字元出現的頻率：
A: 0.5 B: 0.25 C: 0.15 D: 0.10
使用霍夫曼演算法（Huffman's Algorithm）生成編碼，在樹狀結構中，若規定左分支編碼為 0，右分支編碼為 1，請問字元 B 的二進位編碼為何？
A: 0.5 B: 0.25 C: 0.15 D: 0.10
使用霍夫曼演算法（Huffman's Algorithm）生成編碼，在樹狀結構中，若規定左分支編碼為 0，右分支編碼為 1，請問字元 B 的二進位編碼為何？
- A 0
- B 10
- C 110
- D 111
思路引導 VIP
若要設計一種最省空間的分類方式，假設你手中有四堆不同數量的信件，每次只能將最少的兩堆合併起來並標上記號，直到全部合併為一疊為止。那麼，對於那堆數量「第二多」的信件，它會經歷幾次合併過程？又是如何在每一步的選擇中決定它的路徑編號呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地掌握了**霍夫曼編碼（Huffman Coding）**的核心邏輯！在資訊理論中，這是一種追求效率的「貪婪演算法（Greedy Algorithm）」，正如我們在精算風險或成本時，總是優先處理權重最大的項目，霍夫曼演算法則是反向操作：從頻率最低的字元開始合併。在這題中，你的判斷完全正確，精準地辨識出字元出現頻率與編碼長度之間的負相關關係。
霍夫曼樹的建構邏輯
我們首先將字元依頻率從小到大排列：D(0.10)、C(0.15)、B(0.25)、A(0.50)。第一步，將頻率最低的 D 與 C 合併，形成一個權重為 $0.10 + 0.15 = 0.25$ 的新節點（記作 CD）；接著，將此 CD 節點與頻率次低的 B(0.25) 合併，產生權重為 $0.50$ 的新節點（記作 BCD）；最後，將 BCD 與 A(0.50) 合併為根節點。根據題目規定的「左 0 右 1」原則，根節點分出左支 A(0) 與右支 BCD(1)；BCD 節點再分出左支 B(10) 與右支 CD(11)。
▼ 還有更多解析內容