huffman編碼譯碼實現文件壓縮與解壓

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

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

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

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

5、rchild; int weight;函數實現： void creathuffman() /構造huffman樹的函數 2.2構造huffman編碼 2.2.1 huffman編碼的設計 用結構體huffcode來存儲每個字符的編碼。其中有編碼數組bits、起始編碼start、頻數count、編碼對應的字符 c。struct huffcode/結構體 string bits100;/存放解碼； int start;/ int count;/頻數 string c;/存放字符；;函數實現： void huffmancode()/編碼函數 2.3 壓縮文件與解壓文件的實現 將壓縮的文件根據huff

6、man樹進行編碼，存入新的文件（huffman1.txt）中，將huffman.txt按照huffman編碼對應的字符解壓回來，但是這樣的文件是壓縮不了的，當時用了一個30kb的文件壓縮后竟然成了119kb，導致這樣的問題是因為一個字符對應幾個二進制數字，然而一個二進制文字也是占一個字節(jié)，這就導致了壓縮后的文件變大。處理的方法將huffman1.txt文件中的二進制編碼7位7位的存成一個ascII值存入新的文件，這樣就實現了真正打壓縮。解壓的時候將文件中的ascII值重新弄成二進制，不夠7位的前邊補0，例如ascII值為99的二進制位100011這是6位的ascII碼所以再前邊補一個0那么99

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

8、uffman1為二進制編碼文件大小為130KB，huffman2文件為解壓后的文件大小為30KB，huffman3.為真正壓縮后的文件大小為19KB，huffman為huffman3文件解壓后的文件大小為30KB，與huffman文件內容相同。標記的文件就是壓縮后的huffman3文件。四、源程序：#include #include #include #include #include #include #include using namespace std;string remfile3100000;/存放原文件字符的數組；char strstr1500000;int remcount=0

9、;/記錄元素個數；float bitecount=0;/記錄二進制碼的個數；/*/struct huffchar/存放讀入字符的類； int Count;/字符出現的個數； char data;/字符；;int Count=1;/記錄huff數組中字符實際出現的個數；huffchar huff1000;/類的對象；/*/*文件讀入部分和統(tǒng)計字符出現的頻率*/bool char_judge(char c)/判斷字符出現的函數； for(int i=1;i=Count;i+) if(huffi.data=c)huffi.Count+;return true;/如果出現過，出現的頻數加1； retu

10、rn false;void char_add(char c)/添加新出現的字符； huffCount.data=c; huffCount+.Count+;/個數增加，/文件的讀取void read_file_count() char c; ifstream infile; infile.open(huffman.txt);/打開huffman.txt文件； if(!infile)/檢查文件是否打開。 cerr不能打開 huffman.txt文件;/輸出文件未打開的標志。 exit(0); cout讀入的文件中的內容為：endl; while(c=infile.get()!=EOF) remfi

11、le+remcount=c; if(!char_judge(c) char_add(c); coutendl;/*文件讀入和統(tǒng)計字符出現頻率部分結束*/*/*構造huffman樹程序部分*/struct huff_tree/huffman樹結點定義； int parent; int lchild; int rchild; int weight; int sum;/huffman樹中結點的個數； huff_tree huffman1000;void creathuffman()/構造huffman樹的函數 int min1,min2;/指示權值最??； int loc1,loc2;/指向權值最小的

12、兩個數的位置； for(int i=1;i=sum;i+) /對huffman樹的結點進行初始化； huffmani.parent=0; huffmani.lchild=0; huffmani.rchild=0; huffmani.weight=0; for(int ii=1;iiCount;ii+)/將權值賦給huffman.weight; huffmanii.weight=huffii.Count; sum=2*Count-3;for(int j=Count;j=sum;j+) loc1=loc2=0;/權值最小的 min1=min2=2000000; for(int k=1;k=j-1;

13、k+)/求權值最小的兩個地址； if(huffmank.parent=0) if(huffmank.weight=min1) min2=min1;min1=huffmank.weight; loc2=loc1;loc1=k; else if(huffmank.weight=min2) min2=huffmank.weight;loc2=k;/將求出的兩個權值最小的結點合并為新的結點，并將新的結點存入數組中 huffmanloc1.parent=j; huffmanloc2.parent=j; huffmanj.lchild=loc1; huffmanj.rchild=loc2; huffman

14、j.weight=huffmanloc1.weight+huffmanloc2.weight; /*構造huffman樹的程序部分結束*/*huffman編碼開始*/struct huffcode/結構體 string bits100;/存放解碼； int start;/ int count;/頻數 string c;/存放字符；;huffcode hcode100;void huffmancode()/編碼函數 int rem,p;int count1=0; for(int y=1;y=Count;y+) /編碼部分； rem=y; hcodey.start=sum; hcodey.c=hu

15、ffy.data; p=huffmany.parent; while(p!=0) if(huffmanp.lchild=rem)hcodey.bits+count1=0; else 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) couthcodet.bitsr-; coutendl; /

16、*/ string str;void code_huffman_file() ofstream fp; cout請輸入文件名endl例如：huffman1.txtendl; cout該文件用來存放編碼后的文件即壓縮文件str; fp.open(str.c_str(); if(!fp)/檢查文件是否打開。 cerr不能打開 str文件endl;/輸出文件未打開的標志。 exit(0); for(int j=1;j=remcount;j+) for(int i=1;i0;k-) fphcodei.bitsk;bitecount+; break; fp.close();/*編碼并將編碼存入文件部分結

17、束*/string s1;/void code_file_out()/將編碼過的文件恢復； ifstream fp1;/編碼文件； ofstream fp2;/解壓縮文件； fp1.open(str.c_str(); if(!fp1)/檢查文件是否打開。 cerr不能打開 str文件endl;/輸出文件未打開的標志。 exit(0); char inchar; cout請輸入文件名endl例如：huffman2.txtendl; cout該文件用來存放解壓后的文件s1; fp2.open(s1.c_str(); if(!fp2)/檢查文件是否打開。 cerr不能打開s1文件inchar; if

18、(inchar=1)ptr=huffmanptr.rchild;/查找相應編碼對應huffman樹中的位置， else ptr=huffmanptr.lchild; if(huffmanptr.rchild=0&huffmanptr.lchild=0)/判斷是否為葉子結點； fp2huffptr.data;ptr=sum;/是葉子結點，將該結點的對應字符輸入到文件中； coutendl 請檢查原文件huffman.txt與解壓縮文件s1endlendlendl; /cout*請檢查*endl;/*解壓縮文件部分結束*/void evaluating() float y1; y1=bitecou

19、nt/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)/檢查文件是否打開。 cerr不能打開 s1文件endl;/輸出文件未打開的標志。 exit(0); cout輸入文件名用來存放壓縮后的文件endl例如huffman3.txts2; char inchar,ch; fp2.open(s2.c_str(); if(!fp2)/檢查文件是否打開。 cerr不能打開 s2文件inc

20、har; s=inchar-0; t*=2; t+=s; f+; if(f=7) ch=t; t=0; fp2ch; strstrtot+=ch; f=0; strstrtot=0; fp1.close(); fp2.close();string s3;/文件解壓2名queues;string s4;void yichu() ifstream fp1; ofstream fp2; fp1.open(s2.c_str(); if(!fp1)/檢查文件是否打開。 cerr不能打開 s2文件endl;/輸出文件未打開的標志。 exit(0); cout輸入文件名用來存放解壓后的文件endl例如huf

21、fman4.txts3; fp2.open(s3.c_str(); if(!fp2)/檢查文件是否打開。 cout不能打開 s3文件endl;/輸出文件未打開的標志。 exit(0); int inchar; int i=0; while(!s.empty()s.pop(); for(int ptr=sum;itot;) if(s.size()ch; ch=strstri+; num=ch; for(int i=6;i=0;i-) ai=num%2;num/=2; for(int i=0;i7;i+) /ch=ai+0; s.push(ai); inchar=s.front(); s.pop(); if(inchar=1)ptr=huffma