郝夫曼编码实现的文件压缩和解压

1、重庆大学实验报告实验题目： 哈夫曼树的应用 学 院： 计算机学院 专业班级：计算机科学与技术 五班 六班 年 级： 2011级 姓 名： 陈云艳 许文丽 王福临 学 号： 20115351 20115352 20115394 完成时间： 2013 年 6 月 1 日指导教师： 石锐 重庆大学教务处制实验项目指导教师评定成绩表学号：20115394姓名：王福临班级：06班项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（4

2、9-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 年 月 日实验项目指导教师评定成绩表学号：20115351姓名：陈云艳班级：05班项目分值参考标准评分

3、学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图

4、表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 实验项目指导教师评定成绩表学号：20115352姓名：许文丽班级：05班项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答

5、老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 重庆大学本科学生实验项目任务书实验题目哈夫曼树的应用学院计算机学院专业计算机科学与技术年级2011级任务描述： 综合运用C+编程技术和数据结构知识，用VS2010或QT设计实现一个简单的哈夫曼编码解码系统。最后提交完整的设计报告和软件程序拷贝。p 设计要求：Complete the implem

6、entation of the Huffman coding tree, building on the code presented in Section 5.6. Include a function to compute and store in a table the codes for each letter, and functions to encode and decode messages. This project extended to support le compression. To do so requires adding two steps: (1) Read

7、 through the input le to generate actual frequencies for all letters in the le; and (2) store a representation for the Huffman tree at the beginning of the encoded output le to be used by the decoding function. If you have trouble with devising such a representation, see Section 6.5.You can refer to

8、 the figure as below:参考资料：p Data Structures and Algorithm Analysis (C+ Version) Clifford A. Shafferp Data Structure and Algorithm Analysis in C+ (Third Edition)，Mark Allen Weiss， Pearson Education, 2006. p Data Structures, Algorithms, and Applications in C+，Sartaj Sahni， McGraw-Hill, 1998. p 数据结构（ C

9、 语言版），严蔚敏，吴伟民编著，清华大学出版社，2007年第1版 任务下达日期 2013 年 5月 5 日完成日期 年 月 日实验报告正文1 需求分析1. 有时候我们需要用到将文件进行压缩，以节省空间，是信息得到更更好的存储，特别是一些现在不用到，可以将其进行压缩而以后需要用的时候再解压；2. 郝夫曼编码刚好可以实现我们的这一需要，利用郝夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本；3. 郝夫曼编码的原理比较简单：对于计算机存储文件，它是按照二进制，对应于每个字符的ASCII值，以01序列存储，但是，如果我们把某一个文件中不同字符出现的频率进行统计，然后按照权值排好序

10、，构建一棵郝夫曼树，将权值较大的用较短的01序列编码，相反，将权值较小的用较长的01序列编码，这样就可以达到整个编码长度的最优，这样，用来存储每个字符的01序列在很大程度上比原来计算机的一般存储方式下的01序列要短，这样就达到了压缩的目的；或者可以看作是一个加密解密的过程，因为计算机存储是按照二进制进行的，但是我们是看不到底层的01序列的，它会把01序列转化为对应字符的ASCII值，然后存储该字符；4. 郝夫曼压缩实现方法主要在郝夫曼树的构建，压缩解压函数的实现，所以比较实用，易于实现。2 系统设计1. 我们首先要有一个控制面板，实现对程序的调试功能的操作：因此，在VS2010下建立一个Qt项

11、目，通过对控制面板上的信息响应函数的实现以达到压缩解压的母的，而信息响应函数的内部又去调用我们事先写好的郝夫曼树类中的郝夫曼树的构建函数和压缩解压函数，所以，我们又在VS环境中声明并定义一些相关操作的函数，主要有compress(压缩函数)，decompress(解压函数)，select(选择函数)，change(对调函数)，getweight(得到权重函数)，return（返回参与编码的字符数）以及reinit（重初始化函数（重清空）;在QT中，我们有如下的函数及功能实现：Widget（对信息响应的函数进行初始化），open_source (打开要被压缩的目标文件) open_des（找出解

12、压的文件另存的地址）dealstr（修改地址）des_info（解压后的文件长度）source_info （要压缩的文件的长度）Go（进行压缩/解压操作）2.具体类图如下：郝夫曼树类继承基类的一些树的基本信息，以实现接口连接；QT中Widget类中的函数（与界面信息直接相连的）来调用郝夫曼树中已经写好的压缩解压函数，具体的关系流程如下图： int parent;int lchild,rchild;char code;int weight;char letter;HuffTree 类 return_count（）; Compress（）； reinit（）; Decompress（）; Sele

13、ct（）; Change（）; Reinit（）； Node类继承 调用 调用 调用 调用 Widget 类open_source（）; des_info（）; open_des（）; Go（）； source_info（）; dealstr（）；3. 再来看看我们的界面：（1） 我们设计了encode和decode两个按钮是方便对压缩还是解压的选择，因为在程序内部我们的Go按钮是通过识别两个按钮传进来的信息进行相对应的操作的；（2） 在界面上，我们可以看到当点击压缩并打开路径文件时，下面的路径框里会自动显示所选的文件详细路径，对于解压的目的文件（或称为另存为）路径也会在选中之后显示出来，这样

14、就方便我们去查找源文件和压缩文件了；（3） 下面的undeocded和deocded information 就是通过我们在选中文件和点击Go操作时进行的，并将这些结果显示到屏幕上，主要包括：源文件字节长度，压缩后的头文件字节长度，平均字节长度，压缩后的文件字节长度以及压缩率。 点击按钮开始压缩（解压）点击按钮选择压缩（加密）点击按钮选择解压（解密）被压缩的文件路径（打开）压缩得到的文件路径（另存为）头文件长度（即树的信息长度）源文件字节长度除去树的信息的实际文件长度参与编码的字符占总字符数的比例压缩率：压缩后的实际文件长度与源文件长度之比点击exit按钮，可以提前退出（中断程序）平均字节长度

15、三关键代码描述1.node 节点类：保存每个树节点的基本信息：父节点，左右孩子节点，自己的权重，编码以及名字（字符）。class nodepublic:int parent;int lchild,rchild;char code;int weight;char letter;2. HuffTree 郝夫曼树类：一些基本的对文件的操作函数的实现（1）权值选择函数:因为在构建郝夫曼树的过程中，我们需要选择权值最小的和次小的两个节点，所以需要实现这个函数：void select(int &min1,int &min2,int n)int i,max=0;for(i=0;i<n;

16、i+)if(treei.weight>max)max=treei.weight;min1=min2=i;for(i=0;i<n;i+)if(treei.parent=-1)if(treei.weight<=treemin1.weight)min2=min1;min1=i;else if(treei.weight<=treemin2.weight)min2=i;（2） 由于开始对节点进行01序列编码和最后从根节点依次找到节点是两个相逆的过程，因此需要将读到的字符串进行“掉头”，前者是从节点一直往上找，到根为止，后者是从根开始找，一直到叶节点为止；这样做就可以避免乱码。vo

17、id change(string& in)char ch;int i,j=in.length();for(i=0;i<in.length()/2;i+)ch=inj-1;inj-1=ini;ini=ch;j-;（3）这个函数主要用来清空并初始化，为了使每次所构建的树和每次所要压缩的目标文件一致对应，必须每次都把上一次的树清空，并对本次的树进行初始化。 void reinit() for(int i=0;i<511;i+) treei.code='0' treei.parent=-1; treei.lchild=treei.rchild=-1; treei.w

18、eight=0; for(int j=0;j<256;j+)treej.letter=j; （4）这个函数就是正式对文件开始操作了，我们需要把文件中的字符的频率进行统计，已得到各个字符的权重，这样为后面的郝夫曼树的构建做基础。void getweight(std:string filename)ifstream infile(filename,ios:binary);if(infile.fail()return ;infile.unsetf(ios:skipws);unsigned char in;while(!infile.eof()infile.read(char*)&in,

19、sizeof(unsigned char);if(infile.eof()break; treein.weight+;infile.close();（5）这个函数就是构建郝夫曼树了，通过调用前面提到的Select函数以得到最小的和次小的权值的节点，以此构建，然后将左节点的code赋为0，右节点的字符赋为1。void buildtree()int len=256;int least,less;while(len!=511)select(least,less,len);treelen.lchild=least;treelen.rchild=less;treelen.weight=treeleast

20、.weight+treeless.weight;treeleast.parent=len;treeleast.code='0'treeless.parent=len;treeless.code='1'len+;（6）通过这个函数对文件进行压缩;首先会对数进行清空，这就调用前面提到的reinit()函数了；然后依次建树，读文件，并将得到的字符的编码以每次8位的次序写进目标文件，并且，由于计算机会给不足八位的自动后面补零，所以在读取的时候要对字符串结尾进行特殊处理，要设置异常处理机制，因为有可能字符编码与字符串的结尾重合或混乱，造成压缩错误。再者，我们压缩文件，可以

21、看做是每一个对应的被压缩的文件都有一个对应的树（钥匙）来保存相关的信息，所以我们必须要把这把钥匙即这棵树的信息保存好，以便想要解压对应文件的时候可以直接操作，因此可以看到我们在这个函数中实现了对每一课对应的郝夫曼树的信息保存。void compress(std:string filename1,std:string filename2) reinit();getweight(filename1); buildtree();ifstream infile(filename1,ios:binary);if(infile.fail()return ;infile.unsetf(ios:skipws)

22、;ofstream outfile(filename2,ios:binary);int i,j;unsigned char a1,a2,a3,a4; for(i=0;i<256;i+)/保存对应的树的信息j=treei.weight;a4=j&255;j=j>>8;a3=j&255;j=j>>8;a2=j&255;j=j>>8;a1=j&255;outfile.write(char*)&a1,sizeof(unsigned char);outfile.write(char*)&a2,sizeof(unsi

23、gned char);outfile.write(char*)&a3,sizeof(unsigned char);outfile.write(char*)&a4,sizeof(unsigned char); string code=""string for_now=""unsigned char in,out='0'node temp; while(!infile.eof()infile.read(char*)&in,sizeof(unsigned char);if(infile.eof()break;temp=t

24、reein;while(temp.parent!=-1) for_now+=temp.code;temp=treetemp.parent;change(for_now); code+=for_now;for_now=""while(code.length()>=8)for(i=0;i<8;i+)out=out<<1;if(codei='1')out|=1;code=code.substr(8);outfile.write(char*)&out,sizeof(unsigned char);out='0' out=

25、code.length(); outfile.write(char*)&out,sizeof(unsigned char);out='0'for(i=0;i<code.length();i+)out=out<<1;if(codei='1')out|=1;for(i=0;i<8-code.length();i+)out=out<<1; outfile.write(char*)&out,sizeof(unsigned char); infile.close();outfile.close();（7）相对应的，这个函

26、数实现对文件的解压，首先还是对上一次调用这个函数时留存下的树的信息清空，然后把我们存在压缩文件中的对应的树的信息读出来，然后进行译码，我们的方法是将从根节点向下找时，把经过的节点的编码（要么0要么1）当做一个个的字符拼接起来，直到找到叶节点为止，那么此时就找到了一个节点的编码，可以把它所对应的叶节点letter写进文件，这样就得到了最初我们拿来编码的字符了。 void decompress(std:string filename1,std:string filename2) reinit();ifstream infile(filename1,ios:binary);infile.unsetf

27、(ios:skipws);int i,j=0; unsigned char a1,a2,a3,a4;for(i=0;i<256;i+)infile.read(char*)&a1,sizeof(unsigned char);/读取对应的树的信息infile.read(char*)&a2,sizeof(unsigned char);infile.read(char*)&a3,sizeof(unsigned char);infile.read(char*)&a4,sizeof(unsigned char);j|=a1;j=j<<8;j|=a2;j=j

28、<<8;j|=a3;j=j<<8;j|=a4; treei.weight=j;j=0;buildtree();ofstream outfile(filename2,ios:binary);unsigned char in,out='0'string code=""node temp=tree510;while(!infile.eof()infile.read(char*)&in,sizeof(unsigned char);if(infile.eof()break;for(i=0;i<8;i+)if(in&128)

29、code+='1'else code+='0'in=in<<1;while(code.length()>16)if(code0='1')temp=treetemp.rchild;elsetemp=treetemp.lchild;if(temp.rchild=-1&&temp.rchild=-1)out=temp.letter; outfile.write(char*)&out,sizeof(unsigned char);temp=tree510;code=code.substr(1);in=0;for(i

30、=0;i<8;i+)in=in<<1;if(code0='1')in|=1;code=code.substr(1);j=in;for(i=0;i<j;i+)if(code0='1')temp=treetemp.rchild;else temp=treetemp.lchild;if(temp.rchild=-1&&temp.rchild=-1)/找到叶节点的条件out=temp.letter;outfile.write(char*)&out,sizeof(unsigned char);temp=tree510; co

31、de=code.substr(1);infile.close();outfile.close();（8） 这个函数的功能就是返回我们建树过程中涉及到的编码的字符数，因为它与我们所要计算的 source Entropy 有关。 int return_count()/返回参与了编码的字符个数 int count=0; for(int i=0;i<256;i+) if(treei.weight!=0)count+; return count; 3. Widget类（1）这个类的构造函数初始化了一些接口，即将一些信息响应的函数都在这里面以connect的方式进行了连接，类似于我们在一般类中对私有

32、成员变量的初始化。Widget:Widget(QWidget *parent) : QWidget(parent), ui(new Ui:Widget) ui->setupUi(this); connect(ui->exit,SIGNAL(clicked(),this,SLOT(close(); connect(ui->open_souurce,SIGNAL(clicked(),this,SLOT(open_source(); connect(ui->open_des,SIGNAL(clicked(),this,SLOT(open_des(); connect(ui-&

33、gt;Go,SIGNAL(clicked(),this,SLOT(Go(); connect(ui->source_path,SIGNAL(textChanged(QString),this,SLOT(source_info(); connect(ui->des_path,SIGNAL(textChanged(QString),this,SLOT(des_info();（2） 下面的前两个函数分别是执行打开文件（弹出对话框）和关闭文件（弹出对话框）的操作，我们通过再打开文件或者关闭文件的同时记下文件路径地址，并通过调用槽函数把它先显示到界面上去；后面一个函数dealstr（），这个

34、是基于文件路径在一般情况下与Qt环境下的不同表示方法实现的，原来一般情况下的文件路径如：C:/Users/Administrator/Desktop/wfl.mp3，那么在QT中，文件的路径表示方法为C:UsersAdministratorDesktopwfl.mp3,所以我们必须用这个函数来进行修改；Source_info 和des_info 两个函数分别是调用系统下的函数得到文件的长度，这里需要注意的有两点：一是要保证我们在选中文件时就读出其相关信息；二是要把压缩后的文件的真正长度读出来，因为我们每次都要在文件中保存树的信息（因为是按顺序读取的，因此树的信息就是1024个字节，也就是1kb

35、），所以要把这1KB减掉。void Widget:open_source()/打开文件（弹出对话框） QString filename=QFileDialog:getOpenFileName(); ui->source_path->setText(filename); void Widget:open_des()/关闭文件（弹出对话框） QString filename=QFileDialog:getSaveFileName(); ui->des_path->setText(filename);std:string Widget:dealstr(QString &

36、;in)/修改文件路径形式 int i; for(i=0;i<in.length();i+) if(ini='/')ini='' for(i=0;i<in.length();i+) if(ini='') in=in.left(i)+''+in.mid(i); i+; return in.toStdString();void Widget:source_info() QFileInfo info(ui->source_path->text(); ui->file_length->setText(Q

37、String:number(info.size();void Widget:des_info() QFileInfo info(ui->des_path->text(); ui->file_head_length->setText("1KB"); if(ui->file_length->text().toFloat()!=0&&info.size()!=0) ui->actual_data_length->setText(QString:number(info.size()-1024); ui->comp

38、ression->setText(QString:number(ui->actual_data_length->text().toFloat()/(ui->file_length->text().toFloat();ui->average_code_length->setText(QString:number(ui->compression->text().toFloat()*8);（3）这个函数是整个的核心，即，当我们选择好压缩源文件和压缩后的保存文件后，点击Go按钮就会调用我们的压缩（解压）函数，实现压缩和解压。void Widget:

39、Go() QString source_path=ui->source_path->text(); QString des_path=ui->des_path->text(); if(ui->encode->isChecked() /Tree.reinit(); Tpress(dealstr(source_path),dealstr(des_path); ui->source_centory->setText(QString:number(ui->file_length->text().toFloat()/Tree.return_co

40、unt(); if(ui->decode->isChecked() /Tree.reinit(); Tree.decompress(dealstr(source_path),dealstr(des_path); source_info(); des_info();4 系统测试报告我们的程序能够实现很好的压缩和解压功能，无论是对于一般的文本文件，还是对于大一点的音频文件都能进行压缩和还原（解压）。我们对文本文件压缩后然后立马将其解压回去，发现与源文件完全相同；然后又对音频文件进行测试，发现解压回去的歌曲还是能够如原来播放；5. 运行效果1. 首先对一般的文本文件进行压缩并解压，如下：（1）选中Encode按钮，点击source file按钮，会弹出对话框，这样我们就可以选选择所需要被压缩的文件了；（2）选中文件后，会在下面的textbook中看到文件路径，并且会显示出源文件的长度：（3）然后选中索要存储的目标路径，可以手动输入，也可以通过选择已存在的文件夹等，此时它会显示出用来保存树的信息的头文件的长度：（4）选好后，点击Go按钮，立即可以看到下面的相关信息出现，然后我们就可以找到压缩的目标文件进行查看了：（5） 对于解压，同样的操作，只需把路径选中，然后选中Decode