软件压缩/解压缩软件Szip（Huffman算法及应用）

完整代码下载地址

1．需求规格说明

【问题描述】

利用哈夫曼树编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间，但是，这要求在首先对一个现有文件进行编码形成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件（控制台程序，不要求界面）

【基本要求】（60%）

一个完整得系统应具有以下功能：
（1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据得权值，压缩前后文件得大小），在屏幕上输出。
（2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数 据一起写入文件中，形成压缩文件(**.Haf)。
（3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其 中的数据，进行译码后，写入文件，完成解压缩。
（4）程序使用命令行方式运行
压缩命令 ：SZip A Test.Haf 1.doc
解压缩命令：SZip X Test.Haf 2.doc 或 SZip X Test.Haf
用户输入的命令不正确时，给出提示。
（5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。

【提高要求】（40%）

（1）采用不同的数据集，比较其压缩比，采用最有效的压缩方式。
（2）多个文件的压缩。
（3）试构建程序框架，使其能添加新的压缩/解压缩算法（例如书上 LZW 压缩算法）。

2．总体分析与设计

（1）设计思想：

【存储结构】

1、构建一个哈夫曼树结点的结构体，其中包括记录结点权值的数据元素、记录结点双亲位置及左右孩子位置的数据元素、记录结点哈夫曼编码的int型指针、记录结点哈夫曼树编码长度的数据元素。
2、利用动态数组来保存哈夫曼编码。
3、本题通过构建哈夫曼树来进行压缩和解压缩，当压缩式即从下至上建树，解压缩时即从上至下读树。

【主要的算法思想】

本题需要我们运用哈夫曼树的算法来实现软件的压缩和解压，而压缩即可以理解为从下至上建树，解压缩时即可以理解为从上至下读树。
在压缩时，我们首先要把需要压缩的文件用二进制的形式打开，然和把其中的字符转换成ascll码，然后进行对比，把具有相同ascll码的字符统计出来进行归类，并计算同类字符的权重，根据权重从下至上建立哈夫曼树，再生成哈夫曼编码（其中，权重大的结点哈夫曼编码短，权重小的结点哈夫曼编长，），然后把哈夫曼编码列出来后，8位进1（1Byte=8 Bit），当后面的哈夫曼编码不足八位时 则要在其后边进行补0后向进1，然后再将所有的字节输出到文件中，形成压缩文件。
在解压缩时，我们同样是要把需要解压缩的文件用二进制的方式进行打开，然后从上至下的读取哈夫曼树，读取哈夫曼编码，将哈夫曼编码装换成编码前对应的内容，即分别对应哈夫曼树中结点的内容，这里要注意的是我们读取的最后一个字节可能是不足8位的，所以我们要注意记录不足八位时的缺省个数，然后再分别对应哈夫曼树中的数据，从而实现解压操作，最后把解压后的内容输出即可。
最后编写计算文件内占用字节大小的函数，再根据占用内存大小计算压缩率；然后通过对比压缩前和解压后文件内每个字符是否一致来判断解压前和解压后的文件内容是否完全一致。

（2）设计表示：

（3）详细设计表示：

1、countFrequency()统计字符出现次数
首先以二进制方式打开文件，然后读取其中的字符，判断这个字符是否是第一次出现，如果是就把它初始化，然后叶子结点总数加一要是不是第一次出现，就把权值加1。
2、createHuffmanTree()建哈夫曼树
先找出两个权值最小的结点然后建树，一直到最后只有一棵树，为了减少压缩文件中需要写入的huffman树的信息，约定小标小的结点做为双亲结点的左孩子。
3、calculateCode() 计算哈夫曼编码
从下往上一直找到根节点，然后一层一层加，计算哈夫曼的长度然后再从上往下找，左孩子编码0，右孩子编码1。
4、addBit(int bit)对一个未满8bit的byte中加入一个bit
如果新增的为0，直接就左移；如果新增为1，就先左移然后与1按位或。
5、resetByte()将byte清空
将byte与byte中bit的个数都赋值0，即清空。
6、doCompress(…）压缩函数
调用前面编写的函数，首先计算每个字符的权值，再根据权值大小建立哈夫曼树，再给树上的结点进行哈夫曼编码，然后把哈夫曼树从上之下将结点位置写入输出文件；将字符的哈夫曼编码写入byte中，即八位算一字节，如果满了就输出字节，并将原字节清空，然后把不足8位的后面补0，然后输出，再清空。
7、doDecompress(…)解压函数
首先读出根节点的位置，然后确立各个几点之间的双亲关系（先左后右），然后方便读取 将数据放入队列，由于在压缩的时候是从上之下存入到文件当中的 所以这个时候直接依此弹出队顶元素即可实现从上至下读树，然后八位一循环，分别与哈夫曼树的左右孩子进行比较，找出哈夫曼编码最后一个字原本对应的内容，注意最后不足8位的字节要单独处理。

3．编码

1、编码过程中遇到一些问题，在建立huffman树时不知如何在压缩过程中同时进行编码和建树，不知如何存放编码，编码必须要存储才能建立有效的huffman树。后来想到可以用动态数组保存huffman编码，由于编码长度不定，用动态数组可以弥补这个空缺。
2、对于不满足八位的字符，最开始没预想到这种情况，压缩过程中出现错误，后来通过同学的提醒，才意识要进行补位的操作。若新增的bit为0，则直接将byte按位左移；新增的bit为1，先将byte按位左移，再与1按位或运算的规律进行补位操作。补位时，还需要预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数。
3、在测试过程中，解压缩后的文件总是会比原文件大一点，而文件内容的最后总会出现一些乱码，后来通过调试和查找相关资料，我明白了，在ofstream中自带一种文件流指针，便于我们读取文件中的字符，在我压缩的过程当中，压缩到最后，这个文件流指针就走到了文件的最后，而该指针占用一i定的内存，所以在压缩过程中把该指针也进行了压缩，解压缩时自然也输出了该指针，所以会出现解压缩后的文件要比原文件大，所以我在压缩函数中增加了ofsFile.seekp(0, ios::beg);函数，将写指针移动到文件开头，从而解决了该问题。

4．程序及算法分析

【使用说明】

输入文件存储的位置，压缩/解压缩文件
（写博客的时候才发现，我这里给的执行命令好像和老师要求的执行命令不一样，不过是小问题哈哈，读者私下自己改一下好了😁）

【测试数据】

1、压缩文件

2、解压缩文件

3、对比原文件与解压缩后的文件

【讨论与分析】

Huffman压缩以字节为单位进行压缩，将8个bit作为一个byte，通过对bit进行操作，以达到压缩与解压的目的

【改进设想】

1、我现在只实现了基本要求，没能实现多个文件的同时压缩
2、我的压缩算法不是很好，以至于我的压缩率比较大，日后还需要多多学习才能逐步提高自己的能力

5．附录

【压缩函数核心代码】

//压缩函数 成功执行返回 true 失败 false bool HuffmanTree::doCompress(char *pcInput, char *pcOutput) {if (!countFrequency(pcInput)) //如果不能计算字符出现的次数就返回false 可以计算就继续执行程序return false;createHuffmanTree();calculateCode();ifstream ifsFile;ofstream ofsFile;ifsFile.open(pcInput, ios::binary);ofsFile.open(pcOutput, ios::binary);char c;if (!ifsFile){cout << "Unable to open the file" << pcInput << '!' << endl;return false;}if (!ofsFile){cout << "Unable to open the file" << pcOutput << '!' << endl;return false;}//输出huffman编码/*while (ifsFile.get(c)){ int _nTem = c + 128;for (int i = 0; i < HT[_nTem].nCodeLenght; i++){ofsFile << HT[_nTem].pnCode[i] << endl;}}*/ofsFile.put(0); //预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofsFile.put(mnRoot - 384); //将根节点的位置-384写入（为使该值不超过char的最大表示范围）//384=256+128for (int i = 0; i<nLeaf * 2 - 1; i++) //从上往下{ //写入每个结点的双亲结点位置if (HT[i].nParent == -1) //若该节点没有双亲结点，则写入127(一个字节所能表示的最大值2⁷-1=128-1=127)ofsFile.put(127);else //否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）ofsFile.put(HT[i].nParent - 384);}while (ifsFile.get(c)){ //将字符的huffman编码并加入byte中int _nTem = c + 128;for (int i = 0; i < HT[_nTem].nCodeLenght; i++){//ofsFile.put(HT[_nTem].pnCode[i]);addBit(HT[_nTem].pnCode[i]); //将字符的huffman编码并加入byte中if (mnBitsNum == 8){ //若byte已满8位，则输出该byte并将byte清空ofsFile.put(mcByte);resetByte();}}}if (mnBitsNum != 0){//满足8位的前面已经通过resetByte()函数清空了 mbitsNum置为0 而不满足8位的执行下面语句//处理最后未满8个字符的byte，用0填充并记录填充的个数for (int i = mnBitsNum; i<8; i++){addBit(0);mnLackNum++;}ofsFile.put(mcByte); //再输出and清空resetByte();}ofsFile.seekp(0, ios::beg); //将写指针移动到文件开头（文件流指针）ofsFile.put(mnLackNum); //写入最后一个字节缺失的bit个数ifsFile.close();ofsFile.close();return true; }

【解压缩函数核心代码】

//解压缩函数 成功执行返回 true 失败 false bool HuffmanTree::doDecompress(char *pcInput, char *pcOutput) {queue<char> q;char c;ifstream ifsFile;ofstream ofsFile;ifsFile.open(pcInput, ios::binary);ofsFile.open(pcOutput, ios::binary);if (!ifsFile){cout << "Unable to open the file" << pcInput << '!' << endl;return true;}if (!ofsFile){cout << "Unable to open the file" << pcOutput << '!' << endl;return false;}ifsFile.get(c);mnLackNum = c; //读出最后一个字节缺失的bit个数ifsFile.get(c);mnRoot = c + 384; //读出根结点的位置for (int i = 0; i < nLeaf * 2 - 1; i++){ //建立各结点之间的双亲孩子关系ifsFile.get(c);if (c == 127) //等于127->根节点continue;else{HT[i].nParent = c + 384;if (HT[c + 384].nLeftChild == -1)//双亲孩子关系——先左后右HT[c + 384].nLeftChild = i;elseHT[c + 384].nRightChild = i;}}int _nPoint = mnRoot;//为了方便处理最后一个可能有缺失bit的字节，先将读出的数据放入队列while (ifsFile.get(c))q.push(c);//还原文件过程while (q.size()>1){ //还未到最后一个字节c = q.front(); //返回队顶元素for (int i = 0; i < 8; i++){ //先左后右if (int(c & 128) == 0){_nPoint = HT[_nPoint].nLeftChild;//这个左孩子没有左孩子也没有右孩子就把这个输出if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot; //更新}c = c << 1;}else{_nPoint = HT[_nPoint].nRightChild;if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot;}c = c << 1;}}q.pop(); //弹出队顶元素}c = q.front(); //最后一个字节for (int i = 0; i < 8 - mnLackNum; i++) //原理同上{if (int(c & 128) == 0){_nPoint = HT[_nPoint].nLeftChild;if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot;}c = c << 1;}else{_nPoint = HT[_nPoint].nRightChild;if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1){ofsFile.put(char(_nPoint - 128));_nPoint = mnRoot;}c = c << 1;}}q.pop();ifsFile.close();ofsFile.close();return true; }

注：点击此处下载源代码程序包，感谢阅读~

总结

以上是生活随笔为你收集整理的c++ 数据结构 软件压缩/解压缩软件Szip（Huffman算法及应用）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。