哈夫曼编码(Huffman Coding)与哈夫曼树(Huffman Tree)

        已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为6，3，8，2，10，4，则对应字符集中各字符的哈夫曼编码可能是（        ）。

A.00，1011，01，1010，11，100                   B.00，100，110，000，0010，01

C.10，1011，11，0011，00，010                   D.0011，10，11，0010，01，000

---

看到此题，首先我们需要了解什么是哈夫曼编码与哈夫曼树？

---

哈夫曼编码(Huffman Coding)

1. 哈夫曼在1952年设计了一种算法，即利用字符频率来构造最优前缀码的编码方法，称为哈夫曼编码。
   1. 该编码方法一般设置在哈夫曼树中，从根节点到每个叶子节点的路径上，标记左分支的权值为0，标记右分支的权值为1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码(即每个叶子节点都会有一个唯一的二进制编码)，这就是哈夫曼编码。
2. 一般应用于数据的解压和压缩。其核心思想是通过构建哈弗曼树，为常用字符分配较短的编码，不常用的字符分配较长的编码，从而减少数据的总体存储空间以及传输成本。 不会丢失信息，能够保持原始数据完整性。但构建哈夫曼树和生成编码的过程相对复杂，一般在应用时也无法实时地快速处理。
3. 可以根据数据出现的频率来构建二叉树 。      
4. 哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一比对即可

   1. 前缀编码 

      1. 任一字符的编码都不是另一个字符的编码的前缀，不会因为编码的长短不等而让人产生混淆，这就是前缀编码。

5. 哈夫曼编码构造过程

   1. 首先统计每个字符在数据中出现的频率，将每个字符的频率视为树的权值。
   2. 先把有权值的叶子结点按照从小到大的顺序进行排列，形成一个有序序列。

   3. 每次选择两个权值最小的树(即出现频率最低的两个节点，相对较小的是左孩子)合并为一棵新的二叉树，新树的权值为两个子树权值之和。(即令N为这两棵树的父结点，N节点的出现频率等于这两棵树出现频率的总和)。

   4. 去掉步骤3的两个节点，将父结点N加入步骤2，重新进行计算。

   5. 重复上述过程，直到只剩下一棵树为止，即最终会形成一个根结点。此时便完成了哈夫曼树的构造。

   6. 根据构建好的哈夫曼树，从根节点到每个叶子节点的路径上，左分支标记为0，右分支标记为1，从而得到每个字符的哈夫曼编码。

               

---

哈夫曼树‌【优化二叉树】(Huffman Tree)

1. 哈夫曼在编码中用到的特殊二叉树称为哈夫曼树。
   1. 同样，我们在解码的时候还是要用到哈夫曼树。
2. 树结点间的边相关的数叫做权。
3. 树的构建基于字符的出现频率，频率高的字符对应的节点更接近树的根结点，频率低的字符对应的节点更远离树的根结点。‌
4. 【路径长度】为从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目。
5. 【树的路径长度】为树根到每一结点的路径长度之和。
6. 【结点带权的路径长度】为从该结点到树根之间的路径长度与结点上权的乘积。
7. 【树的带权路径长度(WPL)】为树中所有叶子结点的带权路径长度之和。
   1. 哈夫曼树是一种最优二叉树，其带权路径长度最短。

                        

回看此题：

        已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为6，3，8，2，10，4，则对应字符集中各字符的哈夫曼编码可能是（        ）。

A.00，1011，01，1010，11，100                   B.00，100，110，000，0010，01

C.10，1011，11，0011，00，010                   D.0011，10，11，0010，01，000

因为各字符出现的次数分别为6，3，8，2，10，4，所以根据上面讲到的哈夫曼编码构造过程第2步，先把有权值的叶子结点按照从小到大的顺序进行排列，形成一个有序序列，即：

2，3，4，6，8，10

根据第3步所讲，每次选择两个权值最小的树(即出现频率最低的两个节点，相对较小的是左孩子)合并为一棵新的二叉树，新树的权值为两个子树权值之和。(即令N为这两棵树的父结点，N节点的出现频率等于这两棵树出现频率的总和)，即：

2和3为出现频率最低的两个节点，2相对较小，是左孩子，N为2+3=5，即N=5

画图为：

将N加入步骤2，重新进行计算，即：

4，5，6，8，10

根据第3步所讲，即：

4和5为出现频率最低的两个节点，4相对较小，是左孩子，父结点为4+5=9，即N=9

将父结点加入步骤2，重新进行计算，即：

6，8，9，10

根据第5步所讲，重复上述过程，直到只剩下一棵树为止，即最终会形成一个根结点。此时便完成了哈夫曼树的构造，即：

9，10，14

14，19

33

 

根据字符集为{a,b,c,d,e,f}，各字符出现的次数分别为6，3，8，2，10，4，所以将上面画好的图替换回来，即：

再根据第6步所讲，根据构建好的哈夫曼树，从根节点到每个叶子节点的路径上，左分支标记为0，右分支标记为1，从而得到每个字符的哈夫曼编码，即：

列表为：

	a	b	c	d	e	f
	00	1011	01	1010	11	100

故得到的哈夫曼编码为00，1011，01，1010，11，100

选项：

A.00，1011，01，1010，11，100                   B.00，100，110，000，0010，01

C.10，1011，11，0011，00，010                   D.0011，10，11，0010，01，000

故选A