Huffman

2023全國高中職教甄：有一組 6個外部節點的資料，其加權値分別為「 4、5、8、11、12、15」。請使用霍夫曼演算法(Huffman Algorithm)建Huffman Tree，求最小加權外部路徑長度 (Min Weighted External Path Length，Min.WEPL)的值。 (4分)

※霍夫曼樹可以有多種組合※

詢問ChatGPT：Build a Hoffman Tree, use the list of [4,5,8,11,12,15]. And calculate Min Weight External Path Length. 

ChatGPT回答：

首先，我們需要使用霍夫曼演算法來建構出霍夫曼樹。建構的過程如下：

1. 將外部節點依照加權值的大小排序，得到「4、5、8、11、12、15」。

2. 將每個外部節點視為一個獨立的樹。

3. 將加權值最小的兩棵樹合併成一個新的樹，新樹的加權值為兩棵樹的加權值之和。

4. 重複步驟 3，直到只剩下一棵樹，此樹即為霍夫曼樹。

具體的建構過程如下：

排序後：4, 5, 8, 11, 12, 15

將 4 和 5 合併，得到：

     9

    / \

   4   5

將 8 和 9 合併，得到：

     17

    /  \

   8    9

       / \

      4   5

將 11 和 12 合併，得到：

       23

      /  \

     11  12

將 15 和 17 合併，得到：

       32

      /  \

     15  17

         / \

        8   9

           / \

          4   5

最後將 23 和 32 合併，得到最終的霍夫曼樹：

           55

          /  \

         23  32

        / \  / \

       11 12 15 17

      / \

       8   9

            / \

          4   5

(11): 2*11=22

(12): 2*12=24

(15): 2*15=30

(8): 3*8=24

(4): 4*4=16

(5): 4*5=20

Sum=22+24+30+24+16+20=136

The algortihm

步驟一： 計算每一個符號的出現機率，並將所有符號及其機率放入待 處理符號集合R中，準備由下往上建立一棵編碼二元樹。

步驟二： 從待處理集合中找出機率最小的兩個符號做為二元樹的兩個 子節點，並為這兩個節點建立一個父節點，此父節點機率為 兩個子節點的機率和。再將這兩個子節點從R中移除，且把其 父節點(含機率)加入R中。

步驟三： 重複步驟二直到待處理集合只剩下一個符號。

步驟四： 將建立完成的二元樹中任何兩兄弟節點的左接線標上0右接線 標上1。樹中每個符號被指定之0與1的位元集合即是代表該符 號的字碼。(此時，符號一定位於樹葉節點) 

步驟五： 使用在步驟四決定的符號字碼，一一編碼所有待壓縮符號。 

Example :

# Encode the sequence: a e b a c d d a e a Determine the probability of each symbol and construct the coding tree.

P(a)=0.4,

P(b)=0.1,

P(c)=0.1,

P(d)=0.2,

P(e)=0.2,

R={a, b, c, d, e}  ※未排序，每次挑選最小兩個來產生新節點。

x ’(0.2) 

/ \

b(0.1) c(0.1) 

(a): 合併b(0.1)、c(0.1)成新節點x'(0.2)，合併後R={a(0.4), x’(0.2), d(0.2), e(0.2)} 

y ’(0.4) 

/ \

x ’(0.2) d(0.2) 

/ \

b(0.1) c(0.1) 

(b): 合併x'(0.2)、d(0.2)成新節點y'(0.4)，合併後R={a(0.4), y’(0.4), e(0.2)} 

z'(0.6)

/ \

y ’(0.4) e(0.2)

/ \

x ’(0.2) d(0.2) 

/ \

b(0.1) c(0.1) 

(c): 合併y'(0.4)、e(0.2)成新節點z'(0.6)，合併後R={a(0.4), z’(0.6)} 

(1)

/ \

z'(0.6) a(0.4)

/ \

y ’(0.4) e(0.2)

/ \

x ’(0.2) d(0.2) 

/ \

b(0.1) c(0.1) 

(d): 合併z'(0.6)、a(0.4)成新節點(1)，合併後R={(1)} ，產生下圖Code-1。

Code-1

樹高共計5層。

Code-2、Code-3

樹高共計4層。

參考文獻

https://medium.com/@bhch3n/huffman-coding-%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%B7%A8%E7%A2%BC-3879df5ecddc (含程式)

https://ithelp.ithome.com.tw/articles/10278711

https://hackmd.io/@vRN1CwEsTLyHOsG4mC0d4Q/SJJ6ofDn4 (含Min.WEPL解說)