huffman编码与解码实现文件压缩与解压缩.doc

采用哈夫曼编码思想 实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比 一、问题分析和任务定义 1.1实验任务 采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比。要求（1）压缩原文件的规模应不小于5K。（2）提供解压缩后文件与原文件的相同性比较功能。 1.2问题分析 本实验是利用哈夫曼编码思想，设计对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。要解决以上问题，需从以下几个方面着手：  （1）如何读入待压缩的文本文件，统计文本文件中各字符的频数及出现的字符个数；  （2）如何构造huffman树，进行huffman编码，生成压缩文件（后缀名.txt）  （3）如何读入待解压的压缩文件名,并利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，生成解压文件（后缀名为.txt）；  （4）如何提供提供压缩前后的占用空间之比 1.3输入、输出数据的形式、值的范围，算法（程序）所能达到的功能 本实验的数据主要是以字符型为主，还有一些自定义的整形和浮点型变量，该实验室对文件进行压缩和解压（被压缩文件容量要求大于5KB），通过该算法程序可以大致上满足实验所要求的功能，即压缩原文件的规模不小于5KB，提供了压缩后的文件与原文件的压缩比例，也即提供了性能比较功能 1.4 测试用的数据 本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据。 所测试的部分数据： 二、概要设计和数据结构的选择 为了完成实验所要求的任务，解决的问题及方法如下： 1.文件的读取及统计字符出现的个数和频率 （1）void read_file_count() {char c; ifstream infile; infile.open(huffman.txt);//打开huffman.txt文件 if(!infile)//检查文件是否打开。 {cout不能打开 huffman.txt文件;//输出文件未打开的标志 exit(0);} cout读入的文件中的内容为：endl; while((c=infile.get())!=EOF)//EOF是文件结束的标志 coutendl;} (2)计所出现的字符个数 void char_add(char c) {huff[count].data=c; huff[count++].count++;//个数增加} (3)计每个字符出现的频率： bool char_judge(char c) {for(int i=1;i=count;i++) if(huff[i].data==c){huff[i].count++;return true;} //如果出现过，出现的频数加1 return false;} 2.构造 huffman树 解决了上述问题，接下来要考虑的是怎样去构造huffman树的问题，进行huffman编码，对文件进行压缩。为了构造huffman树，我将每个字符出现的频率赋予huffman树中叶子结点的权值，从而构造huffman树，也即先查找两个权值最小的结点，合并为新的结点，并将新的结点存入数组中，继续比较合并，最后形成huffman树。 3.huffman编码 利用构造好的huffman树，进行编码：设需要编码的字符集合为{d1,d2,……,dn},各个字符在电文中出现的次数集合为{w1,w2,……,wn}，以d1,d2,……,dn作为叶结点，以w1,w2,……,wn作为各叶子结点的权值构造一棵二叉树，规定HUFFMAN树中的左孩子结点为0，右孩子结点为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码就为HUFFMAN编码。 4.文件压缩问题 采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样就能对文件进行压缩。 在计算机存储中，是以二进制来存储的，本来每个字符将占据8位，而通过huffman编码后，一个字符在计算机存储中，将占据的位数少于8位，这样将大大减少存储空间，从而实现对文件的压缩。 5.读入压缩文件，并对其解压。 对如何读取压缩文件，采用的方法大致和开始相同，在此不赘述。为解压，利用构造好的 huffman树，再根据读取的huffman编码文件，在huffman树中查找叶子结点，查找到叶子结点，放入另一个文本文档中，并输出。其具体查找过程是从根结点开始，根据读入的二进制编码（huffman1.txt中）及生成的huffman树，查找叶子结点，当读到的是“0”时，从左孩子结点继续查找，当读到“1”时，则从右孩子结点继续查找，直