[数据结构与算法]哈夫曼树、哈夫曼编码与压缩比

1、哈夫曼树

• 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

• 带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度

• 构造哈夫曼树

2、哈夫曼编码

3、压缩比

案例分析：

已知某文档包含5个字符。每个字符出现的频率如下表所示。采用霍夫曼编码对该文档压缩存储，则单词“cade”的编码为（ (1) ），文档的压缩比为（ (2)）

(1)：【A】1110110101 【B】1100111101 【C】1110110100 【D】1100111100

(2)：【A】20%【B】25%【C】27%【D】30%

1）构造哈夫曼树

以频率作为权重，依次取最小的两个值

2）标注编码

按照左分支为0、右分支为1原则标注

由此可知：cade的编码为： 111 0 110 101 选答案A

3）计算压缩比

1. 5个字符最少需要3位二位进数表示，即每个字符用三位表示

2. 通过哈夫曼树优化后，a用0表示，只有1位

3. 按照出现频率计算加权平均长度：字符位数 * 出现频率

   a的位数 * 40% + b的位数 * 10% + c的位数 * 20% + c的位数 * 16% + d的位数 * 14%

   = 1 * 40% + 3 * 10% + 3 * 20% + 3 * 16% + 3 * 14%

   = 2.2位

4. 计算压缩比

   未压缩长度为 3 ，压缩后平均长度为 2.2

   (3 - 2.2)/3 = 27%

   选答案C