吉林大学数据结构_哈夫曼树.pptx

1、4.5 压缩与哈夫曼树,数据压缩与哈夫曼树的关系,数据压缩技术，就是用最少的数码来表示信号的技术。 其作用是：能较快地传输各种信号。,1948 年， Shannon 在提出信息熵理论的同时，也给出了一种简单的编码方法 Shannon 编码。 1952 年， R. M. Fano 又进一步提出了 Fano 编码。 这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。,第一个实用的编码方法是由 D. A. Huffman 在 1952 年的论文“最小冗余度代码的构造方法（ A Method for the Construction of Mi

2、nimum Redundancy Codes ）”中提出的。 直到今天，许多数据结构教材在讨论二叉树时仍要提及这种被后人称为 Huffman 编码的方法。,Huffman 编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。,例如，早期 UNIX 系统上一个不太为现代人熟知的压缩程序COMPACT 实际就是Huffman 0 阶自适应编码的具体实现。 20 世纪 80 年代初， Huffman 编码又出现在CP/M和 DOS 系统中，其代表程序叫 SQ 。 今天，在许多知名的压缩工具和压缩算法（如 WinRAR 、 gzip 和 JPEG ）里

3、，都有 Huffman 编码的身影。,哈夫曼编码的发展历史,1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。 由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。 由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端自顶向下构建树。,数据压缩,数据压缩是计算机科学

4、中的重要技术。 数据压缩过程称为编码，即将文件中的每个字符均转换为一个唯一的二进制位串。 数据解压过程称为解码，即将二进制位串转换为对应的字符。 比如： s00000 nl 00001 t0001 a001 e 01 i 10 sp 11,文件编码,等长编码和不等长编码,ASCII字符集中大约包含了 100个可打印字符。为了区分它们，需要 2 100 =7位的二进制串来表示它们，而7位二进制串共能表示 2 7 =128个字符，因此，ASCII字符集又增加了一些非打印字符。,等长编码ASCII码-1,如果字符集包含C个字符，则在标准的等长编码中，每个字符由一个 2 位的二进制串表示。,等长编码A

5、SCII码-2,例. 假设有一个文件仅包含7个字符a,e,I,s,t,sp和nl，且文件中有10个a，15个e，12个i，3个s，4个t，13个sp，1个nl。 等长编码方案：3位二进制串 则文件长度为 103+153+123+33+43+133+13=174,等长编码ASCII码-3,等长编码存在的问题浪费空间,在实际应用的一些大文件中，字符被使用的频率是非平均的，即有些字符出现的次数多，有些字符出现的次数少。如果所有字符都由等长的二进制码表示，那么将造成空间浪费。 如何才能减少这种不必要的空间浪费呢？ 文件压缩的通常策略是采用不等长的二进制码，令文件中出现频率高的字符的编码尽可能短。,不等

6、长编码存在的问题多义性,但是，采用不等长编码又可能会产生多义性。 例. 有如下字符编码： a-01 b-10 c-1001 那么，对于二进码1001，如何进行解码？ 1001-c ? 1001-ba ? 其原因是b的编码与c的编码的开始部分（前缀）相同。,问题解决前缀码,为了避免出现多义性，就必须要求字符集中任何字符的编码都不是其他字符的编码的前缀，满足这个条件的编码被称为前缀码。 显然，等长编码是前缀码。,怎样的前缀码才能使文件的总编码长度最短？,设组成文件的字符集A= 1 , 2 , ，其中， 的编码长度为 ， 出现的次数为 。 要使文件的总编码最短，就必须要确定 ，使 =1 取最小值。,

7、如何设计出使 = 最小的前缀码？,D.A.Huffman于1952年提出了哈夫曼算法。,哈夫曼算法原理,基本概念,扩充二叉树、内结点、外结点 内、外通路长度 加权外通路长度WPL 最优二叉树,扩充二叉树、内结点、外结点,定义4.9 为了使问题的处理更为方便，每当原二叉树中出现空子树时，就增加特殊的结点空树叶，由此生成的二叉树称为扩充二叉树。,内、外通路长度,定义4.10 扩充二叉树的外通路长度定义为从根到每个外结点的路径长度之和，内通路长度定义为从根到每个内结点的路径长度之和。,假设有n个实数 0 , 1 , 1 对应扩充二叉树的n个外结点 即 为扩充二叉树的每一个外结点赋予一个权值 则我们在

8、外通路长度的基础之上定义加权外通路长度WPL,加权外通路长度WPL,定义4.11 给扩充二叉树中n个外结点赋上一个实数 ，称为该结点的权。扩充二叉树的加权外通路长度WPL定义为 = =0 1 其中， n表示外结点的个数， 和 分别表示外结点 的权值和根到 之间的路径长度。,最优二叉树,定义4.12 在外结点权值分别为 0 , 1 , , 1 的扩充二叉树中，加权外通路长度最小的扩充二叉树称为最优二叉树。,例. 假设有一个文件仅包含7个字符a,e,I,s,t,sp和nl，且文件中有10个a，15个e，12个i，3个s，4个t，13个sp，1个nl。 如果把每个结点都作为一棵二叉树的根结点，那么这

9、7个根结点就组成了一个森林。 把结点在文件中出现的次数定义为该节点的权值。,哈夫曼算法思想1,哈夫曼算法思想2,（1）在森林中取权值最小的两个根结点s和nl，合并成一棵二叉树，并生成一个新结点 1 . 作为这两个结点的父节点， 1 的权值是它的两个子节点的权值之和。显然， 1 成为新的根结点，而s和nl成为 1 的子节点。同时，森林中减少了一棵树。 （2）对新森林重复上一步操作，直至森林中只有唯一一个根结点时，终止操作。,哈夫曼算法动画演示示例,s,nl,t,a,e,i,sp,1,3,4,10,12,13,15,nl,s,1,3, ,4, ,4,t,4, ,8, ,8,58,a,10, ,18

10、, ,18,e,i,sp,12,13,15, ,25, ,25, ,33, ,33, ,58, ,0,1,0,0,0,0,1,1,1,1,1,0,文件总编码长度： 15+35+44+103+122+132+152=146,问 题,哈夫曼树是否唯一？ 哈夫曼编码是否唯一？,哈夫曼编码是前缀码,因为在构造哈夫曼树的过程中，没有一片树叶是其他树叶的祖先，所以每个叶结点对应的编码不可能是其他叶结点对应的编码的前缀，由此可知哈夫曼编码是二进制的前缀码。,哈夫曼树为最优二叉树,定理4.3 在外结点权值分别为 0 , 1 , , 1 的扩充二叉树中，由哈夫曼算法构造出的哈夫曼树的加权外通路长度最小，因此，哈

11、夫曼树为最优二叉树。,哈夫曼算法采用的结点结构,下面我们给出构造哈夫曼树的Huffman算法3，假定哈夫曼树中每个结点的结构为： 其中，LLINK和RLINK为链接域，INFO为信息域，Weight为该结点的权值。,哈夫曼算法描述,算法Huffman(H, m.Root) /*Huffman算法，假定与给定的m个实数（权值）结合的结点的地址存于一维数组H1:m+1中，并且该数组按每个结点的Weight域已经排序，即Weight(H1)Weight(Hm) Weight(Hm+1)=+ */,算法Huffman(H, m.Root) FOR i1 TO m DO LLINK(Hi) RLINK(Hi) . FOR i1 TO m-1 DO ( t AVAIL. P1 Hi. P2 Hi+1. Weight(t) Weight(P1 ) Weight(P2 ). LLINK(t) P1 . RLINK(t) P2 . P t . j i 2 . WHILE Weight(p)Weight(Hj) DO ( Hj-1 Hj . j j 1.) Hj-1 p. ) Root p.,解 码,对压缩后的数据文件进行解码必须借助于哈夫曼树，其过程是： 依次读入文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子时便译出相应的字符。然后重新