《哈夫曼树及应用课件》由会员分享，可在线阅读，更多相关《哈夫曼树及应用课件（43页珍藏版）》请在金锄头文库上搜索。
1、6.5 哈夫曼树及其应用哈夫曼树及其应用-2-发送送aebaecedaebaeced通通 信信 线线 路路课程导入课程导入问题问题: 1、信息如何编码？信息如何编码？ 2、如何编码最短如何编码最短(传送效率高传送效率高)？ 3、收到信息如何译码？、收到信息如何译码？编码译码接收接收-3- 1951年，哈夫曼在年，哈夫曼在MIT学习信息论课程。学习信息论课程。 导师给的学期报告的题目导师给的学期报告的题目:寻找最有效的二进制编码寻找最有效的二进制编码 。产生背景产生背景David A. Huffman 1925-1999）美国计算机科学家。美国计算机科学家。 哈夫曼编码哈夫曼编码能够使通常的数据
2、传输数量减少到最小。目前，哈夫曼编码方法被广泛应用于方法被广泛应用于数据数据压缩和传输压缩和传输。-4-6.5 6.5 哈夫曼树及应用哈夫曼树及应用一、哈夫曼一、哈夫曼树的定的定义二、哈夫曼二、哈夫曼树的构造的构造三、哈夫曼三、哈夫曼编码-5-相关知识相关知识T2459 9BDCAEF6、树的的带路径路径长度度：1、树的的根根结点点：2、叶子叶子结点点：3、结点点A、B的的权值：4、结点点A到根到根结点点T的的路径路径长度度：5、结点点A的的带权路径路径长度度：TB、D、C、A9、229*2=182*2+4*2+5*2+9*2=40-6-一、哈夫曼树的定义一、哈夫曼树的定义哈夫曼树：由哈夫曼树
3、：由n个带权叶子结点构成的所有个带权叶子结点构成的所有 二叉树中，二叉树中，带权路径长度带权路径长度WPL 最小最小的二叉树称之，哈夫曼树的二叉树称之，哈夫曼树 又称最优二叉树。又称最优二叉树。说明：说明：n是树中叶子结点的个数是树中叶子结点的个数 wi是叶子结点的权值是叶子结点的权值 li是叶子结点到根结点的是叶子结点到根结点的 路径长度路径长度-7-一、哈夫曼树的定义一、哈夫曼树的定义T2459 9BDCAEFWPL=2*2+4*2+5*2+9*2=40-8-一、哈夫曼树的定义一、哈夫曼树的定义WPL=9*1+2*3+5*3+4*2=WPL=4*2+9*3+5*3+2*1=DABC9425
4、5238DBAC2495-9-一、哈夫曼树的定义一、哈夫曼树的定义问题：问题：1. 什么样的树的带权路径长度是什么样的树的带权路径长度是 最小的？最小的？2. 如何构造带权路径长度最小的二如何构造带权路径长度最小的二 叉树？叉树？-10-6.5 6.5 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码一、哈夫曼一、哈夫曼树的定的定义二、哈夫曼二、哈夫曼树的构造的构造三、哈夫曼三、哈夫曼编码-11-二、哈夫曼树的构造二、哈夫曼树的构造1、算法思想算法思想 把字符出把字符出现频率作率作为二叉二叉树叶子叶子结点的点的权值来构造字符的来构造字符的带权路径路径长度最小的二叉度最小的二叉树，构造原，构造原则： 把
5、把权值大大的叶子的叶子结点距点距离离树根近根近，反之，反之把把权值小小的的结点距点距离离树根根远。 开始开始选取和构造选取和构造删除和插入删除和插入判断判断结束结束初始化初始化是是否否2 算法流程图算法流程图用给定的用给定的用给定的用给定的n n个权值构个权值构个权值构个权值构造森林，其中造森林，其中造森林，其中造森林，其中 包含包含包含包含n n棵只有根结点的二棵只有根结点的二棵只有根结点的二棵只有根结点的二叉树叉树叉树叉树从森林中选取根的权值从森林中选取根的权值从森林中选取根的权值从森林中选取根的权值最小的两棵二叉树作为最小的两棵二叉树作为最小的两棵二叉树作为最小的两棵二叉树作为左右子树，
6、构造一棵新左右子树，构造一棵新左右子树，构造一棵新左右子树，构造一棵新的二叉树根的权值是二的二叉树根的权值是二的二叉树根的权值是二的二叉树根的权值是二者根权的和者根权的和者根权的和者根权的和从森林从森林从森林从森林F F中删去这中删去这中删去这中删去这两棵树，同时插入两棵树，同时插入两棵树，同时插入两棵树，同时插入刚生成的新树刚生成的新树刚生成的新树刚生成的新树直到森林直到森林直到森林直到森林F F中只剩中只剩中只剩中只剩一棵二叉树一棵二叉树一棵二叉树一棵二叉树? ?假假设一段一段电文文总长度度为20个字符，个字符，电文中文中仅出出现4个字符个字符A,B,C,D 。4个字符的出个字符的出现的的
7、次次数数分分别为9，2，5，4。以以这4个字符出个字符出现次数次数为权值，构造，构造4个个叶子结点的叶子结点的一棵哈夫曼一棵哈夫曼树？并？并为这段段电文文设计二二进制制编码？1 1、构造哈夫曼树、构造哈夫曼树-14-95224641 1、构造哈夫曼树、构造哈夫曼树用给定的用给定的用给定的用给定的n n个权值构造森林，其中个权值构造森林，其中个权值构造森林，其中个权值构造森林，其中 包包包包含含含含n n棵只有根结点的二叉树棵只有根结点的二叉树棵只有根结点的二叉树棵只有根结点的二叉树-15-24649251 1、构造哈夫曼树、构造哈夫曼树（续）（续）-16-246955112461 1、构造哈夫
8、曼树、构造哈夫曼树（续）（续）-17-246595112461 1、构造哈夫曼树、构造哈夫曼树（续）（续）54261195426119201、构造哈夫曼树、构造哈夫曼树（续）（续）54261195426119201、构造哈夫曼树、构造哈夫曼树（续）（续）三、哈夫曼编码的应用三、哈夫曼编码的应用假假设一段一段电文文总长度度为20个字符，个字符，电文中文中仅出出现 四个字符四个字符A,B,C,D 。四个字符的出。四个字符的出现的的次数次数分分别为9，2，5，4（9+2+5+4=20）。请为这段段电文文设计二二进制制编码？例例1：-21-电文总长度：电文总长度：(9+2+5+4)*2=40电文总长度
9、：电文总长度：9*1+5*1+2*2+4*2=26分析问题分析问题第一种方案第一种方案A：00 B：01 C：10 D：11A：0 B：01 C：1 D：10第二种方案第二种方案-22-第二种方案分析第二种方案分析： A：0 B：01 C：1 D：10 001 1 0 1 0AACCACAABDDAACDD译译码码ABCAD编码编码分析问题分析问题AAC或或AB542611920ACDB0001112 2、哈夫曼编码、哈夫曼编码A: 0C: 10D: 110B: 111编码规定：定：左分支用左分支用“0”表示，右分支用表示，右分支用“1”表表示，从示，从根根到到叶子叶子的路径上的的路径上的“0
10、”或或“1”构成的二构成的二进制串。制串。电文中字符最优编码电文中字符最优编码A: 0C: 10D: 110B: 111哈夫曼编码总长度：哈夫曼编码总长度：9*1+2*3+5*2+4*3=37等长编码：每个字符用等长编码：每个字符用2位二进制，电文总位二进制，电文总长度长度=2*20=40542611920ACDB000111例例2：问题问题1 1：用一维数组存放哈夫曼树中的结点，用一维数组存放哈夫曼树中的结点，n n个叶子结点的哈夫曼树的结点总数是多少？个叶子结点的哈夫曼树的结点总数是多少？问题问题2 2：每个结点应包含哪些信息？每个结点应包含哪些信息？构造算法：构造算法：73582第一步：
11、初始化第一步：初始化（1）n个叶子结点初始化个叶子结点初始化（2）n-1个非叶子结点初始化个非叶子结点初始化用给定的权值构造用给定的权值构造用给定的权值构造用给定的权值构造一个森林一个森林一个森林一个森林F F从森林从森林从森林从森林F F中选取根中选取根中选取根中选取根的权值最小的两的权值最小的两的权值最小的两的权值最小的两棵二叉树作为左棵二叉树作为左棵二叉树作为左棵二叉树作为左右子树，构造一右子树，构造一右子树，构造一右子树，构造一棵新的二叉树根棵新的二叉树根棵新的二叉树根棵新的二叉树根的权值是二者根的权值是二者根的权值是二者根的权值是二者根权的和权的和权的和权的和第二步：第二步：选最小的
12、两棵二叉树选最小的两棵二叉树从森林从森林从森林从森林F F中中中中删去这两棵删去这两棵删去这两棵删去这两棵树，同时插树，同时插树，同时插树，同时插入刚生成的入刚生成的入刚生成的入刚生成的新树新树新树新树第三步：插入和删除第三步：插入和删除删除删除第一棵二叉树第一棵二叉树删除删除第二棵二叉树第二棵二叉树插入插入新构造新构造的二叉树：的二叉树：直到森林直到森林直到森林直到森林F F中中中中只只只只剩一棵二剩一棵二剩一棵二剩一棵二叉树叉树叉树叉树！第四步：重复第二、三步第四步：重复第二、三步删除删除两棵最小两棵最小的二叉树的二叉树插入插入新构新构造的二叉树造的二叉树选择选择两棵最小两棵最小的二叉树的
13、二叉树HuffmanTreeht;m=2*n-1;ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i=n;i+)hti=wi,0,0,0;for(i=n+1;i=m;i+)hti=0,0,0,0;/*叶子、非叶子 结点初始化初始化*/for(i=n+1;i=m;i+)/*创建非叶子结点, 建哈夫曼树*/ /*在ht1hti-1的范围内选择两个选择两个weight最小最小 的结点，其序号分别赋值给s1、 s2返回*/select(ht,i-1,s1,s2);hts1.parent=i;hts2.parent=i;hti.LChild=s1;h
14、ti.RChild=s2;hti.weight=hts1.weight+hts2.weight; /*哈夫曼树建立完毕哈夫曼树建立完毕*/CrtHuffmanTree(HuffmanTree*ht,*HuffmanCode,*hc,int*w,intn)哈哈夫夫曼曼树树创创建建算算法法实实现现-38-6.5 6.5 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码一、哈夫曼一、哈夫曼树的定的定义二、哈夫曼二、哈夫曼树的构造的构造三、哈夫曼三、哈夫曼编码和和译码/*分配n个编码头指针*/hcode=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)mal
15、loc(n*sizeof(char); /*分配求当前编码的工作空间*/ cdn-10；/*从右向左逐位存放编码， 首先存放编码结束符*/for(i=1;i=n;i+)/*求求n个叶子结点对应的哈夫曼编码个叶子结点对应的哈夫曼编码*/start=n-1;/*初始化编码起始指针初始化编码起始指针*/for(c=i,p=hti.parent;p!=0;c=p,p=htp.parent)/*从叶子到根结点求编码从叶子到根结点求编码*/if(htp.LChild=c)cd-start=0;/*左分支标左分支标0*/elsecd-start=1;/*右分支标右分支标1*/hcodei=(char*)ma
16、lloc(n-start)*sizeof(char);/*为第为第i个编码分配空间个编码分配空间*/strcpy(hcodei,&cdstart);free(cd);voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)哈哈夫夫曼曼编编码码算算法法实实现现-40- 怎怎样对哈夫曼哈夫曼编码进行行译码？思考题思考题-41- 重点：重点： 1、理解哈夫曼、理解哈夫曼树的定的定义 2、掌握哈夫曼、掌握哈夫曼树的构造方法的构造方法3、掌握哈夫曼、掌握哈夫曼编码难点：点：哈夫曼哈夫曼编码算法并上机算法并上机实现本次课小结本次课小结上机作业：
17、上机作业：上机作业：上机作业： 试为通信系统的信息收发站设计哈夫曼编码系试为通信系统的信息收发站设计哈夫曼编码系试为通信系统的信息收发站设计哈夫曼编码系试为通信系统的信息收发站设计哈夫曼编码系统，并上机调试验证。统，并上机调试验证。统，并上机调试验证。统，并上机调试验证。理论作业：理论作业：理论作业：理论作业： 假定用于通信的电文仅由假定用于通信的电文仅由假定用于通信的电文仅由假定用于通信的电文仅由 8 8 个字母个字母个字母个字母 c1, c2, c1, c2, c3, c4, c5, c6, c7, c8 c3, c4, c5, c6, c7, c8 组成组成组成组成, , 各字母在电文中
18、出各字母在电文中出各字母在电文中出各字母在电文中出现的频率分别为现的频率分别为现的频率分别为现的频率分别为 5, 25, 3, 6, 10, 11, 36, 45, 25, 3, 6, 10, 11, 36, 4。试。试。试。试为这为这为这为这 8 8 个字母设计个字母设计个字母设计个字母设计Huffman Huffman 编码编码编码编码, , 并给出该电文并给出该电文并给出该电文并给出该电文的总码数。的总码数。的总码数。的总码数。作业作业-43-1 1、戴维、戴维、戴维、戴维 哈夫曼哈夫曼哈夫曼哈夫曼 （David A. Huffman David A. Huffman 19251999 19251999） 美国计算机科学家美国计算机科学家美国计算机科学家美国计算机科学家 2 2、适应哈夫曼编码的数据压缩与解压技术研究、适应哈夫曼编码的数据压缩与解压技术研究、适应哈夫曼编码的数据压缩与解压技术研究、适应哈夫曼编码的数据压缩与解压技术研究 3 3、基于动态哈夫曼编码的、基于动态哈夫曼编码的、基于动态哈夫曼编码的、基于动态哈夫曼编码的XMLXML数据流压缩技术数据流压缩技术数据流压缩技术数据流压缩技术 知识拓展知识拓展
