霍夫曼编码原理.docx

霍夫曼编码 四川大学2009级戚辅光 0943041196 霍夫曼编码 四川大学计算机学院2009级戚辅光【关键字】霍夫曼编码原理 霍夫曼译码原理 霍夫曼树 霍夫曼编码源代码 霍夫曼编码分析 霍夫曼编码的优化 霍夫曼编码的应用【摘要】哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。它属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。【正文】引言哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。霍夫曼编码原理：霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2*n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantreei.parent，如果i是myHuffmantreei.parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了。霍夫曼树：下面是字符串agdfaghdabsb的霍夫曼编码的霍夫曼树：字符串：agdfaghdabsb 出现的字符 字符出现的次数 a3g2d2f1h1b2s1合计12由上面的霍夫曼树可知各个字符的编码如下：a: 01b:010d:011f:100g:101h:110s:111所以整个串的编码为：011010111000110111001101010111010霍夫曼译码原理：对于霍夫曼的译码，可以肯定的是其译码结果是唯一的。证明：因为霍夫曼编码是根据霍夫曼树来确定的，霍夫曼树是一棵二叉树，编码的时候是从树根一直往下走，直到走到叶子节点为止，在其经过的路径上，如果是树的左子树则为0，否则为1。因为每一次都要走到树的叶子节点，多以不可能存在两个编码a和b，使得a是b的前缀或者b是a的前缀。所以编码一定可以唯一确定。根据上面的结论，我们可以很清楚地直到译码的方法：定义两个指针p1,p2，P1指向当前编码的开始位置，P2指向当前编码的位置，如果P1-P2这一段编码能在编码库里面找到完全对应的编码结果，则译码成功，该段编码的译码结果就是与编码库里完全对应的编码的字符。循环次操作，直到译码结束！例一：假设有一段字符含有a,c,d三个字符，经过编码之后三个字符对应的编码结果分别为：a:01c:010d:011现在给你一段编码0110101，要求将其译码！按照上面介绍的方法我们可以直到：编码的前三个字符是且仅是d的编码，所以011译码为d，依次译码可得整串的译码结果为daa霍夫曼编码源代码：#include#include#include#includeusing namespace std;#define INF 0x7fffffff /无穷大 struct Huffmantree /霍夫曼树的节点 int weight;int parent,ld,rd;struct myNode char ch;int num;struct mycode /字符和其对应的编码 char ch; /字符 int s50; /ch的编码 int len; /编码长度 ;int nNode; /叶子节点数目int totalNode; /霍夫曼树的总节点个数char toCode100000 ; /待编码的字符串myNode myToCode100000; /待编码的字符串和权值int weightOfToCode100000 ; /字符串的权值！Huffmantree myHuffmantree1000000; /霍夫曼树(数组模拟)char allchar1000000; /所哟出现过的字符 mycode coder1000000; /字符与对应的编码 int Len; /待编码的字符的总长度 int Coding100000; /译码之后的01串 int lenOfCoding ; /01串的长度 void build(int n); /建立霍夫曼树 void select(int &a,int &b); /选择两个权值最小的节点 void Code(); /编码 void printCode(); /打印编码void deCode(); /译码 int match(int l,int h);int main() int i;coutn=霍夫曼编码程序=; coutn 作者：戚辅光endl; cout 时间：2010-11-23endl; while(1)printf(请输入待编码的字符串n);int flag=0;gets(toCode);int len=strlen(toCode);if(len=1) flag=1; Len=len; mapmyMap;for(i=0;ilen;i+) /统计字符串中各字符出现的频次！myMaptoCodei+;map:iterator iter;int h=1;for(iter=myMap.begin();iter!=myMap.end();iter+) myToCodeh.ch=iter-first;allcharh=iter-first;weightOfToCodeh=iter-second;myToCodeh+.num=iter-second;nNode=h-1; /叶子节点个数cout-字符统计如下-endl;cout 字符 次数endl;for(i=1;ih;i+) /显示将要编码的字符串中的各字符和他出现的次数！cout myToCodei.ch myToCodei.numendl;coutendl;totalNode=nNode; /totalNode初始值为nNodecout-霍夫曼树节点信息如下(子节点为-1表示是叶子节点)-endlendl; build(nNode);coutendl;Code();coutn-字符串的编码结果如下-n;printCode();coutn-01串的译码结果如下-n; deCode();coutcon; char fang=toupper(con0); if(fang=N) break; getchar();return 0;void build(int n) /建立霍夫曼树int i;int m=2*n-1; /n个叶子节点的霍夫曼树总节点数为2*n-1for(i=1;i=n;i+) /初始化霍夫曼数组myHuffmantreei.weight=weightOfToCodei; /叶子节点权值为字符出现次数myHuffmantreei.ld=-1; /叶子节点没有左孩子myHuffmantreei.rd=-1; /叶子节点没有右孩子myHuffmantreei.parent=i; /叶子节点父节点先初始化为他本身for(i=n+1;i=m;i+)int a,b;select(a,b);myHuffmantreea.parent=i;myHuffmantreeb.parent=i;myHuffmantreei.ld=a;myHuffmantreei.rd=b;myHuffmantreei.weight=myHuffmantreea.weight+myHuffmantreeb.weight;myHuffmantreei.parent=i;for(i=1;i=totalNode;i+)printf(节点：%3d 权值： %3d 左节点： %3d 右节点：%3d 父节点： %3d n,i,myHuffmantreei.weight,myHuffmantreei.ld,myHuffmantreei.rd,myHuffmantreei.parent);void Code() /编码 int i,j; int numOfCode100000; cout-各字符编码结果如下-endl; if(Len=1) couttoCode0 : 0n; return ; for(i=1;i=nNode;i+) j=i; int h=0; while(myHuffmantreej.parent!=j) int x=j;j=myHuffmantreej.parent;if(myHuffmantreej.ld=x)numOfCodeh+=0;else if(myHuffmantreej.rd=x)numOfCodeh+=1; cout allchari=0;k-) coderi.sx+=numOfCodek; printf(%d,numOfCodek); coutendl; void select(int &a,int &b) /选择两个权值最小的节点int i;int min1=INF;int min2=INF;int sign1=1; /最小值的下标int sign2=2; /次小值的下标for(i=1;i=totalNode;i+)if(myHuffmantreei.parent=i) /说明其是已经更新过的节点if(myHuffmantreei.weightmin1)min1=myHuffmantreei.weight;sign1=i;for(i=1;i=totalNode;i+)if(myHuffmantreei.parent=i) /说明其是已经更新过的节点if(myHuffmantreei.weightmin2&i!=sign1)min2=myHuffmantreei.weight;sign2=i;a=sign1;b=sign2;totalNode+; /总节点数加1void printCode() /打印编码结果！ int i; if(Len=1) /长度为1的时候特殊考虑 cout0n; return ; int h=0; for(i=0;iLen;i+) for(int j=1;j=nNode;j+) if(toCodei=coderj.ch) for(int k=0;kcoderj.len;k+) printf(%d,coderj.sk); Codingh+=coderj.sk; lenOfCoding=h; coutendl;void deCode() /译码 int i,j; int begin=0; for(i=0;ilenOfCoding;i+) if(match(begin,i)!=-1) int x=match(begin,i); printf(%c,coderx.ch); begin=i+1; printf(n); int match(int l,int h) /译码的辅助函数（寻找匹配） int i,j,k; int flag=0; for(i=1;i=nNode;i+) if(coderi.len!=h-l+1) continue; k=l; for(j=0;jcoderi.len;j+) if(Codingk!=coderi.sj) break; if(j=coderi.len-1) flag=1; goto ok; k+; ok:; if(flag=1) /查找成功返回对应的下表 return i; else /查找不成功返回-1； return -1; 霍夫曼编码代码分析：1. 运行环境：win7操作系统，Inter(R) Core(TM) Duo t6600 2.20GHz 2.20GHz 内存：2.00GB，32位操作系统2. 程序运行结果：3. 程序功能模块分析：整个程序包含6个函数：A void build(int n); B void select(int &a,int &b);C void Code(); D void printCode();E void deCode(); F int match(int l,int h);其中A是用来建立霍夫曼树，B是在A中调用的一个辅助函数，用来查找两个权值最小的节点的下标，C是对字符串编码，D是现实编码结果，E是译码01串,F是E的辅助函数，用来寻找编码的匹配。包含3个结构体：Astruct Huffmantree /霍夫曼树的节点 int weight;int parent,ld,rd;Bstruct myNode /字符和其权值char ch; /字符int num; /权值; Cstruct mycode /字符和其对应的编码 char ch; /字符 int s50; /ch