编写基于C++ Huffman 算法的无损压缩程序和解压程序

♻️ 资源大小2.92MB➡️资源下载https://download.csdn.net/download/s1t16/87450324编写基于 Huffman 算法的无损压缩程序和解压程序实验目的编写基于 Huffman 算法的压缩和解压缩程序。你的程序应该能够压缩任意文件并能无损解压。实验环境本实验可基于 Visual Studio Code 等平台开发参考主流的编码规范如 Google CStyle Guide中文版编程语言和开发工具编程语言 ANSI C/C开发工具 Visual Studio Code、编译器 G编码规范遵循良好的程序设计风格来设计和编写程序。基本编码规范标识符的命名要到达顾名思义的程度关键代码提供清晰、准确的注释程序版面要求不同功能块用空行分隔般一个语句一行语句缩进整齐、层次分明。实验内容压缩文件根据 ASCII 码文件中各 ASCII 字符出现的频率情况创建 Huffman 树再将各字符对应的哈夫曼编码写入压缩文件中实现文件压缩。解压文件根据压缩文件时 创建的 Huffman 树构建解码词典解码词典从压缩文件中读取 Huffman 编码并翻译成对应字符写入解压文件中实现文件解压。分析与设计实验原理Huffman 编码的目的是如何用更短的 bit 来编码数据。通过变长编码压缩编码长度。我们知道普通的编码都是定长的比如常用的 ASCII 编码,每个字符都是 8 个 bit。但在很多情况下数据文件中的字符出现的概率是不均匀的比如在一篇英语文章中字母“E”出现的频率最高“Z”最低这时我们可以使用不定长的 bit 编码频率高的字母用比较短的编码表示频率低的字母用长的编码表示。但这就要求编码要符合“前缀编码”的要求即较短的编码不能是任何较长的编码的前缀这样解析的时候才不会混淆。要生成这种编码最方便的就是用二叉树把要编码的字符放在二叉树的叶子上所有的左节点是 0右节点是 1从根浏览到叶子上因为字符只能出现在树叶上任何一个字符的路径都不会是另一字符路径的前缀路径符合前缀原则编码就可以得到。Huffman 树和 Huffman 算法核心思想定义给定 N 个权值作为 N 个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。构建 Huffman 树假设有 n 个权值则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn则哈夫曼树的构造规则为将 w1、w2、…wn 看成是有 n 棵树的森林(每棵树仅有一个结点)在森林中选出两个根结点的权值最小的树合并作为一棵新树的左、右子树且新树的根结点权值为其左、右子树根结点权值之和从森林中删除选取的两棵树并将新树加入森林重复(2)、(3)步直到森林中只剩一棵树为止该树即为所求得的哈夫曼树。前缀码定义任意一个字符的编码都不是另一个字符的编码的前缀,这种编码叫做前缀编码。由于 Huffman 编码的这种特性在解压缩时不会混淆。文件和文件流文件内存中存放的数据在计算机关机后就会消失。要长久保存数据就要使用硬盘、光盘、U 盘等设备。为了便于数据的管理和检索引入了“文件”的概念。一般来说文件可分为文本文件、视频文件、音频文件、图像文件、可执行文件等多种类别这是从文件的功能进行分类的。从数据存储的角度来说所有的文件本质上都是一样的都是由一个个字节组成的归根到底都是 0、1 比特串。不同的文件呈现出不同的形态有的是文本有的是视频等等这主要是文件的创建者和解释者使用文件的软件约定好了文件格式。将文件中定长的字节编码成不定长的 Huffman 编码使在文件在数据不丢失的情况下文件的长度变短从而实验压缩文件的目的。设计程序压缩文件解压文件函数设计#include iostream #include map #include bitset #include string #include cstring #include queue #include list #include fstream #include iomanip using namespace std; struct tree_node{ unsigned char name; tree_node *left, *right; size_t weight; string code; tree_node(unsigned char name_, tree_node *left_, tree_node *right_, size_t weight_, string code_){ name name_;//字符 left left_; right right_; weight weight_;//权重字符出现频率 code code_;//字符对应的Huffman编码的string形式 } }; //统计文件长度计算各字符出现的频率返回文件长度字符到频率的映射存储在char_weight中 size_t char_account(ifstream input, mapchar, size_t char_weight); //跟据字符到频率的映射构建半哈夫曼树返回树的根节点,此时哈夫曼树未编码 tree_node* built_tree(mapchar, size_t char_weight); //销毁树懂得都懂 void destroy_tree(tree_node *); //根据半哈夫曼树节点未编码得到完整的哈夫曼树 在结点处得到字符到它对应的哈夫曼编码和映射 void encoder(tree_node *root, mapchar, string dictionary); //压缩过程压缩成功返回TRUE bool compress(const string source_filename, const string encoded_filename); //解压过程压缩成功返回TRUE bool uncompress(const string encoded_filename, const string source_filename); //统计文件长度 size_t get_filesize(const string filename); //修改文件拓展名 string change_extension(const string filename, const string extension);main.cpp#include Huffman.hpp #define std_extension hwy //自定义压缩文件的拓展名 string change_extension(const string filename, const string extension){ size_t p filename.find_last_of(.); string str filename.substr(0, p) . extension; return str; } int main(){ string input_filename, output_filename, ex; int select; do{ cout *********************************************************************************** endl; cout 1: Compress endl; cout 2: Uncompress endl; cout 0: Exit endl; cout *********************************************************************************** endl; cout Your choice: endl; cin select; switch(select){ case 1: cout Please enter the name of the file you want to compress: endl; cin input_filename; //压缩文件名和原始文件名相同拓展名为自定义的拓展名 output_filename change_extension(input_filename,std_extension); //压缩过程 //汇报压缩信息 if(compress(input_filename,output_filename)){ cout Compress successfully! endl; cout Size of input file: get_filesize(input_filename) endl; cout Size of output file: get_filesize(output_filename) endl; if(get_filesize(input_filename)0) cout Compress ratio: ((double)get_filesize(output_filename) / (double)get_filesize(input_filename)) * 100 % endl; } else { cout Fail to compress. endl; } break; case 2: cout Please enter the name of the file you want to uncompress: endl; cin input_filename; //拓展名和自定义拓展名不同的文件不能解压 if(input_filename.substr(input_filename.find_last_of(.)1) ! std_extension){ cout This kind of file can not be uncompressed! endl; break; } //输入要解压文件的格式 cout Please enter the extension of the output file: endl; cin ex; output_filename change_extension(input_filename,ex); //解压过程 //汇报解压信息 if(uncompress(input_filename,output_filename)){ cout Uncompress successfully! endl; cout Size of input file: get_filesize(input_filename) endl; cout Size of output file: get_filesize(output_filename) endl; } else { cout Fail to uncompress. endl; } break; case 0: break; default: cout Invalid choice! Please try again. endl; } input_filename.clear(); output_filename.clear(); cout endl; } while (select); cout Exit successfully! endl; system(pause); return 0; }用户可以选择压缩或解压缩文件或退出系统压缩文件的格式都统一为自定义的格式系统默认无法识别防止文件被错误打开使用分界使程序界面整洁美观汇报压缩解压信息和压缩比率使用户对压缩情况一目了然Huffman.cpp该文件包含各个函数的实现全部贴出过于冗长请自行查看代码其中包含了注释。下面压缩过程和解压过程bool uncompress(const string encoded_filename, const string source_filename){ ifstream in(encoded_filename.c_str(), ios::in | ios::binary); if(!in.is_open()){ cout Fail to open the encoded file! endl; return false; } ofstream out(source_filename.c_str(), ios::out | ios::binary); if(!out.is_open()){ cout Fail to open the output file! endl; return false; } size_t sizes 0; in.read((char *)sizes, 8); //首先从压缩文件的其实字符串得到文件的解码词典 之后便可根据解码词典进行解码 int dictionary_size 0; unsigned char temp; in.read((char *)temp, 1);//解码字典的长度 //编码词典最多256个字符由于unsigned char的表示范围为0~255因此当解码词典个数为256时temp0 dictionary_size temp ? (int)temp : 256; mapstring, char decode_dictionary; char ch; unsigned char buf; unsigned char len; string huffman_code; unsigned char buf_index; unsigned char i; //table数组 从LSB到MSB依次为1其他位为0用于往缓冲区buf逐位写入信息时的位选 unsigned char table[8] {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; for (int j 0; j dictionary_size;j){ buf 0; buf_index 0; in.read((char *)ch, 1); //读入解码字典的字符 in.read((char *)len, 1); //读入当前字符编码的编码长度 in.read((char *)buf, 1); huffman_code ; //根据长度读出后续的编码01串 for ( i 0; i len; i) { if(buftable[buf_index]) huffman_code 1; else huffman_code 0; buf_index; if(buf_index8){ buf_index 0; //若ilen-1表示刚好处理完缓冲区的字符若没处理完则继续读入 if(i!len-1) in.read((char *)buf, 1); } } //将获得的字符对应的编码插入解码器 decode_dictionary.insert(mapstring, char::value_type(huffman_code, ch)); } //根据获得的解码器对文件进行解码 mapstring,char::iterator it; buf_index 0; huffman_code ; //二进制读入压缩文件中的一个字符 in.read((char *)buf, 1); // 若文件没有结束则按照二进制一个字符一个字符的读入所有内容 while(!in.eof()){ if(buftable[buf_index]) huffman_code 1; else huffman_code 0; buf_index; //前缀编码中根据编码找到对应的字符将字符写入解压文件 it decode_dictionary.find(huffman_code); if(it!decode_dictionary.end()){ ch it-second; out.write((char *)ch, 1); --sizes; if(sizes0){ in.close(); in.clear(); out.close(); out.clear(); return true; } huffman_code ; } //读入的字符处理完毕继续读入一个字符 if(buf_index8){ buf_index 0; in.read((char *)buf, 1); } } }压缩共打开两次输入文件一次用于统计字符出现频率和文件长度一次用于编码写入压缩文件若原始文件或压缩文件打卡失败时报错用 table 数组作为缓冲区的位选压缩后文件中的数据存储顺序为原始文件长度 sizes| 解码词典元素个数 n| 第 1 个字符键值 | 第 1 个字符对应的 Huffman 编码长度 | 第 1 个字符的 Huffman 编码的存储区 | 第 2 个字符键值 | 第 2 个字符对应的 Huffman 编码长度 | 第 2 个字符的 Huffman 编码的存储区 |···| 第 n 个字符键值 | 第 n 个字符对应的 Huffman 编码长度 | 第 n 个字符的 Huffman 编码的存储区 | 原始文件的 Huffman 编码 | 原始文件的 Huffman 编码长度不是 8 的倍数时补 0解压打开压缩文件读取原始文件长度读取解码词典元素个数再根据解码词典元素个数读取解码词典内容依次读取字符键值、字符对应 Huffman 编码长度再根据字符对应 Huffman 编码长度在字符的 Huffman 编码的存储区读取字符对应的 Huffman 编码读取完毕时即构建好了解码词典根据解码词典对原始文件的 Huffman 编码进行译码写入输出文件中。其中输出文件被保存成了指定的格式。解码完毕实现无损解压。实验结果下面展示压缩 txt文本、jpg图片格式文件的压缩和解压其他格式文件同理。文件信息压缩文件解压文件test.txt解压后解压文件和原始文件大小相同内容相同符合预期效果。test.jpg文件信息压缩解压后test.jpg解压后解压文件和原始文件大小相同内容相同符合预期效果。反思该程序在压缩字符出现频率较多且类型较少的文件时压缩效果较好压缩比率较低如以上压缩 txt 文件的例子但在压缩字符种类较多的文件时压缩效果一般如以上压缩 jpg 格式的文件的例子。此外当压缩较小的文件时压缩效果不佳因为需要往压缩文件写入解压信息原始文件长度、解码词典需要占据一定的空间当 Huffman 算法对该文件带来的优化效果不能抵消附加解压信息带来的负面效果时压缩是没有意义的甚至会出现压缩文件大于原始文件的情况这些是我认为值得注意的问题。实验心得通过这次实验我理解和掌握了 Huffman 树和 Huffman 算法明白了 Huffman 算法用于压缩文件的原理。学会了如何构造一颗 Huffman 树明白了何为前缀码前缀码的特点和应用理解了文件在系统中的存储形式和文件拓展名的作用此次实验使我受益匪浅。