哈夫曼编码课件

1、第五章 哈夫曼树Huffman Tree,信息与通信工程学院 湖南理工学院 2020/7/12,2,目标,熟悉哈夫曼树构造方法及 熟悉哈夫曼编码译码应用,3,Huffman最优二叉树,Huffman树：n个外部（叶子）结点，权值为w1,w2,w3,wn，构造一棵二叉树，使得所有外部结点的带权路径长度最小。 例：给4个叶子结点，权为2,3,4,11,53,2*2+11*2+3*2+4*2=40,4,Huffman最优二叉树,Huffman树：n个外部（叶子）结点，权值为w1,w2,w3,wn，构造一棵二叉树，使得所有外部结点的带权路径长度最小。 例：给4个叶子结点，权为2,3,4,11,11,4

2、,2,3,11+4*2+(2+3)*3=34,5,Huffman最优二叉树,最优二叉树的特征： 权越小的外部结点离根越远。 Huffman 构造方法： 贪心策略+自底向上,6,7,Huffman算法,n个外部结点，初始时，孤立形成n棵树。 每次选择根结点权值最小的两棵树，进行合并，权值之和构成合并后的根。 每次合并，减少1棵树，故一共需合并n-1次。,5,29,7,8,14,23,3,11,8,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,5,29,7,8,14,23,3,11,9,例题,8个叶子结点，权值W=5, 29, 7, 8,

3、 14, 23, 3, 11 构造huffman树。,3,29,7,8,14,23,5,11,8,10,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,3,29,7,8,14,23,5,11,8,15,11,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,3,29,7,14,23,5,8,15,11,8,19,12,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,3,29,7,23,5,8,15,11,8,19,14,29

4、,13,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,3,29,7,5,8,15,11,8,19,14,29,23,42,14,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,3,29,7,5,8,15,11,8,19,14,29,23,42,58,15,例题,8个叶子结点，权值W=5, 29, 7, 8, 14, 23, 3, 11 构造huffman树。,3,29,7,5,8,15,11,8,19,14,29,23,42,58,100,16,树的(动态)链式存储结构,17,

5、静态链表存储结构,E,A,B,C,D,F,下标作为静态指针,孩子为-1表示？,父亲为-1表示？,18,Huffman树构造算法,5,2,7,3,19,Huffman树构造算法,5,2,7,3,5,20,Huffman树构造算法,5,2,7,3,5,10,21,Huffman树构造算法,5,2,7,3,5,10,17,22,Huffman编码,Huffman 编码树 例：D=A,B, M W=2,3,5,7,11,13,17,19,23,29,31,37,41,23,Huffman 编码树,D=A,B, M W=2,3,5,7,11,13,17,19,23,29,31,37,41,24,Huff

6、man编码,Huffman 编码树 例：D=A, M W=2,3,5,7,11,13,17,19,23,29,31,37,41 利用Huffman算法构造出的各字符的二进制编码为： A: 1011110 B: 1011111 C: 101110 D: 10110 E: 0100 F: 0101 G: 1010 H: 000 I: 001 J: 011 K: 100 L2: 110 M: 111,通信编码总长最短;（L=Wili ） 若didj, 则di不是dj的前缀编码。,25,Huffman编码,字符Huffman编码表： A: 1011110 B: 1011111 C: 101110 D:

7、 10110 E: 0100 F: 0101 G: 1010 H: 000 I: 001 J: 011 K: 100 L2: 110 M: 111 输入正文：ABDEH 查找：字符编码表 得到编码： 10111101011111101100100000,26,Huffman解码,10111101011111101100100000,解码：ABDEH,27,应用举例,明文 A computer program is a sequence of instructions written to perform a specified task with a computer. The program

8、 has an executable form that the computer can use directly to execute the instructions. Computer source code is often written by computer programmers. Source code may be converted into an executable file by a compiler and later executed by a central processing unit.,28,Huffman编码,00111101011001011001

9、101011000100001111011101111010001101110011110011101101001010111000011110111001001101110101100111101100000110010010101111010011000001100001001011101111110110000010111110001100100101110111000111111011000111111111011001011011111001110100010111011100000100110111010111001001101110110001011010100011000000

10、001011101001110111101001110111100100011000111110001111110000111001001100101100110101100010000111101110110011001101110010011000010111101000110111001111001110110100101011101000010100111011100100001011001100110101101010000111101001010001110000111101000001001101110101110111110000101001111110111110000101

11、111001011001101011000100001111011101111001010100001011000001110101111010100100011011011010111111110000011101101111100111001100110101101010000111101111011111000010111100001001011101111110110000010111110001100100101110100110011011100101010011010110001000011110111011110111011001000010110101011110010110

12、011010010111100001111011101001100000111101100101100011111101100011111111101100101101010000011101100101100110101100010000111101110111101000110111001111001110110100101011010101110111110100110011011100101110010000101101010111100101100110100101111010101010000111011010100001111001011001001000111100011101

13、111110111010011100001001011111001110010000101100110011010110101000011110100101000111000011110100000000111100001111010100000111011001001100101100110101100010001111000011101111001000010101001110111000010011110111011110011001101011010100001111011101001110101000001110110010011001010110010111110110100111

14、0001101000110111001010101111101111010001001011100111100000001000011111001100,29,Huffman译码,A computer program is a sequence of instructions written to perform a specified task with a computer. The program has an executable form that the computer can use directly to execute the instructions. Computer

15、source code is often written by computer programmers. Source code may be converted into an executable file by a compiler and later executed by a central processing unit.,30,设计思路,生成明文的字符+权集 构造Huffman树（贪心法+自底向上） 利用Huffman树，对明文进行编码 利用huffman树，对编码译码为明文,31,设计思路,生成明文的字符+权集 字符表：包括字符项和权值项。,#define N 30 stru

16、ct charcode /字符表 char c; /字符 int w; /权值 ; struct charcode ctableN; /全局变量：明文中出现的字符个数。 int num=0;,32,在字符表中查找字符,/ 在字符表中查找字符, /成功找到则返回字符位置;不成功返回-1 int find(char ch) int i; for(i=0;ctablei.c!=0;i+) if(ctablei.c=ch) /找到字符 return i; return i; /未找到 ,33,计算字符出现频率,/ 在字符表中查找字符,成功返回字符位置;不成功返回0 void getweight() c

17、har ch; freopen(plaintext.txt,r,stdin); while(ch=getchar()!=EOF) int i=find(ch); /查找字符位置 if(!ctablei.c) /若字符表相应位置未存放字符 ctablei.c=ch; /存入字符 num+; /字符数加1 ctablei.w+; /权值加1 ,34,构造huffman树,构造Huffman树 Huffman树结构：字符,权,父亲下标,左孩子下标,右孩子下标,struct treenode /静态链表 char c; /char int w; /weight int f;/father int l;

18、 /left child index int r; /right child index ; /N个外部结点,总结点不超过2N-1 struct treenode htree2*N-1;,35,按权值排序,/ 使用选择法进行排序。 void sort() int i,j; struct charcode t; for(i=0;inum;i+) /每次选择最小的权值 int m=i; /m记录最小权值的下标 for(j=i+1;jnum;j+) if(ctablej.wctablem.w) m=j; t=ctablem; ctablem=ctablei; ctablei=t; ,36,构建huf

19、fman树,/使用贪心法建立huffman树,每次选择权值最小的根结点 void huffman() int i,j,k,n; for(i=0; inum; i+) /初始化哈夫曼表 htreei.c=ctablei.c; htreei.w=ctablei.w; htreei.l=htreei.f=htreei.r=-1; j=0; /j记录叶子结点的下标 k=num; /k记录内部结点的下标 for(n=num;n2*num-1;n+) /每次选择权值最小 int r=0,s=0; htreen.l=htreen.f=htreen.r=-1;,37,构建huffman树,while(rhtr

20、eej.w) ,38,构建huffman树,htreen.w=s; /父亲的权值 ,39,Huffman编码,Huffman编码,/ 从plaintext.txt中读入明文, 生成编码, 存入telegraph.txt中 void encode() char ch; freopen(plaintext.txt,r,stdin); freopen(telegraph.txt,w,stdout); while(ch=getchar()!=EOF) int i=find(ch); char strN; getcode(i,str); printf(%s,str); ,40,Huffman编码,/根据字符所在的下标，从叶子结点往上搜索到根节点 /然后逆置得到该字符的huffman编码 void getcode(int i, char *str) int n,j,l=0; for(n=i;htreen.f!=-1;n=htreen.f)/沿着父亲往上搜索 int m=htreen.f; if(n=htreem.l) strl+=0; /左孩子记为0 else strl+=1; /右孩子记为1 ,41,Hu