霍夫曼编码原理.docx

霍夫曼编码四川大学计算机学院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，那么他的父节点必然是myHuffmantree[i].parent，如果i是myHuffmantree[i].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霍夫曼编码源代码：#includeiostream#includecstring#includealgorithm#includemapusing namespace std;#define INF 0x7fffffff //无穷大struct Huffmantree //霍夫曼树的节点{int weight;int parent,ld,rd;};struct myNode {char ch;int num;};struct mycode //字符和其对应的编码{ char ch; //字符 int s[50]; //ch的编码 int len; //编码长度};int nNode; //叶子节点数目int totalNode; //霍夫曼树的总节点个数char