霍夫曼编码的C语言实现.pdf

《霍夫曼编码的C语言实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

《信息处理与编码》结课大作业学号：班级：姓名：成绩：霍夫曼编码的C语言实现1.编码原理霍夫曼码由霍夫曼树构造，平均码长是霍夫曼树的带权 路径长度，由于霍夫曼树是权最小的树，故其压缩效果最好。霍夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的。霍夫曼码是用概率匹配方法进行信源编码。有两个明显特点：一是保证了概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。霍夫曼变长码的效率很高，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也易实现，但要注意，更高效率的编码仍须按长序列来计算，这样才能使平均码字降低。2.霍夫曼编码的步骤（l）将信号源的符号按照出现概率递减的顺序排列。（2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。（3）重复进行步骤1和2直到概率相加的结果等于1为止。（4）在合并运算时，概率大的符号用编码0表示，概率小 的符号用编码1表示。（5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。例如：设信号源为s＝｛s1,s2,s3,s4,s5｝对应的概率为p＝｛0.25，0.22，0.20,0.18，0.15｝。根据字符出现的概率来构造平均长度最短的异字头码字。霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。3.编码程序#include#include#include#include#includetypedefstruct{unsignedintweight;nsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode; typedefstruct{unsignedints1;unsignedints2;}MinCode;voidError(char*message);HuffmanCodeHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,unsignedint*w,unsignedintn);MinCodeSelect(HuffmanTreeHT,unsignedintn);voidError(char*message){clrscr();fprintf(stderr,"Error:%s ",message);exit(1);}HuffmanCodeHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,unsignedint*w,unsignedintn){unsignedinti,s1=0,s2=0;HuffmanTreep;char*cd;unsignedintf,c,start,m;MinCodemin; if(n<=1)Error("Codetoosmall!");m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT,i=0;i<=n;i++,p++,w++){p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;i++,p++){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;i++){min=Select(HT,i-1);s1=min.s1;s2=min.s2;HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight; }printf("HTList: ");printf("Numberttweightttparentttlchildttrchild ");for(i=1;i<=m;i++)printf("%dtt%dtt%dtt%dtt%d ",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char*));cd[n-1]='';for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char*));strcpy(HC[i],&cd[start]);}free(cd);returnHC;}MinCodeSelect(HuffmanTreeHT,unsignedintn){unsignedintmin,secmin;unsignedinttemp;unsignedinti,s1,s2,tempi; MinCodecode;s1=1;s2=1;for(i=1;i<=n;i++)if(HT[i].parent==0){min=HT[i].weight;s1=i;break;}tempi=i++;for(;i<=n;i++)if(HT[i].weights2){temp=s1;s1=s2;s2=temp;}code.s1=s1;code.s2=s2;returncode;}voidmain(){HuffmanTreeHT=NULL;HuffmanCodeHC=NULL;unsignedint*w=NULL;unsignedinti,n;clrscr();printf("Inputn: ");scanf("%d",&n);w=(unsignedint*)malloc((n+1)*sizeof(unsignedint*));w[0]=0;printf("Enterweight: ");for(i=1;i<=n;i++){ printf("w[%d]=",i);scanf("%d",&w[i]);}HC=HuffmanCoding(HT,HC,w,n);printf("HuffmanCode: ");printf("NumberttWeightttCode ");for(i=1;i<=n;i++)printf("%dtt%dtt%s ",i,w[i],HC[i]);}程序运行：首先用户先输入一个数n，以实现n个节点的HuffmanTree之后输入权值w[1]~w[n]，注意是unsignedint型数值。然后程序自动生成HuffmanTree的存储形式的一张表格。最后是HuffmanCoding。SampleInput:Inputn:8Enterweight:w[1]=5w[2]=29w[3]=7w[4]=8w[5]=14w[6]=23w[7]=3 w[8]=11SampleOutput::如表1HTListNumberweightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314如表二HuffmanCode:NumberWeightCode15011022910371110 48111151411062300730111811010