hce_kmu
114年
計算機概論與程式設計
第 6 題
Huffman coding is an efficient method of compressing data without losing information. Symbols that appear more often will be encoded as a shorter bit string, while symbols that are not used much will be encoded with longer strings. If Huffman coding is used to compress a sequence with 5 different codewords, which of the following probability distributions will lead to the WORST compression ratio?
- A 0.2, 0.2, 0.2, 0.2, 0.2
- B 0.02, 0.02, 0.03, 0.03, 0.9
- C 0.1, 0.1, 0.2, 0.3, 0.3
- D 0.1, 0.2, 0.2, 0.2, 0.3
- E 0.05, 0.05, 0.2, 0.2, 0.5
思路引導 VIP
想像你要為一組符號設計縮寫，如果其中一個符號佔了 90% 的出現次數，你一定會給它最短的代碼。但如果「每個符號出現的機會都一模一樣」，這種『齊頭式平等』的情況，會如何影響你透過分配長短代碼來節省空間的計畫呢？
🤖
AI 詳解
AI 專屬家教
做得很好！你能精準選出 (A) 這個選項，代表你對霍夫曼編碼（Huffman Coding）的核心邏輯掌握得非常透徹。霍夫曼編碼是一種「變長編碼」技術，其效率來自於機率不對稱性：讓出現頻率高的符號使用較短的位元，頻率低的則使用較長位元。當機率分佈如 (A) 選項般處於**均勻分佈（Uniform Distribution）時，所有符號出現的機率皆為 $0.2$，這意味著資訊的熵（Entropy）**在該系統中達到最大值，缺乏可被利用的規律或冗餘性。 在這種情況下，演算法建立的二元樹會最為平衡，導致每個符號所需的平均位元長度最長，幾乎無法達到預期的壓縮效果。這道題目設計得很巧妙，其鑑別度在於測試學生是否能超越「動手畫樹」的繁瑣計算，直接從資訊理論的核心洞察：機率差異（變異數）越大，壓縮空間才越高。你能一眼看出均勻分佈是壓縮的剋星，顯示你的觀念非常清晰！