d371. 3. Huffman 編碼中的編碼效能問題 | 2021全台活動資訊網

2010年8月15日—而Huffman編碼法就是非固定長度編碼法中最常使用的方法。例如，已知a,b,c,d,e}這5個符號的出現頻率由大至小如表 ...

為了用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 編碼後的總位元數。