哈夫曼编码.doc
哈夫曼编码一、概述哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。二、C语言程序实现文件的huffman编码#include <stdio.h>#define MAX 1000#define MAXSYMBS 30#define MAXNODE 59typedef structint weight;int flag;int parent;int lchild;int rchild;huffnode;typedef struct int bitsMAXSYMBS; int start;huffcode;void main() huffnode huff_nodeMAXNODE; huffcode huff_codeMAXSYMBS,cd; int i,j,m1,m2,x1,x2,n,c,p; /*char symbsMAXSYMBS,symb;*/ /*数组buff_node初始化*/ printf("please input the leaf num of tree:n"); scanf("%d",&n); for(i=0;i<2*n-1;i+) huff_nodei.weight=0;huff_nodei.parent=0;huff_nodei.flag=0;huff_nodei.lchild=-1;huff_nodei.rchild=-1; printf("please input the weight of every leafn"); for(i=0;i<n-1;i+) scanf("%d",&huff_nodei.weight); /*构造哈弗曼树*/ for(i=0;i<n-1;i+) m1=m2=MAX; x1=x2=0; for(j=0;j<n+i;j+) if(huff_nodej.weight <m1&&huff_nodej.flag =0) m2=m1; x2=x1; m1=huff_nodej.weight ; x1=j; else if (huff_nodej.weight <m2&&huff_nodej.flag =0) m2=huff_nodej.weight; x2=j; huff_nodex1.parent=n+i; huff_nodex2.parent=n+i; huff_nodex1.flag =1; huff_nodex2.flag =1; huff_noden+i.weight =huff_nodex1.weight +huff_nodex2.weight ; huff_noden+i.lchild =x1; huff_noden+i.rchild =x2; /*求字符的哈弗曼编码*/ for(i=0;i<n;i+) cd.start =n;c=i;p=huff_nodec.parent ;while(p!=0)if(huff_nodep.lchild =c)cd.bits cd.start =0;else cd.bits cd.start =1;cd.start=cd.start -1;c=p;p=huff_nodep.parent ;cd.start +;for(j=cd.start ;j<=n;j+)huff_codei.bitsj=cd.bits j;huff_codei.start =cd.start ; /*输出字符的哈弗曼编码*/ puts("the hafman code are:"); for(i=0;i<n;i+) for(j=huff_codei.start;j<=n;j+)printf("%10d",huff_codei.bits j); printf("/n"); puts("press any key to quit."); 三、运行界面please input the leaf num of tree：8please input the weight of every leaf1 2 3 4 5 6 7 1输出：110101100100101111000111011
