huffman编码译码实现文件的压缩与解压

..数据结构课程设计题目名称：huffman编码与解码实现文件的压缩与解压专业年级：组长：小组成员：指导二〇一二年十二月二十六日..目录目标任务与问题分析…………21.1目标任务…………21.2问题分析…………2算法分析………22.1构造huffman树…………………22.1.1字符的统计………………22.1.2huffman树节点的设计……22.2构造huffman编码………………32.2.1huffman编码的设计………32.3压缩文件与解压文件的实现……3三、执行效果……43.1界面………43.2每个字符的编码…………43.3操作部分…………………53.4文件效果…………………6源程序………………7参考文献……………16huffman编码与解码实现文件的压缩与解压一、目标任务与问题分析1.1目标任务采用huffman编码思想实现文件的压缩和解压功能,可以将任意文件压缩,压缩后也可以解压出来。这样即节约了存储空间,也不会破坏文件的完整性。1.2问题分析本问题首先应该是利用哈夫曼思想,对需要压缩的文件中的个字符进行频率统计,为了能对任意的文件进行处理,应该所有的文件以二进制的方式进行处理,即对文件〔不管包含的是字母还是汉字采取一个个的字节处理,然后根据统计的频率结果构造哈夫曼树,然后对每个字符进行哈夫曼编码,然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码,对文件进行解压,得到解压文件。二、算法分析2.1构造huffman树要利用哈夫曼编码对文本文件进行压缩,首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率,一般的做法是扫描整个文本进行统计,编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间,即共256个状态,所以可以直接用256个哈夫曼树节点即数组〔后面有节点的定义空间来存储整个文件的信息,节点中包括对应字符信息,其中包括频率。2.1.1字符的统计用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。structhuffchar{//存放读入字符的类；intCount;//字符出现的个数；chardata;//字符；};函数实现：boolchar_judge<charc>//判断字符出现的函数；voidchar_add<charc>//添加新出现的字符；voidread_file_count<>//文件的读取2.1.2huffman树节点的设计用结构体huff_tree来存储结点信息,其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。structhuff_tree{//huffman树结点定义；intparent;intlchild;intrchild;intweight;};函数实现：voidcreathuffman<>//构造huffman树的函数2.2构造huffman编码2.2.1huffman编码的设计用结构体huffcode来存储每个字符的编码。其中有编码数组bits、起始编码start、频数count、编码对应的字符c。structhuffcode{//结构体stringbits[100];//存放解码；intstart;//intcount;//频数stringc;//存放字符；};函数实现：voidhuffmancode<>//编码函数2.3压缩文件与解压文件的实现将压缩的文件根据huffman树进行编码,存入新的文件〔huffman1.txt中,将huffman.txt按照huffman编码对应的字符解压回来,但是这样的文件是压缩不了的,当时用了一个30kb的文件压缩后竟然成了119kb,导致这样的问题是因为一个字符对应几个二进制数字,然而一个二进制文字也是占一个字节,这就导致了压缩后的文件变大。处理的方法将huffman1.txt文件中的二进制编码7位7位的存成一个ascII值存入新的文件,这样就实现了真正打压缩。解压的时候将文件中的ascII值重新弄成二进制,不够7位的前边补0,例如ascII值为99的二进制位100011这是6位的ascII码所以再前边补一个0那么99的二进制就变成0100011。接下来就利用huffman编码将这个文件重新译码过来。函数实现：voidcode_huffman_file<>//编码后的二进制码存入文件voidcode_file_out<>//将编码过的文件恢复；voidevaluating<>//比较文件压缩的比例voidchange<>//将二进制编码变成ascII码voidyichu<>//将ascII翻译成二进制码恢复文件三、执行效果本算法有一个初始文件为huffman.txt。为一篇小说,大小为32KB3.1界面3.2每个字符的编码3.3操作部分3.4文件效果huffman为初始文件大小为30KB,huffman1为二进制编码文件大小为130KB,huffman2文件为解压后的文件大小为30KB,huffman3.为真正压缩后的文件大小为19KB,huffman为huffman3文件解压后的文件大小为30KB,与huffman文件内容相同。标记的文件就是压缩后的huffman3文件。四、源程序：#include<iostream>#include<fstream>#include<string>#include<iomanip>#include<cstdio>#include<algorithm>#include<queue>usingnamespacestd;stringremfile[3100000];//存放原文件字符的数组；charstrstr[1500000];intremcount=0;//记录元素个数；floatbitecount=0;//记录二进制码的个数；/****************************************************************/structhuffchar{//存放读入字符的类；intCount;//字符出现的个数；chardata;//字符；};intCount=1;//记录huff数组中字符实际出现的个数；huffcharhuff[1000];//类的对象；/****************************************************************//*文件读入部分和统计字符出现的频率*/boolchar_judge<charc>//判断字符出现的函数；{for<inti=1;i<=Count;i++>if<huff[i].data==c>{huff[i].Count++;returntrue;}//如果出现过,出现的频数加1；returnfalse;}voidchar_add<charc>//添加新出现的字符；{huff[Count].data=c;huff[Count++].Count++;//个数增加,}//文件的读取voidread_file_count<>{charc;ifstreaminfile;infile.open<"huffman.txt">;//打开huffman.txt文件；if<!infile>//检查文件是否打开。{cerr<<"不能打开huffman.txt文件";//输出文件未打开的标志。exit<0>;}cout<<"读入的文件中的内容为："<<endl;while<<c=infile.get<>>!=EOF>{remfile[++remcount]=c;if<!char_judge<c>>char_add<c>;}cout<<endl;}/******************文件读入和统计字符出现频率部分结束**************//******************************************************************//******************构造huffman树程序部分***************************/structhuff_tree{//huffman树结点定义；intparent;intlchild;intrchild;intweight;};intsum;//huffman树中结点的个数；huff_treehuffman[1000];voidcreathuffman<>//构造huffman树的函数{intmin1,min2;//指示权值最小；intloc1,loc2;//指向权值最小的两个数的位置；for<inti=1;i<=sum;i++>{//对huffman树的结点进行初始化；huffman[i].parent=0;huffman[i].lchild=0;huffman[i].rchild=0;huffman[i].weight=0;}for<intii=1;ii<Count;ii++>//将权值赋给huffman[].weight;huffman[ii].weight=huff[ii].Count;sum=2*Count-3;for<intj=Count;j<=sum;j++>{loc1=loc2=0;//权值最小的min1=min2=2000000;for<intk=1;k<=j-1;k++>//求权值最小的两个地址；if<huffman[k].parent==0>if<huffman[k].weight<=min1>{min2=min1;min1=huffman[k].weight;loc2=loc1;loc1=k;}elseif<huffman[k].weight<=min2>{min2=huffman[k].weight;loc2=k;}////////////将求出的两个权值最小的结点合并为新的结点,并将新的结点存入数组中huffman[loc1].parent=j;huffman[loc2].parent=j;huffman[j].lchild=loc1;huffman[j].rchild=loc2;huffman[j].weight=huffman[loc1].weight+huffman[loc2].weight;}}/*******************************构造huffman树的程序部分结束********************************//*************************************huffman编码开始**************************************/structhuffcode{//结构体stringbits[100];//存放解码；intstart;//intcount;//频数stringc;//存放字符；};huffcodehcode[100];voidhuffmancode<>//编码函数{intrem,p;intcount1=0;for<inty=1;y<=Count;y++>{//编码部分；rem=y;hcode[y].start=sum;hcode[y].c=huff[y].data;p=huffman[y].parent;while<p!=0>{if<huffman[p].lchild==rem>hcode[y].bits[++count1]='0';elsehcode[y].bits[++count1]='1';rem=p;p=huffman[p].parent;}hcode[y].count=count1;count1=0;}cout<<"字符以及其编码："<<endl;for<intt=1;t<=Count;t++>//输出所编的码；{cout<<"字符"<<hcode[t].c<<"；编码：";intr=hcode[t].count;while<r>cout<<hcode[t].bits[r--];cout<<endl;}}/************************************************************************************/stringstr;voidcode_huffman_file<>{ofstreamfp;cout<<"请输入文件名"<<endl<<"例如：huffman1.txt"<<endl;cout<<"该文件用来存放编码后的文件即压缩文件"<<endl;cin>>str;fp.open<str.c_str<>>;if<!fp>//检查文件是否打开。{cerr<<"不能打开"<<str<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}for<intj=1;j<=remcount;j++>{for<inti=1;i<=Count;i++>if<remfile[j]==hcode[i].c>{for<intk=hcode[i].count;k>0;k-->{fp<<hcode[i].bits[k];bitecount++;}break;}}fp.close<>;}/****************************编码并将编码存入文件部分结束*************************/strings1;/////////////////////////////////////////////////////////////////////////////////voidcode_file_out<>//将编码过的文件恢复；{ifstreamfp1;//编码文件；ofstreamfp2;//解压缩文件；fp1.open<str.c_str<>>;if<!fp1>//检查文件是否打开。{cerr<<"不能打开"<<str<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}charinchar;cout<<"请输入文件名"<<endl<<"例如：huffman2.txt"<<endl;cout<<"该文件用来存放解压后的文件"<<endl;cin>>s1;fp2.open<s1.c_str<>>;if<!fp2>//检查文件是否打开。{cerr<<"不能打开"<<s1<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}for<intptr=sum;!fp1.eof<>;>//将编码转为字符输入的到文件中；{fp1>>inchar;if<inchar=='1'>ptr=huffman[ptr].rchild;//查找相应编码对应huffman树中的位置,elseptr=huffman[ptr].lchild;if<huffman[ptr].rchild==0&&huffman[ptr].lchild==0>//判断是否为叶子结点；{fp2<<huff[ptr].data;ptr=sum;}//是叶子结点,将该结点的对应字符输入到文件中；}cout<<endl<<"请检查原文件"<<"huffman.txt"<<"与解压缩文件"<<s1<<endl<<endl<<endl;//cout<<"*********************************请检查*****************************"<<endl;}/*************************解压缩文件部分结束**************************************/voidevaluating<>{floaty1;y1=bitecount/7/remcount*100;cout<<"压缩比例是："<<y1<<"%"<<endl;}strings2;//压缩文件2名inttot=0;voidchange<>{ifstreamfp1;ofstreamfp2;fp1.open<str.c_str<>>;if<!fp1>//检查文件是否打开。{cerr<<"不能打开"<<s1<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}cout<<"输入文件名用来存放压缩后的文件"<<endl<<"例如huffman3.txt"<<endl;cin>>s2;charinchar,ch;fp2.open<s2.c_str<>>;if<!fp2>//检查文件是否打开。{cerr<<"不能打开"<<s2<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}intt=0,f=0,s;//chara[8];while<!fp1.eof<>>{fp1>>inchar;s=inchar-'0';t*=2;t+=s;f++;if<f==7>{ch=t;t=0;fp2<<ch;strstr[tot++]=ch;f=0;}}strstr[tot]='\0';fp1.close<>;fp2.close<>;}strings3;//文件解压2名queue<int>s;strings4;voidyichu<>{ifstreamfp1;ofstreamfp2;fp1.open<s2.c_str<>>;if<!fp1>//检查文件是否打开。{cerr<<"不能打开"<<s2<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}cout<<"输入文件名用来存放解压后的文件"<<endl<<"例如huffman4.txt"<<endl;cin>>s3;fp2.open<s3.c_str<>>;if<!fp2>//检查文件是否打开。{cout<<"不能打开"<<s3<<"文件"<<endl;//输出文件未打开的标志。exit<0>;}intinchar;inti=0;while<!s.empty<>>s.pop<>;for<intptr=sum;i<tot;>{if<s.size<><3>{charch;intnum,a[8];fp1>>ch;ch=strstr[i++];num=ch;for<inti=6;i>=0;i-->{a[i]=num%2;num/=2;}for<inti=0;i<7;i++>{//ch=a[i]+'0';s.push<a[i]>;}}inchar=s.front<>;s.pop<>;if<inchar==1>ptr=huffman[ptr].rchild;//查找相应编码对应huffman树中的位置,elseptr=huffman[ptr].lchild;if<huffman[ptr].lchild==0&&huffman[ptr].rchild==0>//判断是否为叶子结点；{fp2<<huff[ptr].data;ptr=sum;}//是叶子结点,将该结点的对应字符输入到文件中；}fp1.close<>;fp2.close<>;//printf<"****">;}intmain<>{cout<<"***************