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

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)題目名稱：huffman編碼與解碼實(shí)現(xiàn)文件的壓縮與解壓專業(yè)年級(jí)： 組 長(zhǎng)： 小組成員： 指導(dǎo)教師： 二一二 年 十二 月 二十六 日 目錄1、 目標(biāo)任務(wù)與問(wèn)題分析2 1.1目標(biāo)任務(wù)2 1.2問(wèn)題分析22、 算法分析2 2.1構(gòu)造huffman樹(shù)2 2.1.1 字符的統(tǒng)計(jì) 2 2.1.2 huffman樹(shù)節(jié)點(diǎn)的設(shè)計(jì)2 2.2構(gòu)造huffman編碼 3 2.2.1 huffman編碼的設(shè)計(jì) 3 2.3 壓縮文件與解壓文件的實(shí)現(xiàn)3 三、執(zhí)行效果 4 3.1界面 4 3.2每個(gè)字符的編碼 43.3操作部分 53.4文件效果 64、 源程序 7 5、 參考文獻(xiàn)16huffman編碼與

2、解碼實(shí)現(xiàn)文件的壓縮與解壓一、目標(biāo)任務(wù)與問(wèn)題分析 1.1目標(biāo)任務(wù) 采用huffman編碼思想實(shí)現(xiàn)文件的壓縮和解壓功能，可以將任意文件壓縮，壓縮后也可以解壓出來(lái)。這樣即節(jié)約了存儲(chǔ)空間，也不會(huì)破壞文件的完整性。 1.2問(wèn)題分析 本問(wèn)題首先應(yīng)該是利用哈夫曼思想，對(duì)需要壓縮的文件中的個(gè)字符進(jìn)行頻率統(tǒng)計(jì)，為了能對(duì)任意的文件進(jìn)行處理，應(yīng)該所有的文件以二進(jìn)制的方式進(jìn)行處理，即對(duì)文件（不管包含的是字母還是漢字）采取一個(gè)個(gè)的字節(jié)處理，然后根據(jù)統(tǒng)計(jì)的頻率結(jié)果構(gòu)造哈夫曼樹(shù)，然后對(duì)每個(gè)字符進(jìn)行哈夫曼編碼，然后逐一對(duì)被壓縮的文件的每個(gè)字符構(gòu)建的新的哈夫曼編碼存入新的文件中即得到的壓縮文件。解壓過(guò)程則利用相應(yīng)的哈夫曼樹(shù)及壓

3、縮文件中的二進(jìn)制碼將編碼序列譯碼，對(duì)文件進(jìn)行解壓，得到解壓文件。二、算法分析 2.1構(gòu)造huffman樹(shù) 要利用哈夫曼編碼對(duì)文本文件進(jìn)行壓縮，首先必須知道期字符相應(yīng)的哈夫曼編碼。為了得到文件中字符的頻率，一般的做法是掃描整個(gè)文本進(jìn)行統(tǒng)計(jì)，編寫程序統(tǒng)計(jì)文件中各個(gè)字符出現(xiàn)的頻率。由于一個(gè)字符的范圍在0-255之間，即共256個(gè)狀態(tài)，所以可以直接用256個(gè)哈夫曼樹(shù)節(jié)點(diǎn)即數(shù)組（后面有節(jié)點(diǎn)的定義）空間來(lái)存儲(chǔ)整個(gè)文件的信息，節(jié)點(diǎn)中包括對(duì)應(yīng)字符信息，其中包括頻率。2.1.1 字符的統(tǒng)計(jì)用結(jié)構(gòu)體huffchar來(lái)存放文件字符的信息。其中有文件中不同字符出現(xiàn)的種類Count、字符data。struct huff

4、char/存放讀入字符的類； int Count;/字符出現(xiàn)的個(gè)數(shù)； char data;/字符；;函數(shù)實(shí)現(xiàn)： bool char_judge(char c)/判斷字符出現(xiàn)的函數(shù)； void char_add(char c)/添加新出現(xiàn)的字符； void read_file_count() /文件的讀取2.1.2 huffman樹(shù)節(jié)點(diǎn)的設(shè)計(jì)用結(jié)構(gòu)體huff_tree來(lái)存儲(chǔ)結(jié)點(diǎn)信息，其中有成員頻率weight、父親節(jié)點(diǎn)parent、左兒子節(jié)點(diǎn)lchild、右兒子節(jié)點(diǎn)rchild。struct huff_tree/huffman樹(shù)結(jié)點(diǎn)定義； int parent; int lchild; int

5、rchild; int weight;函數(shù)實(shí)現(xiàn)： void creathuffman() /構(gòu)造huffman樹(shù)的函數(shù) 2.2構(gòu)造huffman編碼 2.2.1 huffman編碼的設(shè)計(jì) 用結(jié)構(gòu)體huffcode來(lái)存儲(chǔ)每個(gè)字符的編碼。其中有編碼數(shù)組bits、起始編碼start、頻數(shù)count、編碼對(duì)應(yīng)的字符 c。struct huffcode/結(jié)構(gòu)體 string bits100;/存放解碼； int start;/ int count;/頻數(shù) string c;/存放字符；;函數(shù)實(shí)現(xiàn)： void huffmancode()/編碼函數(shù) 2.3 壓縮文件與解壓文件的實(shí)現(xiàn) 將壓縮的文件根據(jù)huff

6、man樹(shù)進(jìn)行編碼，存入新的文件（huffman1.txt）中，將huffman.txt按照huffman編碼對(duì)應(yīng)的字符解壓回來(lái)，但是這樣的文件是壓縮不了的，當(dāng)時(shí)用了一個(gè)30kb的文件壓縮后竟然成了119kb，導(dǎo)致這樣的問(wèn)題是因?yàn)橐粋€(gè)字符對(duì)應(yīng)幾個(gè)二進(jìn)制數(shù)字，然而一個(gè)二進(jìn)制文字也是占一個(gè)字節(jié)，這就導(dǎo)致了壓縮后的文件變大。處理的方法將huffman1.txt文件中的二進(jìn)制編碼7位7位的存成一個(gè)ascII值存入新的文件，這樣就實(shí)現(xiàn)了真正打壓縮。解壓的時(shí)候?qū)⑽募械腶scII值重新弄成二進(jìn)制，不夠7位的前邊補(bǔ)0，例如ascII值為99的二進(jìn)制位100011這是6位的ascII碼所以再前邊補(bǔ)一個(gè)0那么99

7、的二進(jìn)制就變成0100011。接下來(lái)就利用huffman編碼將這個(gè)文件重新譯碼過(guò)來(lái)。函數(shù)實(shí)現(xiàn)： void code_huffman_file()/編碼后的二進(jìn)制碼存入文件 void code_file_out()/將編碼過(guò)的文件恢復(fù)； void evaluating()/比較文件壓縮的比例 void change()/將二進(jìn)制編碼變成ascII碼 void yichu()/將ascII翻譯成二進(jìn)制碼恢復(fù)文件三、執(zhí)行效果 本算法有一個(gè)初始文件為huffman.txt。為一篇小說(shuō)，大小為32KB 3.1界面 3.2每個(gè)字符的編碼3.3操作部分3.4文件效果huffman為初始文件大小為30KB，h

8、uffman1為二進(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>#incl

9、ude <queue>using namespace std;string remfile3100000;/存放原文件字符的數(shù)組；char strstr1500000;int remcount=0;/記錄元素個(gè)數(shù)；float bitecount=0;/記錄二進(jìn)制碼的個(gè)數(shù)；/*/struct huffchar/存放讀入字符的類； int Count;/字符出現(xiàn)的個(gè)數(shù)； char data;/字符；;int Count=1;/記錄huff數(shù)組中字符實(shí)際出現(xiàn)的個(gè)數(shù)；huffchar huff1000;/類的對(duì)象；/*/*文件讀入部分和統(tǒng)計(jì)字符出現(xiàn)的頻率*/bool char_judge(

10、char c)/判斷字符出現(xiàn)的函數(shù)； for(int i=1;i<=Count;i+) if(huffi.data=c)huffi.Count+;return true;/如果出現(xiàn)過(guò)，出現(xiàn)的頻數(shù)加1； return false;void char_add(char c)/添加新出現(xiàn)的字符； huffCount.data=c; huffCount+.Count+;/個(gè)數(shù)增加，/文件的讀取void read_file_count() char c; ifstream infile; infile.open("huffman.txt");/打開(kāi)huffman.txt文件；

11、if(!infile)/檢查文件是否打開(kāi)。 cerr<<"不能打開(kāi) huffman.txt文件"/輸出文件未打開(kāi)的標(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)計(jì)字符出現(xiàn)頻率部分結(jié)束*/*/*構(gòu)造huffman樹(shù)程序部分*/struct huff_tree/huffman樹(shù)結(jié)點(diǎn)定義；

12、 int parent; int lchild; int rchild; int weight; int sum;/huffman樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)； huff_tree huffman1000;void creathuffman()/構(gòu)造huffman樹(shù)的函數(shù) int min1,min2;/指示權(quán)值最??； int loc1,loc2;/指向權(quán)值最小的兩個(gè)數(shù)的位置； for(int i=1;i<=sum;i+) /對(duì)huffman樹(shù)的結(jié)點(diǎn)進(jìn)行初始化； huffmani.parent=0; huffmani.lchild=0; huffmani.rchild=0; huffmani.weigh

13、t=0; for(int ii=1;ii<Count;ii+)/將權(quán)值賦給huffman.weight; huffmanii.weight=huffii.Count; sum=2*Count-3;for(int j=Count;j<=sum;j+) loc1=loc2=0;/權(quán)值最小的 min1=min2=2000000; for(int k=1;k<=j-1;k+)/求權(quán)值最小的兩個(gè)地址； if(huffmank.parent=0) if(huffmank.weight<=min1) min2=min1;min1=huffmank.weight; loc2=loc1;

14、loc1=k; else if(huffmank.weight<=min2) min2=huffmank.weight;loc2=k;/將求出的兩個(gè)權(quán)值最小的結(jié)點(diǎn)合并為新的結(jié)點(diǎn)，并將新的結(jié)點(diǎn)存入數(shù)組中 huffmanloc1.parent=j; huffmanloc2.parent=j; huffmanj.lchild=loc1; huffmanj.rchild=loc2; huffmanj.weight=huffmanloc1.weight+huffmanloc2.weight; /*構(gòu)造huffman樹(shù)的程序部分結(jié)束*/*huffman編碼開(kāi)始*/struct huffcode/結(jié)構(gòu)

15、體 string bits100;/存放解碼； int start;/ int count;/頻數(shù) string c;/存放字符；;huffcode hcode100;void huffmancode()/編碼函數(shù) int rem,p;int count1=0; for(int y=1;y<=Count;y+) /編碼部分； rem=y; hcodey.start=sum; hcodey.c=huffy.data; p=huffmany.parent; while(p!=0) if(huffmanp.lchild=rem)hcodey.bits+count1='0' el

16、se hcodey.bits+count1='1' rem=p; p=huffmanp.parent; hcodey.count=count1; count1=0; cout<<"字符以及其編碼："<<endl; for(int t=1;t<=Count;t+)/輸出所編的碼； cout<<"字符"<<hcodet.c<<"；編碼： " int r=hcodet.count; while(r) cout<<hcodet.bitsr-; cou

17、t<<endl; /*/ string str;void code_huffman_file() ofstream fp; cout<<"請(qǐng)輸入文件名"<<endl<<"例如：huffman1.txt"<<endl; cout<<"該文件用來(lái)存放編碼后的文件即壓縮文件"<<endl; cin>>str; fp.open(str.c_str(); if(!fp)/檢查文件是否打開(kāi)。 cerr<<"不能打開(kāi) "&

18、lt;<str<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); for(int j=1;j<=remcount;j+) for(int i=1;i<=Count;i+) if(remfilej=hcodei.c) for(int k=hcodei.count;k>0;k-) fp<<hcodei.bitsk;bitecount+; break; fp.close();/*編碼并將編碼存入文件部分結(jié)束*/string s1;/void code_file_out()/將編碼過(guò)的文件恢復(fù)； ifst

19、ream fp1;/編碼文件； ofstream fp2;/解壓縮文件； fp1.open(str.c_str(); if(!fp1)/檢查文件是否打開(kāi)。 cerr<<"不能打開(kāi) "<<str<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); char inchar; cout<<"請(qǐng)輸入文件名"<<endl<<"例如：huffman2.txt"<<endl; cout<<"該文件

20、用來(lái)存放解壓后的文件"<<endl; cin>>s1; fp2.open(s1.c_str(); if(!fp2)/檢查文件是否打開(kāi)。 cerr<<"不能打開(kāi)"<<s1<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); for(int ptr=sum;!fp1.eof();)/將編碼轉(zhuǎn)為字符輸入的到文件中； fp1>>inchar; if(inchar='1')ptr=huffmanptr.rchild;/查找相應(yīng)編碼對(duì)應(yīng)huf

21、fman樹(shù)中的位置， else ptr=huffmanptr.lchild; if(huffmanptr.rchild=0&&huffmanptr.lchild=0)/判斷是否為葉子結(jié)點(diǎn)； fp2<<huffptr.data;ptr=sum;/是葉子結(jié)點(diǎn)，將該結(jié)點(diǎn)的對(duì)應(yīng)字符輸入到文件中； cout<<endl<<" 請(qǐng)檢查原文件"<<"huffman.txt"<<"與解壓縮文件"<<s1<<endl<<endl<<

22、;endl; /cout<<"*請(qǐng)檢查*"<<endl;/*解壓縮文件部分結(jié)束*/void evaluating() float y1; y1=bitecount/7/remcount*100; cout<<"壓縮比例是："<<y1<<"%"<<endl;string s2;/壓縮文件2名int tot=0;void change() ifstream fp1; ofstream fp2; fp1.open(str.c_str(); if(!fp1)/檢查文件是否

23、打開(kāi)。 cerr<<"不能打開(kāi) "<<s1<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); cout<<"輸入文件名用來(lái)存放壓縮后的文件"<<endl<<"例如huffman3.txt"<<endl; cin>>s2; char inchar,ch; fp2.open(s2.c_str(); if(!fp2)/檢查文件是否打開(kāi)。 cerr<<"不能打開(kāi) "&

24、lt;<s2<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); int t=0,f=0,s; /char a8; while(!fp1.eof() fp1>>inchar; s=inchar-'0' t*=2; t+=s; f+; if(f=7) ch=t; t=0; fp2<<ch; strstrtot+=ch; f=0; strstrtot='0' fp1.close(); fp2.close();string s3;/文件解壓2名queue<int >s

25、;string s4;void yichu() ifstream fp1; ofstream fp2; fp1.open(s2.c_str(); if(!fp1)/檢查文件是否打開(kāi)。 cerr<<"不能打開(kāi) "<<s2<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); cout<<"輸入文件名用來(lái)存放解壓后的文件"<<endl<<"例如huffman4.txt"<<endl; cin>>s3

26、; fp2.open(s3.c_str(); if(!fp2)/檢查文件是否打開(kāi)。 cout<<"不能打開(kāi) "<<s3<<"文件"<<endl;/輸出文件未打開(kāi)的標(biāo)志。 exit(0); int inchar; int i=0; while(!s.empty()s.pop(); for(int ptr=sum;i<tot;) if(s.size()<3) char ch; int num,a8; fp1>>ch; ch=strstri+; num=ch; for(int i=6;i&

27、gt;=0;i-) ai=num%2;num/=2; for(int i=0;i<7;i+) /ch=ai+'0' s.push(ai); inchar=s.front(); s.pop(); if(inchar=1)ptr=huffmanptr.rchild;/查找相應(yīng)編碼對(duì)應(yīng)huffman樹(shù)中的位置， else ptr=huffmanptr.lchild; if(huffmanptr.lchild=0&&huffmanptr.rchild=0)/判斷是否為葉子結(jié)點(diǎn)； fp2<<huffptr.data;ptr=sum;/是葉子結(jié)點(diǎn)，將該結(jié)點(diǎn)的對(duì)應(yīng)字符輸入到文件中； fp1.close(); fp2.close();/printf("*");int main() cout<<" *"<<endl; cout<<&qu