基于赫夫曼编码的文本压缩程序

1、基于赫夫曼编码的文本压缩程序一、目的及意义通过课程设计的综合训练，旨在帮助学生进一步系统的掌握数据结构这 门课的主要内容，并进一步培养学生分析问题和解决问题的能力，主要体现在 能够让学生针对实际问题有效地组织数据，选择合适的数据结构，并进行正确 和高效地算法设计，并用程序实现算法。该课的课程设计是一个良好的程序设 计技能训练的过程使学生能够：1 .了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计 能力。2 .初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基 本技能和方法。3 .提高综合运用所学的理论知识和方法独立分析和解决问题的能力。4 .训练用系统的观点和软件开发一般

2、规范进行软件开发，培养计算机科 学与技术专业学生所具备的科学的工作方法和作风。二、程序功能描述程序实现的功能：对文本文件进行压缩以及对压缩的文本文件进行解压 缩。程序的实现的理论依据是赫夫曼编码。赫夫曼编码是一种无损的压缩算 法，一般用来压缩文本和程序文件。赫夫曼压缩属于可变代码长度算法一族。 意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因 此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号， 则用较长的位序列。程序由三个文件组成：头文件 CourseDesign.h、函数实现文件 CourseDesign.cpp、测试文件 Test.cpp 。在 Co

3、urseDesign.h 中声明数据的存 储结构以及程序所需要的处理函数；CourseDesign.cpp文件实现在 CourseDesign.h中声明的函数；Test.cpp负责对所实现的函数进行调用测 试，确定是否满足程序设计要求。利用赫夫曼编码实现对文本的压缩的过程大致为：打开要压缩的文本文 件，读取文件中的字符，统计文件中不同字符出现的频率，建立赫夫曼树，通 过赫夫曼树对出现的互不相同的字符进行编码，建立编码表，接着将将赫夫曼 树（即解码表）写入压缩文件中。再次重新读取文件中的字符，对每个字符通过 查阅编码表确定对应的编码，将该字符的赫夫曼编码写入压缩文件。对压缩文 件的解压过程为：打

4、开压缩文件，读取压缩文件解码表部分，读取压缩文件的 编码数据，将压缩数据通过解码表进行解码，将解码出的字符写入解码文件 中。程序执行后，用户按照程序的提示选择相应的功能选项。当用户选择压 缩功能，此时程序要求用户输入要压缩的文本文件的路径，用户输入完成后。 程序检查文件是否能够建立。检查完成后，程序将文件从硬盘读入内存。接着 程序将统计不同字符出现的频率以及建立编码表的初步结构。例如当文件中存 有如下表所示字符。表1文件字符属性表字符第一字节机内码/ASCII第二字节机内码权重的 18119620 a9709把 17620914表 1772375班 1762241补 1781852百 1762

5、1417防 18319212飞 1832019博 17816913包 1762522才 1781976方 1831898拜 1762213 A6503份 1832215必 1772165英文字符在计算机中是以标准 ASCII码进行表示，一个英文字符占一个 字节空间，编码范围为0127;汉字在计算机中是以 GB2312S码进行表小。 每个汉字占两个字节存储空间，汉字的存储使用机内码，各字节的机内码编码范围为160254现在需要考虑使用怎样的数据结构来存放这些字符，如果采 用如下简单的数据结构存放：typedef structchar data3 ; / 存放字符int internal_code

6、1 ; 存放第一字节的机内码/ASCII码int internal_code2 ； 存放第二字节的机内码，英文默认为0 intweight ; /存放字符的权重char*code ; /字符的赫夫曼编码CodeList,*CodePList ；分析所要处理的字符数据会发现：许多的字符的第一字节的机内码相同，如"防"、"飞"、"方"、"份"，第一字节机内码都是183。这是因为汉字是 通过划分区号和位号来表示的，所有汉字被划分成了94个区，94个位，所以当汉字属于同一个区，那么它的第一字节机内码就会相同。如果采用如上的

7、数 据结构建立的线性表来存放处理字符，就会存在大量数据冗余。在这种情况下，就有必要为特定的数据设计合适的数据结构。通过分 析，采用如下数据结构：typedef structchar internal_code ; 存放第二字节机内码char*code ; /存放字符的赫夫曼编码InternalCode ;typedef structint count ; /已编码字符数char internal_code ; 存放第一字节机内码InternalCode*internal_code_address ; / 第二字节机内码及字符的HuffmanCode,*HuffmanPCode； / 赫夫曼编码

8、的地址该结构的优点：当汉字的第一字节机内码相同，则该第一字节机内码只 会被存储一次，从而消除汉字第一字节机内码存储的冗余，而且可以方便的使 用折半查找快速检索编码表来确定字符的赫夫曼编码。采用该数据结构对表1数据进行表示如图1。图1编码表HC的存储结构这种数据结构形式上类似于图的邻接表结构，功能上类似于哈希表的链 地址法。但邻接表的表结点采用链式存储，而图 1的表结点和头结点都采用线 性表储存。图1中编码表HC的内码1是纵向非递减排列，内码2是横向非递 减排列。HCi.count - HCi - 1.count 等于HCi实际存储的字符数量。 例如,HC3中字符数为7, HC2中字符数为2,则

9、HC3存放了 5个字符，这 5个字符拥有相同的第一字节机内码176。程序执行压缩操作详细过程：当程序从文件中读取一个字符后，通过字 符的编码范围分析该字符是属于 ASCII还是GB2312若是ASCII编码，增加编 码表HC纵向表长，将该字符的ASCII码按非递减次序插入到内码1处，并将 当前位置的字符数加1,并置内码2默认为0;如果是汉字，首先通过折半查 找算法纵向查找编码表HC的内码1成员，若当前汉字第一字节机内码已经出 现过，则折半查找返回该机内码 1在HC表中的位置，增加当前位置的横向表 长，将汉字的第二字节机内码按非递减次序插入当前位置的内码2处。否则将汉字的第一字节机内码按非递减次

10、序插入 HC表的内码1区域，第二字节机内 码直接插入内码2处。在读取文件的同时记录文件中各字符出现的频率，当编 码表 HC表构建完成，止匕时 w=3,9,14,3,1,2,17,5,5,13,2,6,20,9,8,5,12。依次从w中选择权重最小并且双亲为0的两个结点，根据这两个结点生成新的 结点，新结点的权重为这两个最小结点的和，新结点的左右子树为这两个结点 在w中的位置。根据表1数据构建赫夫曼树如图2所示。赫夫曼树存储结构的 初始状态如图3(a),终结状态如图3(b)。图2根据表1构造的赫夫曼树图3(a)HT初始状态图3(b)HT终止状态根据生成的赫夫曼树对HC表中的字符进行编码，编码的方

11、法：从该叶子 到根逆向求该字符的编码。例如图 2中"把"的权值为14,对应的编码为： "000" o 将得到的赫夫曼编码写入 HCernal_code_addressj.code 指 向的区域。当字符编码完成之后，打开压缩文件，将赫夫曼树HT中除权重以外的数据(解码无需权重信息)写入压缩文件中，作为下一次解压缩的解码表。再次打开要压缩的文本文件，读取文件中的字符，根据编码的范围确定该字符 是ASCII还是GB2312如果ASCII则调用折半查找函数，在编码表 HC中进行 纵向查找，查找此ASCII出现的位置pl,该字符的编码为 HC

12、ernal_code_address1.code ;如果字符是汉字，则调用折半查找 先纵向查找该汉字的第一字节机内码在HC中的位置pl,然后从HCernal_code_address开始横向查找该汉字的第二字节机内码的位置p2,这样就得到了该汉字的赫夫曼编码为 HCernal_code_addressp2.code因为赫夫曼编码在HC表中是以字符串形式存放（因为计算机的基本储单位是字节，如果以位存放，需要另设一 个空间来表示未编码的位空间大小）。所以需要将字符串"0101”转换为二进制 0101写入文件。因为每个赫夫曼编码的长度是不一样的，假设某字符的赫夫 曼

13、长度为4,则将该编码写入一个字节后，还剩余 4个位，则下一次可以继续 从第5个位开始写入，当所有字符的编码都写入完毕后，最后一个字节并不一 定会用完,所以需要附设一个字节来记录最后一个字符编码实际写入的编码位 数。编码文件的结构如下图所示：图4压缩文件存储结构程序解压文件：打开压缩文件，取出压缩文件的解码表长度N,根据N读取N条解码表记录，重建解码表 HT,然后读取压缩数据DATA解码的过程是 从根出发，按DAT徽据的0或1确定找左子树还是右子树，直至叶子结点， 便求得了 DATA®应的字符。将字符写入文件，直至所有DAT徵据处理完毕，整个解压过程结束。三、程序源代码1.头文件 Co

14、urseDesign.h#ifndef _COURSEDESIGN_H_#define _COURSEDESIGN_H_/-Huffman 树存储结构 typedef struct char ch3;unsigned int weight ；unsigned int parent,lchild,rchild ;HTNode,*HuffmanTree ；/-Huffman 编码表存储结构typedef structchar internal_code ;char*code ;InternalCode ;typedef structint count ;char internal_code ;In

15、ternalCode*internal_code_address ;HuffmanCode,*HuffmanPCode；/-解码表存储结构typedef structchar ch3;unsigned int lchild,rchildDecodeList,*DecodePList ；/-辅助数组，置/取一个字节的指定位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.函数实现文件 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;/-寻找权重最小的两个结点-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 ;/-构建 HC.internal_code 以及 HC.internal_code_address 结构-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 ；/-统计不同字符出现的频率以及构建HC的机内码成员结构-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 ;/-构造赫夫曼树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”原始文件大小："ifs.tellg()"B"endl;cout"压缩文件大小："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”学号：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