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

# 编写基于 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)