基于赫夫曼編碼的文本壓縮程序

1、基于赫夫曼編碼的文本壓縮程序一、目的及意義通過課程設(shè)計的綜合訓(xùn)練，旨在幫助學(xué)生進一步系統(tǒng)的掌握數(shù)據(jù)結(jié)構(gòu)這 門課的主要內(nèi)容，并進一步培養(yǎng)學(xué)生分析問題和解決問題的能力，主要體現(xiàn)在 能夠讓學(xué)生針對實際問題有效地組織數(shù)據(jù)，選擇合適的數(shù)據(jù)結(jié)構(gòu)，并進行正確 和高效地算法設(shè)計，并用程序?qū)崿F(xiàn)算法。該課的課程設(shè)計是一個良好的程序設(shè) 計技能訓(xùn)練的過程使學(xué)生能夠：1 .了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計 能力。2 .初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基 本技能和方法。3 .提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力。4 .訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般

2、規(guī)范進行軟件開發(fā)，培養(yǎng)計算機科 學(xué)與技術(shù)專業(yè)學(xué)生所具備的科學(xué)的工作方法和作風(fēng)。二、程序功能描述程序?qū)崿F(xiàn)的功能：對文本文件進行壓縮以及對壓縮的文本文件進行解壓 縮。程序的實現(xiàn)的理論依據(jù)是赫夫曼編碼。赫夫曼編碼是一種無損的壓縮算 法，一般用來壓縮文本和程序文件。赫夫曼壓縮屬于可變代碼長度算法一族。 意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因 此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號， 則用較長的位序列。程序由三個文件組成：頭文件 CourseDesign.h、函數(shù)實現(xiàn)文件 CourseDesign.cpp、測試文件 Test.cpp 。在 Co

3、urseDesign.h 中聲明數(shù)據(jù)的存 儲結(jié)構(gòu)以及程序所需要的處理函數(shù)；CourseDesign.cpp文件實現(xiàn)在 CourseDesign.h中聲明的函數(shù)；Test.cpp負責(zé)對所實現(xiàn)的函數(shù)進行調(diào)用測 試，確定是否滿足程序設(shè)計要求。利用赫夫曼編碼實現(xiàn)對文本的壓縮的過程大致為：打開要壓縮的文本文 件，讀取文件中的字符，統(tǒng)計文件中不同字符出現(xiàn)的頻率，建立赫夫曼樹，通 過赫夫曼樹對出現(xiàn)的互不相同的字符進行編碼，建立編碼表，接著將將赫夫曼 樹（即解碼表）寫入壓縮文件中。再次重新讀取文件中的字符，對每個字符通過 查閱編碼表確定對應(yīng)的編碼，將該字符的赫夫曼編碼寫入壓縮文件。對壓縮文 件的解壓過程為：打

4、開壓縮文件，讀取壓縮文件解碼表部分，讀取壓縮文件的 編碼數(shù)據(jù)，將壓縮數(shù)據(jù)通過解碼表進行解碼，將解碼出的字符寫入解碼文件 中。程序執(zhí)行后，用戶按照程序的提示選擇相應(yīng)的功能選項。當(dāng)用戶選擇壓 縮功能，此時程序要求用戶輸入要壓縮的文本文件的路徑，用戶輸入完成后。 程序檢查文件是否能夠建立。檢查完成后，程序?qū)⑽募挠脖P讀入內(nèi)存。接著 程序?qū)⒔y(tǒng)計不同字符出現(xiàn)的頻率以及建立編碼表的初步結(jié)構(gòu)。例如當(dāng)文件中存 有如下表所示字符。表1文件字符屬性表字符第一字節(jié)機內(nèi)碼/ASCII第二字節(jié)機內(nèi)碼權(quán)重的 18119620 a9709把 17620914表 1772375班 1762241補 1781852百 1762

5、1417防 18319212飛 1832019博 17816913包 1762522才 1781976方 1831898拜 1762213 A6503份 1832215必 1772165英文字符在計算機中是以標(biāo)準(zhǔn) ASCII碼進行表示，一個英文字符占一個 字節(jié)空間，編碼范圍為0127;漢字在計算機中是以 GB2312S碼進行表小。 每個漢字占兩個字節(jié)存儲空間，漢字的存儲使用機內(nèi)碼，各字節(jié)的機內(nèi)碼編碼范圍為160254現(xiàn)在需要考慮使用怎樣的數(shù)據(jù)結(jié)構(gòu)來存放這些字符，如果采 用如下簡單的數(shù)據(jù)結(jié)構(gòu)存放：typedef structchar data3 ; / 存放字符int internal_code

6、1 ; 存放第一字節(jié)的機內(nèi)碼/ASCII碼int internal_code2 ； 存放第二字節(jié)的機內(nèi)碼，英文默認為0 intweight ; /存放字符的權(quán)重char*code ; /字符的赫夫曼編碼CodeList,*CodePList ；分析所要處理的字符數(shù)據(jù)會發(fā)現(xiàn)：許多的字符的第一字節(jié)的機內(nèi)碼相同，如"防"、"飛"、"方"、"份"，第一字節(jié)機內(nèi)碼都是183。這是因為漢字是 通過劃分區(qū)號和位號來表示的，所有漢字被劃分成了94個區(qū)，94個位，所以當(dāng)漢字屬于同一個區(qū)，那么它的第一字節(jié)機內(nèi)碼就會相同。如果采用如上的

7、數(shù) 據(jù)結(jié)構(gòu)建立的線性表來存放處理字符，就會存在大量數(shù)據(jù)冗余。在這種情況下，就有必要為特定的數(shù)據(jù)設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)。通過分 析，采用如下數(shù)據(jù)結(jié)構(gòu)：typedef structchar internal_code ; 存放第二字節(jié)機內(nèi)碼char*code ; /存放字符的赫夫曼編碼InternalCode ;typedef structint count ; /已編碼字符數(shù)char internal_code ; 存放第一字節(jié)機內(nèi)碼InternalCode*internal_code_address ; / 第二字節(jié)機內(nèi)碼及字符的HuffmanCode,*HuffmanPCode； / 赫夫曼編碼

8、的地址該結(jié)構(gòu)的優(yōu)點：當(dāng)漢字的第一字節(jié)機內(nèi)碼相同，則該第一字節(jié)機內(nèi)碼只 會被存儲一次，從而消除漢字第一字節(jié)機內(nèi)碼存儲的冗余，而且可以方便的使 用折半查找快速檢索編碼表來確定字符的赫夫曼編碼。采用該數(shù)據(jù)結(jié)構(gòu)對表1數(shù)據(jù)進行表示如圖1。圖1編碼表HC的存儲結(jié)構(gòu)這種數(shù)據(jù)結(jié)構(gòu)形式上類似于圖的鄰接表結(jié)構(gòu)，功能上類似于哈希表的鏈 地址法。但鄰接表的表結(jié)點采用鏈?zhǔn)酱鎯?，而圖 1的表結(jié)點和頭結(jié)點都采用線 性表儲存。圖1中編碼表HC的內(nèi)碼1是縱向非遞減排列，內(nèi)碼2是橫向非遞 減排列。HCi.count - HCi - 1.count 等于HCi實際存儲的字符數(shù)量。 例如,HC3中字符數(shù)為7, HC2中字符數(shù)為2,則

9、HC3存放了 5個字符，這 5個字符擁有相同的第一字節(jié)機內(nèi)碼176。程序執(zhí)行壓縮操作詳細過程：當(dāng)程序從文件中讀取一個字符后，通過字 符的編碼范圍分析該字符是屬于 ASCII還是GB2312若是ASCII編碼，增加編 碼表HC縱向表長，將該字符的ASCII碼按非遞減次序插入到內(nèi)碼1處，并將 當(dāng)前位置的字符數(shù)加1,并置內(nèi)碼2默認為0;如果是漢字，首先通過折半查 找算法縱向查找編碼表HC的內(nèi)碼1成員，若當(dāng)前漢字第一字節(jié)機內(nèi)碼已經(jīng)出 現(xiàn)過，則折半查找返回該機內(nèi)碼 1在HC表中的位置，增加當(dāng)前位置的橫向表 長，將漢字的第二字節(jié)機內(nèi)碼按非遞減次序插入當(dāng)前位置的內(nèi)碼2處。否則將漢字的第一字節(jié)機內(nèi)碼按非遞減次

10、序插入 HC表的內(nèi)碼1區(qū)域，第二字節(jié)機內(nèi) 碼直接插入內(nèi)碼2處。在讀取文件的同時記錄文件中各字符出現(xiàn)的頻率，當(dāng)編 碼表 HC表構(gòu)建完成，止匕時 w=3,9,14,3,1,2,17,5,5,13,2,6,20,9,8,5,12。依次從w中選擇權(quán)重最小并且雙親為0的兩個結(jié)點，根據(jù)這兩個結(jié)點生成新的 結(jié)點，新結(jié)點的權(quán)重為這兩個最小結(jié)點的和，新結(jié)點的左右子樹為這兩個結(jié)點 在w中的位置。根據(jù)表1數(shù)據(jù)構(gòu)建赫夫曼樹如圖2所示。赫夫曼樹存儲結(jié)構(gòu)的 初始狀態(tài)如圖3(a),終結(jié)狀態(tài)如圖3(b)。圖2根據(jù)表1構(gòu)造的赫夫曼樹圖3(a)HT初始狀態(tài)圖3(b)HT終止?fàn)顟B(tài)根據(jù)生成的赫夫曼樹對HC表中的字符進行編碼，編碼的方

11、法：從該葉子 到根逆向求該字符的編碼。例如圖 2中"把"的權(quán)值為14,對應(yīng)的編碼為： "000" o 將得到的赫夫曼編碼寫入 HCernal_code_addressj.code 指 向的區(qū)域。當(dāng)字符編碼完成之后，打開壓縮文件，將赫夫曼樹HT中除權(quán)重以外的數(shù)據(jù)(解碼無需權(quán)重信息)寫入壓縮文件中，作為下一次解壓縮的解碼表。再次打開要壓縮的文本文件，讀取文件中的字符，根據(jù)編碼的范圍確定該字符 是ASCII還是GB2312如果ASCII則調(diào)用折半查找函數(shù)，在編碼表 HC中進行 縱向查找，查找此ASCII出現(xiàn)的位置pl,該字符的編碼為 HC

12、ernal_code_address1.code ;如果字符是漢字，則調(diào)用折半查找 先縱向查找該漢字的第一字節(jié)機內(nèi)碼在HC中的位置pl,然后從HCernal_code_address開始橫向查找該漢字的第二字節(jié)機內(nèi)碼的位置p2,這樣就得到了該漢字的赫夫曼編碼為 HCernal_code_addressp2.code因為赫夫曼編碼在HC表中是以字符串形式存放（因為計算機的基本儲單位是字節(jié)，如果以位存放，需要另設(shè)一 個空間來表示未編碼的位空間大?。?。所以需要將字符串"0101”轉(zhuǎn)換為二進制 0101寫入文件。因為每個赫夫曼編碼的長度是不一樣的，假設(shè)某字符的赫夫 曼

13、長度為4,則將該編碼寫入一個字節(jié)后，還剩余 4個位，則下一次可以繼續(xù) 從第5個位開始寫入，當(dāng)所有字符的編碼都寫入完畢后，最后一個字節(jié)并不一 定會用完,所以需要附設(shè)一個字節(jié)來記錄最后一個字符編碼實際寫入的編碼位 數(shù)。編碼文件的結(jié)構(gòu)如下圖所示：圖4壓縮文件存儲結(jié)構(gòu)程序解壓文件：打開壓縮文件，取出壓縮文件的解碼表長度N,根據(jù)N讀取N條解碼表記錄，重建解碼表 HT,然后讀取壓縮數(shù)據(jù)DATA解碼的過程是 從根出發(fā)，按DAT徽據(jù)的0或1確定找左子樹還是右子樹，直至葉子結(jié)點， 便求得了 DATA®應(yīng)的字符。將字符寫入文件，直至所有DAT徵據(jù)處理完畢，整個解壓過程結(jié)束。三、程序源代碼1.頭文件 Co

14、urseDesign.h#ifndef _COURSEDESIGN_H_#define _COURSEDESIGN_H_/-Huffman 樹存儲結(jié)構(gòu) typedef struct char ch3;unsigned int weight ；unsigned int parent,lchild,rchild ;HTNode,*HuffmanTree ；/-Huffman 編碼表存儲結(jié)構(gòu)typedef structchar internal_code ;char*code ;InternalCode ;typedef structint count ;char internal_code ;In

15、ternalCode*internal_code_address ;HuffmanCode,*HuffmanPCode；/-解碼表存儲結(jié)構(gòu)typedef structchar ch3;unsigned int lchild,rchildDecodeList,*DecodePList ；/-輔助數(shù)組，置/取一個字節(jié)的指定位const static unsigned charmask8=0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01;template class Tstatic int xj_Search_Bin(int key,T L,int low,int hi

16、gh) ；template class Tstatic void xj_InsertSort(T L,int start,int end);void xj_Select(const HuffmanTree HT,int n,int&s1,int&s2)void xj_Statistics(HuffmanPCode&HC,int internal_code1,int internal_code2,int(*FrequencyMeter)255,int&n)bool xj_Init(char*filename,HuffmanPCode&HC,int*&

17、;w,int&n)void xj_CreateHuffmanTree(HuffmanTree&HT,const HuffmanPCodeHC,const int*w,int n) ；void xj_HuffmanCoding(const HuffmanTree HT,HuffmanPCode HC,int n)；bool xj_Compress(char*ifilename,char*ofilename,const HuffmanPCode HC,const HuffmanTree HT,int n) ；bool xj_DeCompress(char*ifilename,cha

18、r*ofilename) ；void xj_Interface() ；#endif 2.函數(shù)實現(xiàn)文件 CourseDesign.cpp#include"CourseDesign.h#include iostream#include fstream#include iomanip#include malloc.h#include string.h using namespace std ;/-折半查找-template class Tint xj_Search_Bin(int key,T L,int low,int high)int mid=0 ;int internal_code ;

19、while(low=high)mid=(low+high)/2 ；internal_code=int(Lernal_code&0xFF)if(key=internal_code)return mid ;else if(internal_code key)high=mid-1 ;elselow=mid+1;return 0 ;/-對HC表的字符域做插入非遞減排序-template class Tvoid xj_InsertSort(T L,int start,int end)int i ;L0=Lend;i=end-1 ；while(i=start&&int

20、(Lernal_code&0xFF)int(L0.internal_co de&0xFF)Li+1=Li;i-；Li+1=L0;/-尋找權(quán)重最小的兩個結(jié)點-void xj_Select(const HuffmanTree HT,int n,int&s1,int&s2)int i=0 ; s1=s2=0； for(i=1 ； i=n ； +i)if(HTi.parent=0) if(s1=0)s1=i ； else if(s2=0)s2=i ；else if(HTi.weight HTs1.weight|HTi.weight HTs2.weight) s

21、1=HTs1.weight HTs2.weight?s1 : s2;s2=i ;/-構(gòu)建 HC.internal_code 以及 HC.internal_code_address 結(jié)構(gòu)-void xj_Statistics(HuffmanPCode&HC,int internal_code1,int internal_code2,int(*FrequencyMeter)255,int&n)int position ；if(internal_code1 128)if(FrequencyMeterinternal_code10=0)+n；HC=(HuffmanPCode)reall

22、oc(HC,(n+1)*sizeof(HuffmanCode) ;HCernal_code=internal_code1 ;HCn.count=1 ；HCernal_code_address=(InternalCode*)malloc(2*sizeof(Inte rnalCode);HCernal_code_ernal_code=0 ; /0 號單元未用xj_InsertSort(HC,1,n) ；+FrequencyMeterinternal_code10 ;elseif(FrequencyMeterinternal_code1inter

23、nal_code2=0)position=xj_Search_Bin(internal_code1,HC,1,n) ；imposition! =0)+HCposition.count ;HCernal_code_address=(InternalCode*)realloc(HCpo ernal_code_address,(HCposition.count+1)*sizeof(Internal Code);HCernal_code_addressHCernal _code=internal_c

24、ode2 ；xj_InsertSort(HCernal_code_address,1,HCposition .count);else+n；HC=(HuffmanPCode)realloc(HC,(n+1)*sizeof(HuffmanCode) ;HCernal_code=internal_code1 ;HCn.count=1 ；HCernal_code_address=(InternalCode*)malloc(2*sizeof(Inte rnalCode);HCernal_code_ernal_code=inte

25、rnal_code2xj_InsertSort(HC,1,n) ；+FrequencyMeterinternal_code1internal_code2 ；/-統(tǒng)計不同字符出現(xiàn)的頻率以及構(gòu)建HC的機內(nèi)碼成員結(jié)構(gòu)-bool xj_Init(char*filename,HuffmanPCode&HC,int*&w,int&n)ifstream ifs(filename) ；int i=0,j=0；int FrequencyMeter255255=0 ; char ch1,ch2 ；n=0; HC=NULL w=NULL if(ifs.fail() cout"can

26、't open file ! ”endl ; return false ； while(ch1=ifs.get() ! =EOF) if(int(ch1&0xFF)128) ch2=ifs.get() ； else ch2=0; xj_Statistics(HC,int(ch1&0xFF),int(ch2&0xFF),FrequencyMeter,n) ；HC0.count=0 ；for(i=2 ； i=n ； +i)HCi.count+=HCi-1.count；w=(int*)malloc(HCn.count*sizeof(int) ； for(i=1 ； i

27、=n ； +i) for(j=HCi-1.count ； j HCi.count ； +j) wj=FrequencyMeterint(HCernal_code&0xFF)int(HCi.in ternal_code_addressj-HCi-1.count+1.internal_code&0xFF)；ifs.close() ；return true ;/-構(gòu)造赫夫曼樹HT-void xj_CreateHuffmanTree(HuffmanTree&HT,const HuffmanPCode HC,const int*w,int n)int i=0,j=0;i

28、nt m=0,s1=0,s2=0 ；if(HCn.count=1)return ；m=2*HCn.count-1 ；HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1 ； i=n ； +i) for(j=HCi-1.count+1 ； j=HCi.count ； +j,+w) HTj.ch0=HCernal_code ;HTj.ch1=HCernal_code_addressj-HCernal_code ;HTj.ch2='message' ；HTj.weight=*w ；HTj.l

29、child=HTj.rchild=HTj.parent=0；for(i=HCn.count+1 ； i=m； +i)*HTi.ch=0 ;HTi.weight=HTi.lchild=HTi.rchild=HTi.parent=0；for(i=HCn.count+1 ； i=m； +i)xj_Select(HT,i-1,s1,s2) ；HTs1.parent=i ； HTs2.parent=i；HTi.lchild=s1; HTi.rchild=s2；HTi.weight=HTs1.weight+HTs2.weight ；/-建立編碼表HC-n)void xj_HuffmanCoding(con

30、st HuffmanTree HT,HuffmanPCode HC,intint start=0,c=0,f=0;int i=0,k=1,r=1；char*cd=NULL;cd=(char*)malloc(HCn.count*sizeof(char) ；cdHCn.count-1='message' ；for(i=1 ； i=HCn.count ; +i)start=HCn.count-1 ;for(c=i,f=HTi.parent ; f! =0; c=f,f=HTf.parent)if(HTf.lchild=c)cd-start='0' elsecd-sta

31、rt='1'if(k HCr.count-HCr-1.count)k=1 ；+r ；HCernal_code_addressk.code=(char*)malloc(HCn.count- start)*sizeof(char) ；strcpy(HCernal_code_addressk.code,&cdstart)+k；free(cd)；/-壓縮文件-bool xj_Compress(char*ifilename,char*ofilename,const HuffmanPCode HC,const HuffmanTree HT,int n)ifstr

32、eam ifs(ifilename) ；ofstream ofs(ofilename,ios : binary)；int bit_size=0 ；int position1,position2 ；int internal_code1,internal_code2 ；char ch ；charcode=0 ;char*code_address ；DecodePListdecode_list=(DecodePList)malloc(HCn.count*2)*sizeof(DecodeList)?if(ifs.fail()|ofs.fail() cout"Can't open th

33、e file ! "endl ; return false ； ofs.write(char*)&HCn.count,sizeof(int)； / 寫入解碼表for(int i=1； i=2*HCn.count-1 ； +i) strcpy(decode_listi.ch,HTi.ch)；decode_listi.lchild=HTi.lchild;decode_listi.rchild=HTi.rchild;ofs.write(char*)&decode_listi,sizeof(DecodeList)； while(ch=ifs.get() ! =EOF) int

34、ernal_code1=int(ch&0xFF)； position1=xj_Search_Bin(internal_code1,HC,1,n) ； if(internal_code1 128) internal_code2=0 position2=1 ； else internal_code2=int(ifs.get()&0xFF) ； position2=xj_Search_Bin(internal_code2,HCernal_code_address,1,HCposition1.count-HCposition1-1.count)； code_a

35、ddress=HCernal_code_addressposition2.code；while(*code_address) code|=(*code_address+-48)*maskbit_size%8 ; +bit_size ； if(bit_size%8=0) ofs code ； code=0； if(bit_size%8 ! =0) ofs code ； ofs char(bit_size%8) ; elseofs char(8);ifs.clear() ；ifs.seekg(0,ios : end)；cout"壓縮完成！ "endl

36、;cout”原始文件大?。?quot;ifs.tellg()"B"endl;cout"壓縮文件大?。?quot;ofs.tellp()"B"endl;cout"壓縮率："float(ofs.tellp()/float(ifs.tellg()*100"%nn" free(decode_list) ； free(HT)； free(HC)； ifs.close() ； ofs.close() ； return true ;/-解壓縮文件-bool xj_DeCompress(char*ifilename,ch

37、ar*ofilename) ifstream ifs(ifilename,ios : binary)； ofstream ofs(ofilename) ； int bit_size ； int i ； int m,n ； char buf ； int value ； DecodePList decode_list ;if(ifs.fail()|ofs.fail()cout"Can't open the file ! "endl ;return false ；ifs.read(char*)&n,sizeof(int) ； / 讀取解碼表m=2*n-1 ；dec

38、ode_list=(DecodePList)malloc(m+1)*sizeof(DecodeList)for(i=1 ； i=m； +i)ifs.read(char*)&decode_listi,sizeof(DecodeList)streampos pos1=ifs.tellg() ；ifs.seekg(-1,ios : end)；streampos pos2=ifs.tellg() ；bit_size=(int(pos2-pos1)-1)*8+ifs.get()ifs.seekg(pos1,ios : beg);for(i=0 ； i bit_size ； +i)if(i%8=0

39、)ifs.read(&buf,1) ；value=int(buf&0xFF)； if(int(value&maski%8)! =maski%8)/value 編碼的 i%8+1 位是 0m=decode_listm.lchild;elsem=decode_listm.rchild ;if(decode_listm.lchild=0)ofs decode_listm.ch ；m=2*n-1 ；ifs.close() ；ofs.close() ；free(decode_list) ；cout"解壓完成！ "endl ;return true ;void

40、xj_Interface()nn"；09 計單 nn"cout"-nn"；cout"基于赫夫曼編碼的文本壓縮程序cout”學(xué)號：20090502137姓名：夏軍班級:cout"請選擇功能選項：nn"cout"1.壓縮文件n”;cout"2.解壓縮文件n"cout"3.退出 nn"；cout"-n"；3.測試文件Test.cpp#include"CourseDesign.h"#include iostream#include malloc

41、.h using namespace std ；int main()int n,*w ；char ifile50 ;char compress_file50="d:壓縮文件.huf"char decompress_file50="d:解壓縮文件?.txt"char key ；HuffmanTree HT=NULLHuffmanPCode HC=NUL Ldosystem("cls");xj_Interface() ；cin key ；switch(key)case'1':cout”請輸入壓縮文件路徑:"endl ;cin ifile ；cout"請稍等."endl ;if( ! xj_Init(ifile,HC,w,n)breakif(HCn.count=1)break ；xj_CreateHuffmanTre