哈夫曼樹

習題預習

1. 如何建立一個Huffman Tree給以下字元的 frequencies: A(6), B(3), C(2), D(1), E(1)?
2. 如果一個Huffman Tree有1百萬個字元，那麼此樹的深度是多少？
3. 如何在Huffman Tree中，找到某些特定字元的編碼？
4. 如果一個Huffman Tree是壓縮一個二進制字符流，需要多少位元才能儲存此樹的節點？
5. 什麼是Huffman coding的時間和空間複雜度？

說明知識

Huffman Tree（霍夫曼樹）是一種二叉樹，用於壓縮數據和編碼。它的結構和模樣如下圖所示：

Huffman Tree 由一個權值列表（通常是字符的出現頻率）建立而成。透過一系列的操作，可以把權值最小的兩個節點合併為一個新節點，新節點的權值等於它的兩個子節點的權值之和。這個新節點會被插入回原權值列表中，並重複上述操作，直到只剩下一個節點，即為霍夫曼樹的根節點。

對於一個待壓縮的文本，可以透過霍夫曼編碼將每個字符用另一個代表它的二進制碼替代，使得密碼簿的長度縮短，節省儲存空間。具體方法是在霍夫曼樹中，左子節點代表的二進制碼為 0，右子節點為 1，將每個字符所對應的路徑即可構成其二進制碼。

舉例來說，假設有一個文本 “aaabbcdddd”，每個字母的權值為：

• a: 3
• b: 2
• c: 1
• d: 4

則可以建立出以下的霍夫曼樹：

從上圖可知，字符 a 的二進制碼為 0，字符 b 為 10，字符 c 為 110，字符 d 為 111。紀錄壓縮後的二進制碼即可將原文本壓縮。在解壓縮時，透過霍夫曼樹的路徑，即可將每個二進制碼替換成原本的字符，還原原文本。

彙總重點

1. Huffman Tree 是一種二叉树，用於進行有效的資料壓縮和解壓縮。

2. 每個節點都有一個權值，該權值表示對應字符的出現頻率。

3. 民采用貪婪算法來構建Huffman Tree，即從權值最小的兩個節點開始合併，直到所有節點都結合成一個樹。

4. 每個節點都是由兩個子節點組成，左子樹表示第一位二進制數0，右子樹表示第一位二進制數1。

5. 通過對Huffman Tree的遍歷，可以編碼每個字符，使其代表的二進制序列最短。

6. 解碼時，根據遍歷Huffman Tree的路徑來查找相應的字符，並將它們組合成原始數據。

7. Huffman Tree是一種可變長編碼，字符的編碼長度根據出現頻率不同而不同，出現頻率越高的字符編碼越短。

8. Huffman Tree廣泛應用於數據壓縮和傳輸中，使數據傳輸更快，減少存儲空間，並提高數據使用效率。

知識測驗

1. 將如下項目的頻率存儲在數組中: {a: 5, b: 9, c: 12, d: 13, e: 16, f: 45} 創建一個Huffman Tree，並求出“f”字符的Huffman編碼。
   答案: Huffman Tree如下圖所示， “f”字符的編碼為“0”:

         ________0_______
        /                \
   ____1____          ___0___
  /         \        /       \
d:13         e:16  ____1     c:12
                 /     \ 
                b:9     a:5

2. 將如下項目的頻率存儲在數組中：{a: 12, b: 5, c: 15, d: 13, e: 11, f: 3}創建一個Huffman Tree，求出項目“b”和“e”的Huffman編碼。
   答案: Huffman Tree如下圖所示，“b”字符的編碼為“111”，“e”字符的編碼為“00”:

         _________0_________
        /                   \
    ___1___             ____0___
   /       \           /        \
c:15      ___1___     d:13      e:11
         /       \  
        a:12     ___0___
                /       \
               b:5       f:3

3. 創建一個Huffman Tree並確定項目的Huffman編碼。該示例中給出項目和相應的頻率：{a: 50, b: 20, c: 40, d: 30, e: 10}
   答案: Huffman Tree如下圖所示，“a”的編碼為“0”，“b”的編碼為“1101”，“c”的編碼為“10”，“d”的編碼為“111”，“e”的編碼為“1100”:

               __0__
            /        \
           /          \
        _1_            0
     /      \      /     \
    1      __0__   1      0
  /   \   /     \        /  \
c:40  d:30 a:50 e:10    b:20

4. 創建一個Huffman Tree並確定項目的Huffman編碼。該示例中給出項目和相應的頻率：{a: 20, b: 15, c: 25, d: 10, e: 30}
   答案: Huffman Tree如下圖所示，“a”的編碼為“1011”，“b”的編碼為“1010”，“c”的編碼為“11”，“d”的編碼為“1101”，“e”的編碼為“0”:

                0
           /        \
         _1_        1
      /      \      
     0      __1__   
           /     \  
          0      _1_
               /   \
             a:20 b:15
             /    /   \
            c:25  d:10 e:30

5. 創建一個Huffman Tree並確定項目的Huffman編碼。該示例中給出項目和相應的頻率：{a: 40, b: 25, c: 15, d: 10, e: 5, f: 5}
   答案: Huffman Tree如下圖所示，“a”的編碼為“0”，“b”的編碼為“11”，“c”的編碼為“101”，“d”的編碼為“1001”，“e”的編碼為“10001”，“f”的編碼為“10000”:

                __0__
             /        \
           _1_        _1_
         /     \    /     \
        a:40  b:25   __1__  f:5
                  /     \
                 c:15   __0__
                       /     \
                     d:10   e:5