哈夫曼编码.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个字母个字母进行哈夫曼

10、编码进行哈夫曼编码v构建哈夫曼树构建哈夫曼树v进行哈夫曼编码进行哈夫曼编码按左分支为按左分支为0、右分支为、右分支为1的规则对哈夫曼树的左右分支的规则对哈夫曼树的左右分支进行标记进行标记将从根结点到叶子结点的路径上所有分支标记组成一个将从根结点到叶子结点的路径上所有分支标记组成一个代码序列代码序列v这个序列就是该叶子结点对应的字符的编码这个序列就是该叶子结点对应的字符的编码返回开头返回开头哈夫曼编码例一哈夫曼编码例一187116245anid4个字母个字母 a,d,i,n 在电文中出现的概率分别为在电文中出现的概率分别为 2,7,5,4 字符编码表字符编码表HC=(d,0),(i,10),(a

11、,110),(n,111)000111010110111返回返回字母字母d的编码为的编码为0字母字母i的编码为的编码为10字母字母a的编码为的编码为110字母字母n的编码为的编码为111可见：可见：在电文中出现频率高的字在电文中出现频率高的字母其对应叶子结点离根结母其对应叶子结点离根结点近；出现频率低的字母点近；出现频率低的字母其对应叶子结点离根结点其对应叶子结点离根结点远远因此，在电文中出现频率因此，在电文中出现频率高的字母的编码相对短，高的字母的编码相对短，而出现频率低的字母的编而出现频率低的字母的编码相对长码相对长可以看出，概率大的符号其编码短，概率小的符号其可以看出，概率大的符号其编码

12、短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的2.2.2 哈夫曼编码哈夫曼编码v哈夫曼编码过程演示哈夫曼编码过程演示A1A1A2A2A3A3A4A4A5A5A6A6A7A70.230.230.210.210.180.180.150.150.130.130.070.070.030.03 1 1 0 00.100.101 1 0 00.230.23 1

13、1 0 00.330.33 1 1 0 00.440.44 1 1 0 00.560.560 0 1 11 1编码编码编码编码 01 01 00 00 111 111 110 110 101 1011001100110001000练习练习 设设某某信信源源有有5种种符符号号x=A1，A2，A3，A4，A5。在在数数据据中中出出现现的的概概率率p=0.25，0.22，0.20，0.18，0.15，试试给给出出Huffman编码方案，写出每个符号对应的编码方案，写出每个符号对应的Huffman编码。编码。答案答案1：A1:10 A2:01 A3:00 A4:111 A5:110答案答案2：A1:0

14、1 A2:10 A3:11 A4:000 A5:001哈夫曼译码哈夫曼译码v接收端接收的是代码报文和字符频度表接收端接收的是代码报文和字符频度表代码报文为代码报文为11010111010111010111110010001001110 字符频度表为字符频度表为(a,2),(d,7),(i,5),(n,4)v构建哈夫曼树构建哈夫曼树v哈夫曼译码哈夫曼译码逐个扫描代码报文逐个扫描代码报文按遇按遇0向左、遇向左、遇1向右的规则从根出发走一向右的规则从根出发走一条从根到叶子结点的路径条从根到叶子结点的路径与路径对应的代码段就是叶子结点对应字与路径对应的代码段就是叶子结点对应字符的编码符的编码对照字符频

15、度表得到相应字符的原码对照字符频度表得到相应字符的原码继续继续187116245anid返回返回返回开头返回开头哈夫曼译码例哈夫曼译码例11010111010111010111110010001001110返回返回187116245anid原码报文：原码报文：aindindinadiddidnd看方法看方法aindindinad iddidnd哈夫曼编码系统哈夫曼编码系统v输入输入原码报文原码报文OCv形成字符频度表形成字符频度表W根据原码报文根据原码报文OCv构建哈夫曼树构建哈夫曼树根据字符频度表根据字符频度表Wv进行哈夫曼编码进行哈夫曼编码根据字符频度表根据字符频度表W和哈夫曼树和哈夫曼树

16、HTv形成代码报文形成代码报文CC根据原码报文根据原码报文OC和字符编码表和字符编码表HCv输出输出发送报文发送报文v字符频度表字符频度表W原码报文中出现的不同符号个数和频率原码报文中出现的不同符号个数和频率v代码报文代码报文CC输入原码报文输入原码报文形成字符频度表形成字符频度表构建哈夫曼树构建哈夫曼树进行哈夫曼编码进行哈夫曼编码形成代码报文形成代码报文输出输出CC和和WOCWHTWHCOCCC到哈夫曼译码系统到哈夫曼译码系统来自哈夫曼译码系统外来自哈夫曼译码系统外简易哈夫曼编码简易哈夫曼编码/译码系统译码系统哈哈夫夫曼曼编编码码系系统统功功能能流流程程返回开头返回开头哈夫曼译码系统哈夫曼译

17、码系统v输入输入代码报文代码报文CC和字符频度表和字符频度表Wv构建哈夫曼树构建哈夫曼树根据字符频度表根据字符频度表Wv进行哈夫曼译码形成原码报文进行哈夫曼译码形成原码报文OC根据代码报文根据代码报文CC哈夫曼树哈夫曼树HT字符频度表字符频度表Wv输出输出原码报文原码报文OC输入输入W、CC构建哈夫曼树构建哈夫曼树进行哈夫曼译码进行哈夫曼译码形成原码报文形成原码报文输出输出OCHTWOC到哈夫曼译码系统之外到哈夫曼译码系统之外来自哈夫曼编码系统来自哈夫曼编码系统简易哈夫曼编码简易哈夫曼编码/译码系统译码系统哈哈夫夫曼曼编编码码系系统统功功能能流流程程返回开头返回开头WCC哈夫曼编码哈夫曼编码/

18、译码例译码例v发送端：发送端：接收的原码报文接收的原码报文0C=uvuwxxxvywyuyyvxxyxxuxuvvyvxy求出字符频度表求出字符频度表W=(u,5)，(v,6)，(w,2)，(x,9)，(y,7)构建哈夫曼树构建哈夫曼树HT求出字符编码表求出字符编码表HC=(u,110),(v,00),(w,111),(x,10),(y,01)求出代码报文求出代码报文671397521630uvyxw00001111CC=11000110111101010000111101110010100101001101011010110000001001001111110100100返回开头返回开头接收

19、端接收端哈夫曼编码哈夫曼编码/译码例译码例v接收端接收端:接收代码报文接收代码报文CC11000110111101010000111101110010100101001101011010110000001001001 接收字符频度表接收字符频度表W(u,5)，(v,6)，(w,2)，(x,9)，(y,7)构建哈夫曼树构建哈夫曼树HT求出原码报文求出原码报文OCuvuwxxxvywyuyyvxxyxxuxuvvyvxy发送端发送端671397521630uvyxw00001111返回开头返回开头v一个编码一个编码/译码简易系统译码简易系统编码系统编码系统发送端：发送端：译码系统译码系统接收端：接收端：原码报文原码报文发送报文发送报文发送报文发送报文原码报文原码报文代码报文代码报文+字符频度表字符频度表代码报文代码报文+字符频度表字符频度表