d371. 3. Huffman 編碼中的編碼效能問題

內容

為了用0 與1 的位元串表示電腦中所需使用的符號，常見的編碼法可分為兩大類：固定長度編碼法與非固定長度編碼法。

固定長度編碼法指的是，將每個符號用相同長度的位元串表示。

例如，要以二進位的0 與1 位元串表示{a, b, c, d, e } 5個符號

每個符號最少需要以3 個位元來編碼成{000, 001, 010, 011, 100}。

但如果我們已知這些符號在多數資料中出現的頻率不同，就可用非固定長度編碼法更有效地表示這些資料

而Huffman 編碼法就是非固定長度編碼法中最常使用的方法。

例如，已知{a, b, c, d, e}這5 個符號的出現頻率由大至小如表一所示。

則Huffman 編碼法利用建立二元樹的方式，首先將每個符號以一個自由節點(freenode)表示

這些自由節點的權重(weight)即是符號的頻率。

接著，從自由節點中找出權重最小的兩個節點，為這兩個節點做一個父節點，此父節點的權重則為這兩個子節點的權重和。

之後，將父節點加入自由節點的行列，並將兩個子節點從自由節點的行列中去除。

接著，重覆選取兩個權重最小的節點，造出父節點並更新自由節點的過程，直到最後只剩一個自由節點為止。

當得到這棵編碼樹後，我們就可以從二元樹的根結點(root node)開始往下走

每往左子樹(left subtree)走一層就給定一個位元的編碼0

每往右子樹(right subtree)走一層就給定一個位元的編碼1

依此方式逐層往下走並同時編碼直到走到葉節點(leaf node)為止。

圖一、二所示即為依表一頻率表所建造的不同Huffman 編碼樹。

雖然圖一和圖二的編碼結果不同，但檢視其編碼效能，如表二所示，可發現這兩個編碼所得到的總位元數是相同的:

16+24+16+16+16+16=32+16+16+12+12=88。

請撰寫一個程式，根據已知的頻率表(尚未排序過)，計算以Huffman 編碼後的總位元數。

輸入說明

第一行為一個整數n，代表共有幾個符號。(n<=2^k，k 為正整數，1<k<=16)。

接下來的n 個數字代表這n 個符號的頻率，每個數字為介於1 與2¹⁶ 之間的正整數，每兩個數字以一個空格隔開。

輸出說明

對每一個輸入的頻率表，計算以Huffman 編碼後的總位元數。

範例輸入 #1

5
16 8 8 4 4

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (20%): 2.0s , <1K
不公開測資點#1 (20%): 2.0s , <1K
不公開測資點#2 (20%): 2.0s , <1K
不公開測資點#3 (20%): 2.0s , <1M
不公開測資點#4 (20%): 2.0s , <1M

提示：

標籤:

出處:

96學年度全國資訊學科能力競賽 [管理者：

Unknown User

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」