07第07部分树贪心07_哈夫曼树_第1页
07第07部分树贪心07_哈夫曼树_第2页
07第07部分树贪心07_哈夫曼树_第3页
07第07部分树贪心07_哈夫曼树_第4页
07第07部分树贪心07_哈夫曼树_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

哈夫曼树,1,数据结构与算法365特训营,2,哈夫曼树,知识点概述,通常的编码方法有固定长度和不等长度编码两种。最优编码方案的目的是使总码长度最短。利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需要位。例如三个不同的字符a,b,c，至少需要2位二进制数表示：a:00，b:01，c:10。如果每个字符的使用频率相等的话，固定长度编码是空间效率最高的方法。,3,哈夫曼树,知识点概述,不等长编码方法需要解决两个关键问题：（1）编码尽可能的短使用频率高的字符编码较短，使用频率低的编码较长，可提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。（2）不能有二义性解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。,4,哈夫曼树,知识点概述,1952年，数学家D.A.Huffman提出了用字符在文件中出现的频率来建议一个用0，1串表示各字符的最佳编码方式，称为Huffman编码。哈夫曼编码很好的解决了上述两个关键问题，广泛地应用于数据压缩，尤其是远距离通信和大容量数据存储，常用的JPEG图片就是采用哈夫曼编码压缩的。哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。,5,哈夫曼树,知识点概述,构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权值，以自底向上的方式，通过n-1次的“合并”运算后构造出的树。核心思想是让权值大的叶子离根最近。哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中。,6,哈夫曼树,知识点概述,7,哈夫曼树,知识点概述,确定合适的数据结构。哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点(n-1次的“合并”，每次产生一个新结点)。构成哈夫曼树后，为求编码需从叶子结点出发走一条从叶子到根的路径。译码需要从根出发走一条从根到叶子的路径。那么对于每个结点而言，需要知道每个结点的权值、双亲、左孩子、右孩子和结点的信息。,8,哈夫曼树,知识点概述,9,哈夫曼树,知识点概述,10,哈夫曼树,知识点概述,11,哈夫曼树,知识点概述,12,作业,1
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论