编写基于C++ Huffman 算法的无损压缩程序和解压程序-尧图网络科技

♻️ 资源

大小：2.92MB

➡️资源下载：https://download.csdn.net/download/s1t16/87450324

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

实验目的

编写基于 Huffman 算法的压缩和解压缩程序。你的程序应该能够压缩任意文件，并能无损解压。

实验环境

本实验可基于 Visual Studio Code 等平台开发，参考主流的编码规范，如 Google C++Style 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, map<char, size_t> &char_weight); //跟据字符到频率的映射构建半哈夫曼树，返回树的根节点,此时哈夫曼树未编码 tree_node* built_tree(map<char, size_t> &char_weight); //销毁树，懂得都懂 void destroy_tree(tree_node *); //根据半哈夫曼树（节点未编码）得到完整的哈夫曼树 （在结点处得到字符到它对应的哈夫曼编码和映射 void encoder(tree_node *root, map<char, 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时temp=0 dictionary_size = temp ? (int)temp : 256; map<string, 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(buf&table[buf_index]) huffman_code += "1"; else huffman_code += "0"; buf_index++; if(buf_index==8){ buf_index = 0; //若i=len-1表示刚好处理完缓冲区的字符，若没处理完则继续读入 if(i!=len-1) in.read((char *)&buf, 1); } } //将获得的字符对应的编码插入解码器 decode_dictionary.insert(map<string, char>::value_type(huffman_code, ch)); } //根据获得的解码器对文件进行解码 map<string,char>::iterator it; buf_index = 0; huffman_code = ""; //二进制读入压缩文件中的一个字符 in.read((char *)&buf, 1); // 若文件没有结束则按照二进制一个字符一个字符的读入所有内容 while(!in.eof()){ if(buf&table[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(sizes==0){ in.close(); in.clear(); out.close(); out.clear(); return true; } huffman_code = ""; } //读入的字符处理完毕，继续读入一个字符 if(buf_index==8){ 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（图片）格式文件的压缩和解压，其他格式文件同理。

文件信息

压缩文件

解压文件