哈夫曼树

习题预习

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