huffman編碼譯碼實現(xiàn)文件的壓縮與解壓

..數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目名稱：huffman編碼與解碼實現(xiàn)文件的壓縮與解壓專業(yè)年級：組長：小組成員：指導(dǎo)二〇一二年十二月二十六日..目錄目標(biāo)任務(wù)與問題分析…………21.1目標(biāo)任務(wù)…………21.2問題分析…………2算法分析………22.1構(gòu)造huffman樹…………………22.1.1字符的統(tǒng)計………………22.1.2huffman樹節(jié)點的設(shè)計……22.2構(gòu)造huffman編碼………………32.2.1huffman編碼的設(shè)計………32.3壓縮文件與解壓文件的實現(xiàn)……3三、執(zhí)行效果……43.1界面………43.2每個字符的編碼…………43.3操作部分…………………53.4文件效果…………………6源程序………………7參考文獻(xiàn)……………16huffman編碼與解碼實現(xiàn)文件的壓縮與解壓一、目標(biāo)任務(wù)與問題分析1.1目標(biāo)任務(wù)采用huffman編碼思想實現(xiàn)文件的壓縮和解壓功能,可以將任意文件壓縮,壓縮后也可以解壓出來。這樣即節(jié)約了存儲空間,也不會破壞文件的完整性。1.2問題分析本問題首先應(yīng)該是利用哈夫曼思想,對需要壓縮的文件中的個字符進(jìn)行頻率統(tǒng)計,為了能對任意的文件進(jìn)行處理,應(yīng)該所有的文件以二進(jìn)制的方式進(jìn)行處理,即對文件〔不管包含的是字母還是漢字采取一個個的字節(jié)處理,然后根據(jù)統(tǒng)計的頻率結(jié)果構(gòu)造哈夫曼樹,然后對每個字符進(jìn)行哈夫曼編碼,然后逐一對被壓縮的文件的每個字符構(gòu)建的新的哈夫曼編碼存入新的文件中即得到的壓縮文件。解壓過程則利用相應(yīng)的哈夫曼樹及壓縮文件中的二進(jìn)制碼將編碼序列譯碼,對文件進(jìn)行解壓,得到解壓文件。二、算法分析2.1構(gòu)造huffman樹要利用哈夫曼編碼對文本文件進(jìn)行壓縮,首先必須知道期字符相應(yīng)的哈夫曼編碼。為了得到文件中字符的頻率,一般的做法是掃描整個文本進(jìn)行統(tǒng)計,編寫程序統(tǒng)計文件中各個字符出現(xiàn)的頻率。由于一個字符的范圍在[0-255]之間,即共256個狀態(tài),所以可以直接用256個哈夫曼樹節(jié)點即數(shù)組〔后面有節(jié)點的定義空間來存儲整個文件的信息,節(jié)點中包括對應(yīng)字符信息,其中包括頻率。2.1.1字符的統(tǒng)計用結(jié)構(gòu)體huffchar來存放文件字符的信息。其中有文件中不同字符出現(xiàn)的種類Count、字符data。structhuffchar{//存放讀入字符的類；intCount;//字符出現(xiàn)的個數(shù)；chardata;//字符；};函數(shù)實現(xiàn)：boolchar_judge<charc>//判斷字符出現(xiàn)的函數(shù)；voidchar_add<charc>//添加新出現(xiàn)的字符；voidread_file_count<>//文件的讀取2.1.2huffman樹節(jié)點的設(shè)計用結(jié)構(gòu)體huff_tree來存儲結(jié)點信息,其中有成員頻率weight、父親節(jié)點parent、左兒子節(jié)點lchild、右兒子節(jié)點rchild。structhuff_tree{//huffman樹結(jié)點定義；intparent;intlchild;intrchild;intweight;};函數(shù)實現(xiàn)：voidcreathuffman<>//構(gòu)造huffman樹的函數(shù)2.2構(gòu)造huffman編碼2.2.1huffman編碼的設(shè)計用結(jié)構(gòu)體huffcode來存儲每個字符的編碼。其中有編碼數(shù)組bits、起始編碼start、頻數(shù)count、編碼對應(yīng)的字符c。structhuffcode{//結(jié)構(gòu)體stringbits[100];//存放解碼；intstart;//intcount;//頻數(shù)stringc;//存放字符；};函數(shù)實現(xiàn)：voidhuffmancode<>//編碼函數(shù)2.3壓縮文件與解壓文件的實現(xiàn)將壓縮的文件根據(jù)huffman樹進(jìn)行編碼,存入新的文件〔huffman1.txt中,將huffman.txt按照huffman編碼對應(yīng)的字符解壓回來,但是這樣的文件是壓縮不了的,當(dāng)時用了一個30kb的文件壓縮后竟然成了119kb,導(dǎo)致這樣的問題是因為一個字符對應(yīng)幾個二進(jìn)制數(shù)字,然而一個二進(jìn)制文字也是占一個字節(jié),這就導(dǎo)致了壓縮后的文件變大。處理的方法將huffman1.txt文件中的二進(jìn)制編碼7位7位的存成一個ascII值存入新的文件,這樣就實現(xiàn)了真正打壓縮。解壓的時候?qū)⑽募械腶scII值重新弄成二進(jìn)制,不夠7位的前邊補(bǔ)0,例如ascII值為99的二進(jìn)制位100011這是6位的ascII碼所以再前邊補(bǔ)一個0那么99的二進(jìn)制就變成0100011。接下來就利用huffman編碼將這個文件重新譯碼過來。函數(shù)實現(xiàn)：voidcode_huffman_file<>//編碼后的二進(jìn)制碼存入文件voidcode_file_out<>//將編碼過的文件恢復(fù)；voidevaluating<>//比較文件壓縮的比例voidchange<>//將二進(jìn)制編碼變成ascII碼voidyichu<>//將ascII翻譯成二進(jìn)制碼恢復(fù)文件三、執(zhí)行效果本算法有一個初始文件為huffman.txt。為一篇小說,大小為32KB3.1界面3.2每個字符的編碼3.3操作部分3.4文件效果huffman為初始文件大小為30KB,huffman1為二進(jìn)制編碼文件大小為130KB,huffman2文件為解壓后的文件大小為30KB,huffman3.為真正壓縮后的文件大小為19KB,huffman為huffman3文件解壓后的文件大小為30KB,與huffman文件內(nèi)容相同。標(biāo)記的文件就是壓縮后的huffman3文件。四、源程序：#include<iostream>#include<fstream>#include<string>#include<iomanip>#include<cstdio>#include<algorithm>#include<queue>usingnamespacestd;stringremfile[3100000];//存放原文件字符的數(shù)組；charstrstr[1500000];intremcount=0;//記錄元素個數(shù)；floatbitecount=0;//記錄二進(jìn)制碼的個數(shù)；/****************************************************************/structhuffchar{//存放讀入字符的類；intCount;//字符出現(xiàn)的個數(shù)；chardata;//字符；};intCount=1;//記錄huff數(shù)組中字符實際出現(xiàn)的個數(shù)；huffcharhuff[1000];//類的對象；/****************************************************************//*文件讀入部分和統(tǒng)計字符出現(xiàn)的頻率*/boolchar_judge<charc>//判斷字符出現(xiàn)的函數(shù)；{for<inti=1;i<=Count;i++>if<huff[i].data==c>{huff[i].Count++;returntrue;}//如果出現(xiàn)過,出現(xiàn)的頻數(shù)加1；returnfalse;}voidchar_add<charc>//添加新出現(xiàn)的字符；{huff[Count].data=c;huff[Count++].Count++;//個數(shù)增加,}//文件的讀取voidread_file_count<>{charc;ifstreaminfile;infile.open<"huffman.txt">;//打開huffman.txt文件；if<!infile>//檢查文件是否打開。{cerr<<"不能打開huffman.txt文件";//輸出文件未打開的標(biāo)志。exit<0>;}cout<<"讀入的文件中的內(nèi)容為："<<endl;while<<c=infile.get<>>!=EOF>{remfile[++remcount]=c;if<!char_judge<c>>char_add<c>;}cout<<endl;}/******************文件讀入和統(tǒng)計字符出現(xiàn)頻率部分結(jié)束**************//******************************************************************//******************構(gòu)造huffman樹程序部分***************************/structhuff_tree{//huffman樹結(jié)點定義；intparent;intlchild;intrchild;intweight;};intsum;//huffman樹中結(jié)點的個數(shù)；huff_treehuffman[1000];voidcreathuffman<>//構(gòu)造huffman樹的函數(shù){intmin1,min2;//指示權(quán)值最??；intloc1,loc2;//指向權(quán)值最小的兩個數(shù)的位置；for<inti=1;i<=sum;i++>{//對huffman樹的結(jié)點進(jìn)行初始化；huffman[i].parent=0;huffman[i].lchild=0;huffman[i].rchild=0;huffman[i].weight=0;}for<intii=1;ii<Count;ii++>//將權(quán)值賦給huffman[].weight;huffman[ii].weight=huff[ii].Count;sum=2*Count-3;for<intj=Count;j<=sum;j++>{loc1=loc2=0;//權(quán)值最小的min1=min2=2000000;for<intk=1;k<=j-1;k++>//求權(quán)值最小的兩個地址；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;}////////////將求出的兩個權(quán)值最小的結(jié)點合并為新的結(jié)點,并將新的結(jié)點存入數(shù)組中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;}}/*******************************構(gòu)造huffman樹的程序部分結(jié)束********************************//*************************************huffman編碼開始**************************************/structhuffcode{//結(jié)構(gòu)體stringbits[100];//存放解碼；intstart;//intcount;//頻數(shù)stringc;//存放字符；};huffcodehcode[100];voidhuffmancode<>//編碼函數(shù){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;//輸出文件未打開的標(biāo)志。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<>;}/****************************編碼并將編碼存入文件部分結(jié)束*************************/strings1;/////////////////////////////////////////////////////////////////////////////////voidcode_file_out<>//將編碼過的文件恢復(fù)；{ifstreamfp1;//編碼文件；ofstreamfp2;//解壓縮文件；fp1.open<str.c_str<>>;if<!fp1>//檢查文件是否打開。{cerr<<"不能打開"<<str<<"文件"<<endl;//輸出文件未打開的標(biāo)志。exit<0>;}charinchar;cout<<"請輸入文件名"<<endl<<"例如：huffman2.txt"<<endl;cout<<"該文件用來存放解壓后的文件"<<endl;cin>>s1;fp2.open<s1.c_str<>>;if<!fp2>//檢查文件是否打開。{cerr<<"不能打開"<<s1<<"文件"<<endl;//輸出文件未打開的標(biāo)志。exit<0>;}for<intptr=sum;!fp1.eof<>;>//將編碼轉(zhuǎn)為字符輸入的到文件中；{fp1>>inchar;if<inchar=='1'>ptr=huffman[ptr].rchild;//查找相應(yīng)編碼對應(yīng)huffman樹中的位置,elseptr=huffman[ptr].lchild;if<huffman[ptr].rchild==0&&huffman[ptr].lchild==0>//判斷是否為葉子結(jié)點；{fp2<<huff[ptr].data;ptr=sum;}//是葉子結(jié)點,將該結(jié)點的對應(yīng)字符輸入到文件中；}cout<<endl<<"請檢查原文件"<<"huffman.txt"<<"與解壓縮文件"<<s1<<endl<<endl<<endl;//cout<<"*********************************請檢查*****************************"<<endl;}/*************************解壓縮文件部分結(jié)束**************************************/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;//輸出文件未打開的標(biāo)志。exit<0>;}cout<<"輸入文件名用來存放壓縮后的文件"<<endl<<"例如huffman3.txt"<<endl;cin>>s2;charinchar,ch;fp2.open<s2.c_str<>>;if<!fp2>//檢查文件是否打開。{cerr<<"不能打開"<<s2<<"文件"<<endl;//輸出文件未打開的標(biāo)志。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;//輸出文件未打開的標(biāo)志。exit<0>;}cout<<"輸入文件名用來存放解壓后的文件"<<endl<<"例如huffman4.txt"<<endl;cin>>s3;fp2.open<s3.c_str<>>;if<!fp2>//檢查文件是否打開。{cout<<"不能打開"<<s3<<"文件"<<endl;//輸出文件未打開的標(biāo)志。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;//查找相應(yīng)編碼對應(yīng)huffman樹中的位置,elseptr=huffman[ptr].lchild;if<huffman[ptr].lchild==0&&huffman[ptr].rchild==0>//判斷是否為葉子結(jié)點；{fp2<<huff[ptr].data;ptr=sum;}//是葉子結(jié)點,將該結(jié)點的對應(yīng)字符輸入到文件中；}fp1.close<>;fp2.close<>;//printf<"****">;}intmain<>{cout<<"***************