Huffman编解码实验报告

文本文件的二进制预统计Huffman编解码

一、实验目的1熟悉Huffman编解码算法；2理解Huffman编码的最佳性

二、实验内容

1、编程思想霍夫曼Huffman编码是1952年为文本文件而建立，是一种统计编码属于无损压缩编码霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长这样，处理全部信息的总码长一定小于实际信息的符号长度计算机编程实现时，首先统计带编码的文本文件中各个字符出现的概率，然后将概率作为节点的权值构建huffman树编码时从叶子节点出发，如果这个节点在左子树上,则编码0,否则编码1,直到根节点为止，所得到的01序列即为该叶子节点的编码所有叶子节点的编码构成一个码本有两种译码方法1按位读入码字，从已建好的Huffman树的根节点开始，若码字为“0”，则跳到左子树，若为“1”则跳到右子树，直到叶子结点为止，输出叶子接点所表示的符号2由于Huffman编码是唯一码，还有另一种译码方法，每读入一位编码就去码本中去匹配相应的码字，若匹配不成功，则继续读入下一个编码，直到匹配成功为止显然前一种方法比较简便，本程序采用便是该方法

2、程序流程图for i nt i=0;ileafnode;i++CodLen=0;*CodeBook+i*leafnode+1=sw[i].symboI;P二i；while htree[p].part if p-htree[htree[p].part].Ichd//夕建左夜子codetemp[CodLen]=0x0;e\se//P是右孩子codetemp[CodLen]=0x1;CodLen++;p二htree[p].part;*CodeBook+i*Ieafnode+1+1=CodLen;for intj=0;jCodLen;j++*CodeBook+i*Ieafnode+1+1+CodLen-j=*codetemp+j;CodeBuf=new uns i gned char[F i IeLen*Ieafnode-1];for int i i=0;i iFiIeLen;i i++for intjj=0;jjleafnode;jj++i f*DataBuf+i i==*CodeBook+jj*Ieafnode+1for i nt kk=0;kk*CodeBook+jj*leafnode+1+1;kk++*CodeBuf+CodeLen=*CodeBook+j j*Ieafnode+1+2+kk;CodeLen++;vo id HufmDCodeuns i gned char*CDataBuf,i ntCDataLenFILE*lp;int i=0;DCodeBuf=new uns i gned char[1024*1024];while iCDataLen i nt p=totaI node-1;while p=leafnode if*CDataBuf+i=1p=htree[p].rchd;e Isep=htree[p].Ichd;i++；1*DCodeBuf+DCodeLen=sw[p].symboI;DCodeLen++;

3、编程实现本实验采用用C语言程序语言，VC++

6.0编程环境⑴数据结构构造存放符号及其权值的存储结构如下typedef struct{unsigned charsymbol;〃符号的ASCH码值int sweight;〃权值}syml_weit;syml_weit*sw;sw构造huffman树存储结构如下typedef struct{int weit;〃权值int Ichd;〃左孩子地址int rchd;〃右孩子地址int part;//双亲地址}hufmtree;hufmtree*htree;2函数本程序共包含5个函数一个主函数void main,4个子函数void CountWeightunsigned char*DataBuf,int FileLen;void BuildTree;void HufmCodeunsigned char*DataBuf,int FileLen;void HufmDCodeunsigned char*CDataBuf,int CDataLen;其功能分别是CountWeight计算文本文件中各符号的权值；BuildTree构建Huffman树，形成码本；HufmCode对文本文件进行编码；HufmDCode进彳亍译码⑶存储器本程序共包含4个存储器unsigned char*DataBuf;〃存放文本文件数据的内存空间unsigned char*CodeBook;〃存放码本unsigned char*CodeBuf;〃存放编好的码unsigned char*DCodeBuf;〃存放译码后数据详细代码见附件

三、实验结果程序运行后会形成3个文件codebook,txt码本文件；abc_code.txt编码文件；abc dcode.txt译码文件经比较译码后的文件与待编码文件相同，编译码成功实现为了编写简单，编码文件输出时未采用的比特输出的方式，而采用了字节输出方式，即每个字节代表一个码字这样输出文件大小是理论值的8倍因此计算压缩率时应该除以8才是真正的压缩率已编码文件大小/8压缩率=--------------------------------*100%待编码文件大小二42231/8/9433*100%=

55.96178%附件完整程序代码#i ncIudestd io.h#i ncIudestr i ng.h#def ine MaxNo256#define NULL0typedef structuns i gned char symboI;i ntswe i ght;}syml_weit;syml_wei t*sw;//存放符号及其权值typedef structi nt we i t;i ntIchd;i ntrchd;hufmtree*htree;H存放Huffman树i ntpart;}hufmtree;int leafnode,total node;//叶子节点个数和整棵树的所有节点uns i gned char*DataBuf;//存放文本文件数据的内存空间uns i gned char//存放码本*CodeBook;uns ignedchar//存放编好的码*CodeBuf;uns ignedchar*DCodeBuf;i ntCodeBookLen;//码本长度i ntCodeLen;//码长度\nt DCodeLen;vo id CountWe i ghtuns ignedchar*DataBuf,i ntFi leLen;vo id Bu i IdTree;void HufmCodeunsignedchar*DataBuf,int Fi leLen;void HufmDCodeunsignedchar*CDataBuf,int CDataLen;vo id main0{FILE*fp1,*fp2,*fp3,*fp4;//文件读取指针char fi I epath[]=abc.txt;int Fi leLen;//读入的文件长度DataBuf=new unsignedchar[1024*1024];pr intf=====Huffman Codeand Decodeby Li Yi ngIe@NDSC==~\n\n;if fp1=fopenf iIepath,rb—NULL//读入文本文件pr intf abcopen error!;FileLen=fread DataBuf,1,1024*1024,fp1;CountWeight DataBuf,F iI eLen;//计算权值BuiIdTree0;//建树HufmCode DataBuf,Fi IeLen;〃编码HufmDCode CodeBuf,CodeLen;//译码/////输出码本文件和压缩率if fp2=fopen codebook,txt,w==NULL{pr intf abc_codebook openerror!;1fprintf fp2,ASCI IWEIGHT C0DE\nn;for int i=0;ileafnode;i++{fpr intffp2,n0x%02x%

8.4f%%:,*CodeBook+i*Ieafnode+1,

100.0*sw[i].swe ight/htree[totaI node-1].we it;for intj=0;j*CodeBook+i*Ieafnode+1+1;j++fpr intf fp2,,,%du,*CodeBook+i*leafnode+1+2+j;}fpr intf fp2,\n;fprintf fp2,H\n%.5f%%,

100.0*CodeLen/8/FileLen;/////输出编码文件\f fp3=fopen abc_code.txt,nwn==NULLpr intf abc_code openerror!;}.fwr ite CodeBuf,1,CodeLen,fp3;/////输出译码文件\ffp4=fopen abc_dcode.txt,wb—NULLpr intf abc_dcode openerror!;fwr iteDCodeBuf,1,DCodeLen,fp4;fcIose fp1;fcIose fp2;fcIose fp3;fcIose fp4;de Iete[]DataBuf;de Iete[]CodeBook;de Iete[]CodeBuf;de Iete[]DCodeBuf;vo id CountWeightunsignedchar*DataBuf,intFi leLeninti=0,sum=0;intcounter[MaxNo]={0x0};for i=0;i FiIeLen;i++//计算权值counter[DataBuf[i]]++;for i=0;iMaxNo;i++//计算叶子节点个数if counter[i]Ieafnode++;}tota Inode二I eafnode-1+1eafnode;//满树情况下的节点个数sw=new symI_we it[I eafnode];//存放码字和权值htree=new hufmtree[tota Inode];//huff manintj=0;for i=0;i MaxNo;i++if counter[i]sw[j].sweight=counter[i];sw[j].symboI=i;htree[j].we it=counter[i];htree[j].Ichd=0;htree[j].rchd=0;htree[j++],part=0;}}void BuiIdTree{int i=0;int=\ea干node;//非叶子节点的开始int wl,w2//两个最小的权值int p1=-1,p2=-1;for int Ieaf=0;IeafIeafnode-1;Ieaf++〃〃〃〃〃〃〃〃〃〃〃〃/女次缜最小的两个落点〃〃〃/for i=0;itotaInode;i++i fhtree[i].part==0ifp1=7p1=i；w1=htree[i].weit;else ifp2=7i fhtree[i].we it=w1{p2二i;w2=htree[i].we it;e Ise p2=p1;w2=w1;p1二i；w1=htree[i].we it;}break;for i=0;itotaI node;i++if htree[i].part==0i!二p1i!邓2i fhtree[i].we itw2{i fhtree[i].weitw1w2=w1;p2=p1；w1=htree[i].we it;p1=i；}e Ise w2=htree[i].we it;p2二i;}}}/////////////////////////////////////////////////////设置父节点htree[j].we it=w1+w2;htree[j].Ichd=p1;htree[j].rchd=p2;htree[j].part=0;htree[p1].part=j;htree[p2].part=j;p1=-1；p2=-1;j++；}vo id HufmCodeunsignedchar*DataBuf,intFi leLenCodeBookLen=Ieafnode*Ieafnode+1;CodeBook=new unsignedchar[CodeBookLen];〃存放编好的打字unsignedchar*codetemp=new unsignedchar[I eafnode];//端时存放编好的码字int p;intCodLen;。