Huffman编码与解码实现文件压缩与解压

Huffman编码与解码实现文件压缩与解压 Huffman编码与解码实现文件压缩与解压 Huffman编码与解码实现文件压缩与解压 学 号: 06080711 姓 名: 李爱武 指导教师: 陈波 二?一零年九月三日 目录 目录 ..………………………………….2 目标任务和问题分析 ..………………………………….3 算法及思想描述 ..………………………………….3 ---------建立哈夫曼树、压缩、解压缩 程序结构及测试 ..………………………………….5 1 Huffman编码与解码实现文件压缩与解压 测试结果分析 ..………………………………….12 收获与体会 ..………………………………….12 参考文献 ..………………………………….13 2 Huffman编码与解码实现文件压缩与解压 Huffman编码与解码实现文件压缩与解压 一、目标任务与问题分析 1.1目标任务 采用哈夫曼编码思想实现文件的压缩和解压缩功能，可以将任意文件压缩成任意的压缩文件类型，并且能将压缩后的文件解压成相应的源文件。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件(不管包含的是字母还是汉字)采取一个个的字节(unsigned char)处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法思想描述 2.1 构造哈夫曼树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组(后面有节点的定义)空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 哈夫曼树节点的设计 用结构体NODE来存储节点的信息，其中有成员频率weight、父节点parent、左枝节点lchild、右枝节点rchild、对应的编码code。 2.1.2文件字符频率处理 由于所有的文件都采用字节存取，字符的最多个数就只能是256个，即ASCII码在0-255之间，而我们用的是数组来存储文件的信息，我们用NODE[256]来统计文件的所有信息。此操作的过程中应用的关键技术在于我们直接用该数组 的下标来保存每个字符的信息，原因在于字符为单字节，正好与每个下标0-255对应。这样既减少了内存的开销，而且还精简了代码。我们只需要在每读一个字节(inByte)的同时,让对应的NODE[inByte]加一就可以达到统计字符频率的效果。 2.1.3构建哈夫曼树 哈夫曼树的存储结构采用双亲孩子示法，即用结构体数组来实现。为了让程序设计更加的精简，我们直接用扩大节点数组的方法来保存，由于原来的256个叶子节点会产生255个父亲节点，所以我们将原来的空间为256的数组扩大为NODE[511]来构建哈弗曼树。扩充空间后，我们开始初始化哈夫曼树，即通过上述统计的叶子节点循环提取哈弗曼中权值最小的两个节点，将它们合并起来，组成一个新的根节点，直到最后哈夫曼树只剩下一个根节点为止。 2.1.4 获得哈夫曼编码 采用字节进行编码，每个字符的Huffman编码是一个0/1串，最高效的方法是采用的是采用位串的形式，我们先定义每个字符的编码为一个字符串。我们从哈夫曼树的根节点开始循环遍历，并给每个节点设置一个编码标志，约定如果没编码状态为0,，左孩子已编码状态为1，右孩子已编码状态为2，首先如果编码状态为0从左孩子开始，如果有左孩子，那么编码字符串加上“0”字符，状态设为1，如果没有左孩子并且没有右孩子则该节点的编码结束;接着考虑没有左孩子但有右孩子并且右孩子没编码的情况，如果有右孩子则编码字符串加“1”，编码状态为2，如果做有节点都已编码，则再对该节点的兄弟节点进行编码，因为此时除了最后面一个编码字符外，兄弟节点的前部分编码和已完成编码的节点是相同的，没必要重复遍历。 2.1.5 将文件进行二进制压缩 3 Huffman编码与解码实现文件压缩与解压 以上只能得到文件中每个字符的0/1形式的字符串编码，然而如果想要文件起到真的压缩效果，还必须在读取被压缩文件得到每个字节的编码的同时将字符串编码转化拼接成八位的字节存入压缩文件中。为此我们采用的是将编码字符串切割成长度为八的字串，然后再将其通过从低位遍历如果为“1”则与字节(inByte)值为00000000取“或“操作再向左将字节移一位，依次循环八次得到相应的二进制字节存入压缩文件，如果最后剩余不足八位，另作处理即将其长度也在最后以二进制输入，达到压缩的效果。 2.1.6 将二进制压缩文件解压 与压缩文件相似，我们以字节依次读取压缩文件的每个字节(inByte)，一次取字节的每一位，采用的方法是将字节(inByte)与128(10000000)进行“与“ 操作，得到每位，如果为0，从Huffman树的左孩子下行，反之，从右孩子下行，再将(inByte)向右移一位， 不断循环，当循环到孩子节点的下标小于256时，将下标以二进制的方式输入到解压文件中即可。如果到最后一个字节，其循环次数由其长度决定，于是起到减压的效果。 三、程序结构及测试流程 3.1 类的设计 3.1.1 HuffmanTree类 此类用以实现各种算法，其设计如下: 此类为实现压缩与解压缩操作的各种方法，首先通过成员GetWeight函数计算出需要压缩的文件字符及对应的频率，然后通过BuildTree成员函数根据文件的字符及对应频率建立哈夫曼树，然后调用GenerateCode得到每个字节的编码，最后通过Compress函数进行压缩文件，最终利用可利用Decompress函数进行解压测试，其中SelectMiin为辅助函数，选取建立Huffman树之前权重最小的两个节点。 3.1.2 Application类 此类产生的对象用来执行用户选择的各种操作，其设计如下: 此类的公有方法Run启动整个应用程序，供用户选择各种操作，达到了人机交互的效果。 3.1.3 核心函数的说明 压缩函数: void HuffmanTree::Compress(const char *fn1,const char *fn2) //压缩 { ifstream infile(fn1,ios::binary );//以二进制方式打开文件 4 Huffman编码与解码实现文件压缩与解压 ofstream outfile(fn2,ios::binary ); infile.unsetf (ios::skipws);//设置文件得读取空白符 string waiting="";//编码字符串 unsigned char inByte,outByte;//用来构建读入输出字节 int I; while(infile.good()) //判断文件没结束，不存在或没有打开失败等 { while(waiting.length ()<8) { if(!infile.good ()) break; infile.read ((char *) &inByte,sizeof(unsigned char));//读取一个字节 if(infile.good()) waiting+=tree[inByte].code;//得到该字节的huffman编码 } while(waiting.length() >7) { outByte='\0';//字节八位清零 for(i=0;i<8;i++) { outByte=outByte<<1;//左移一位。原因:字符串编码的首位为二进制的最高位 if(waiting[i]=='1') outByte|=1;//当编码为"1"，通过或操作符将其添加到字节的最低位 } outfile.write((char *)&outByte,sizeof(unsigned char));//将得到的字节存入文件 waiting=waiting.substr (8);//编码字符串去除已存储的前八位构成新的字符串 } if(infile.eof ()) { if(waiting.length ()==0) outByte=static_cast(0); else //文件结束，但还剩最后一段不满八位的编码 { outByte='\0'; for(i=0;i<(int)waiting.length ();i++) { outByte=outByte<<1; if(waiting[i]=='1') outByte|=1; 5 Huffman编码与解码实现文件压缩与解压 } outByte=outByte<<(8-waiting.length ());//将编码字段从尾部移到字节的高位 outfile.write((char *)&outByte,sizeof(unsigned char));//存入最后一个字节 outByte=static_cast(waiting.length ()); } outfile.write((char *)&outByte,sizeof(unsigned char));//存入最后编码的长度 } } infile.setf (ios::skipws ); infile.close ();//关闭文件 outfile.close (); } 解压缩函数: void HuffmanTree::Decompress(const char *fn1,const char *fn2) { ifstream ifile(fn1,ios::binary ); ofstream ofile(fn2,ios::binary ); ifile.unsetf (ios::skipws ); ifile.seekg (0,ios::beg);//将文件指针置于文件开始 int i; //for(i=0;i<256;i++) // ifile.read ((char *)&(tree[i].weight),sizeof(long)); //this->BuildTree (); unsigned char inbyte1=0,inbyte2=0,inbyte3=0; int p=510,len=8; ifile.read ((char *)&inbyte1,sizeof(inbyte1));//读取第一个字节 ifile.read ((char *)&inbyte2,sizeof(inbyte2));//读取第二个字节 if(ifile.eof())//考虑只有两个字节 { len=static_cast(inbyte2); for(i=0;i(p); ofile.write ((char *)&p,sizeof(unsigned char)); } } } while(!ifile.eof())//没到文件结尾 { ifile.read ((char *)&inbyte3,sizeof(inbyte3));//读取下个字节 if(!ifile.good())//考虑最后一个字节的情况，计算其对应的编码的长度 len=static_cast(inbyte2); else len=8; for(i=0;i(p); ofile.write ((char *)&p,sizeof(unsigned char)); p=510; } } inbyte1=inbyte2; inbyte2=inbyte3; } ifile.setf(ios::skipws);//文件流复位 ifile.close (); ofile.close(); } 3.2 执行效果 运行改程序弹出菜单，供用户选择，其效果如下: 7 Huffman编码与解码实现文件压缩与解压 选择菜单1提示用户输入被压缩文件名和压缩后的文件名运行结果如下: 选择菜单2 进行解压操作得到的界面如下: 需要退出操作，用户可以选择菜单0 四、测试结果 此压缩软件起到了良好的压缩效果，部分测试数据的结果如下表:表 《一》 《一》 表 压缩前文件大小 压缩后文件大小 压缩率 a.doc(50KB) b.hfm(24KB) 105% t.txt(6KB) t1.law(5KB) 20% e.xls(106KB) E1.hfm(51KB) 110% 从以上结果可以看出此软件对较大的文件效果跟明显，这是与事实相符的，因为文件越大，字符的重复率越高，根据此软件实现算法，频率越高的字符其编码反而短，效果自然更明显。 五、收获与体会 (1) 哈夫曼编码有一些缺点:对于短的文件进行编码意义不大，因为较短的文件字节的重复率不是很高。 (2)哈夫曼进行解压缩软件设计时候，其核心是哈夫曼树，它编码和译码的纽带。该压缩软件采用的正是哈夫曼算法，建立哈夫曼树，对原文件进行哈夫曼编码，通过将哈夫曼算法应用于压缩软件，更进一步理解哈夫曼树的建立和对各个叶子节点的编码。哈夫曼技术对多种文件压缩率很高，对于二进制这种法也很成功。 (3)该程序中因为涉及文件操作，多次读写文件，为了保证操作后的文件与原文件的一致性，在打开或者建立新文件时都是以二进制进行操作，着不仅加深了我们对文件操作的理解，也在程序中体现了完整性，并且将解压后的文件和原文件相比较具有一致性，体现的程序的健壮性 (4)通过这次课程设计，强化了我结构化编程的思想，对复杂问题的数据结构化有了更深刻的了解,对数据结构有了更深的理解，提高了我对算法的设计层次。 六、参考文献 (1) 数据结构教程(C++版)/吉根林，陈波主编，—北京:电子工业出版社，2009.2 8 Huffman编码与解码实现文件压缩与解压 (2) 现代计算机2008年下半月11期 9