哈夫曼编码.ppt
《哈夫曼编码.ppt》由会员分享,可在线阅读,更多相关《哈夫曼编码.ppt(22页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、哈夫曼编码哈夫曼编码v问题的提出问题的提出v编码简介编码简介v哈夫曼编码方法哈夫曼编码方法编码过程编码过程v构建哈夫曼树构建哈夫曼树 v进行哈夫曼编码进行哈夫曼编码 译码过程译码过程v构建哈夫曼树构建哈夫曼树 v进行哈夫曼译码进行哈夫曼译码 v哈夫曼编码系统哈夫曼编码系统v哈夫曼译码系统哈夫曼译码系统v哈夫曼编码哈夫曼编码/译码例译码例简易哈夫曼编码简易哈夫曼编码/译码系统译码系统问题的提出问题的提出v设计开发一个简易的编码设计开发一个简易的编码/译码系统译码系统该系统模拟单向信息传输通道该系统模拟单向信息传输通道在发送端通过一个编码系统将欲传输的数据进行编码在发送端通过一个编码系统将欲传输的
2、数据进行编码v称欲传输的数据为原码报文称欲传输的数据为原码报文在接收端通过一个译码系统对传来的数据进行译码在接收端通过一个译码系统对传来的数据进行译码(复复原原)v称传来的数据为发送报文称传来的数据为发送报文v如图所示如图所示v对该系统首先明确编码的基本概念对该系统首先明确编码的基本概念返回开头返回开头一个简易编码一个简易编码/译码系统图示译码系统图示编码系统编码系统发送端发送端译码系统译码系统接收端接收端原码报文原码报文发送报文发送报文原码报文原码报文通信通道通信通道返回问题的提出返回问题的提出编码简介编码简介v什么是编码什么是编码将源对象内容用预先规定的方法转换成另一种格式的过将源对象内容
3、用预先规定的方法转换成另一种格式的过程程v称这种预先规定的方法为编码方法称这种预先规定的方法为编码方法编码方法有多种编码方法有多种本问题采用哈夫曼编码方法本问题采用哈夫曼编码方法v什么是哈夫曼编码方法什么是哈夫曼编码方法1952年由年由美国计算机科学家戴维美国计算机科学家戴维哈夫曼哈夫曼先生提出先生提出是一种数据压缩技术是一种数据压缩技术该方法依据字符出现的概率进行编码该方法依据字符出现的概率进行编码,其基本思想为:,其基本思想为:v出现概率高的字符使用较短的编码出现概率高的字符使用较短的编码v出现概率低的则使用较长的编码出现概率低的则使用较长的编码v使编码之后的码字的平均长使编码之后的码字的
4、平均长 度最短度最短v本问题的简易系统也可以如图所示本问题的简易系统也可以如图所示返回开头返回开头一个简易哈夫曼编码一个简易哈夫曼编码/译码系统图示译码系统图示哈夫曼编码系统哈夫曼编码系统发送端发送端哈夫曼译码系统哈夫曼译码系统接收端接收端原码报文原码报文发送报文发送报文原码报文原码报文通信通道通信通道返回编码简介返回编码简介返回返回哈夫曼编码方法哈夫曼编码方法v哈夫曼编码方法包含两个过程哈夫曼编码方法包含两个过程编码过程和译码过程编码过程和译码过程v编码过程编码过程构建哈夫曼树构建哈夫曼树 CreatHT(W,&HT)v输入是字符频度表输入是字符频度表W表中记录的是原码报文中出现的不同符号个
5、数和频率表中记录的是原码报文中出现的不同符号个数和频率v输出是哈夫曼树输出是哈夫曼树HT进行哈夫曼编码进行哈夫曼编码 HuffmanCoding(HT,&HC)v输入是哈夫曼树输入是哈夫曼树HTv输出是字符编码表输出是字符编码表HCv译码过程译码过程返回开头返回开头哈夫曼编码方法哈夫曼编码方法v哈夫曼编码方法包含两个过程哈夫曼编码方法包含两个过程编码过程和译码过程编码过程和译码过程v编码过程编码过程v译码过程译码过程构建哈夫曼树构建哈夫曼树 CreatHT(W,&HT)v输入是字符频度表输入是字符频度表W表中记录的是原码报文中出现的不同符号个数和频率表中记录的是原码报文中出现的不同符号个数和频
6、率v输出是哈夫曼树输出是哈夫曼树HT进行哈夫曼译码进行哈夫曼译码 HuffmanDecod(HT,CC,W,&OC)v输入的是哈夫曼树输入的是哈夫曼树HT、代码报文、代码报文CC和字符频度表和字符频度表Wv输出的是原码报文输出的是原码报文OC返回开头返回开头构建哈夫曼树构建哈夫曼树v构建哈夫曼树构建哈夫曼树 CreatHT(W,&HT)输入是字符频度表输入是字符频度表Wv表中记录的是原码报文中出现的不同符号个数和频率表中记录的是原码报文中出现的不同符号个数和频率输出是哈夫曼树输出是哈夫曼树HTv例:例:假设用于通信的电文仅由假设用于通信的电文仅由4个字母个字母 a,d,i,n 构成,它们构成,
7、它们在电文中出现的概率分别为在电文中出现的概率分别为 2,7,5,4,试试构建相应的哈构建相应的哈夫曼树,以便夫曼树,以便为这为这4个字母个字母进行哈夫曼编码进行哈夫曼编码字符频度表为:字符频度表为:W=(a,2),(),(d,7),(),(i,5),(),(n,4)v哈夫曼算法哈夫曼算法返回开头返回开头构建哈夫曼树例一构建哈夫曼树例一2754adin624116245187116245anid返回构建哈夫曼树返回构建哈夫曼树4个字母个字母 a,d,i,n 在电文中出现的概率分别为在电文中出现的概率分别为 2,7,5,4哈夫曼算法哈夫曼算法v根据给定的根据给定的 n 个权值个权值 w1,w2,
8、wn,构成,构成 n 棵二棵二叉树的集合叉树的集合 F=T1,T2,Tn,其中每棵二叉树,其中每棵二叉树Ti中只有一个带权为中只有一个带权为 wi的根结点,其左右子树均的根结点,其左右子树均为空为空v在在 F 中选取两棵根结点的权值最小的树作为左右子中选取两棵根结点的权值最小的树作为左右子树,构造一棵新的二叉树,且置新的二叉树的根结树,构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和点的权值为其左、右子树上根结点的权值之和v在在 F 中删除这两棵树,同时将新得到的二叉树加入中删除这两棵树,同时将新得到的二叉树加入 F 中中v重复重复(2)和和(3),直到,直到
9、F 只含一棵树为止只含一棵树为止这棵树便是所求的这棵树便是所求的哈夫曼树哈夫曼树 返回构建哈夫曼树返回构建哈夫曼树构建哈夫曼树例二构建哈夫曼树例二625977529752166713671397521630v对对5个权值个权值 5,6,2,9,7 构造哈夫曼树的过程构造哈夫曼树的过程返回返回T1T2T3T4T5T6T7T8T9哈夫曼编码哈夫曼编码v例:例:假设用于通信的电文仅由假设用于通信的电文仅由4个字母个字母 a,d,i,n 构成,它们构成,它们在电文中出现的概率分别为在电文中出现的概率分别为 2,7,5,4,试试构建相应的哈构建相应的哈夫曼树,并夫曼树,并为这为这4个字母个字母进行哈夫曼
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 编码
限制150内