【项目】基于 Huffman 算法实现文件压缩

摘要：记录通过学习Huffman算法自主实现简单的文件压缩程序的过程。

什么是文件压缩

在古诗词中，这种信息的高度浓缩体现得淋漓尽致。例如王维的《使至塞上》中的名句 “ 大漠孤烟直，长河落日圆 ”。仅仅十个字，却描绘出了一幅极为宏大且细致的画面。它不仅包含了丰富的视觉信息，还营造出了一种苍茫、孤寂而又壮丽的意境。

从这些诗词中我们可以发现，诗词就像一个神奇的 “压缩包”，能够把大量的信息、复杂的画面以及深刻的情感压缩在简短的文字之中。而在计算机领域中，文件压缩的概念与之类似。文件压缩就是把文件中的数据看作是丰富的信息源，通过特定的算法，就如同诗人遣词造句的技巧一般，去除其中的冗余信息，对数据进行重新编码和组织。例如一个包含大量重复数据或者可以用更简洁方式表示的数据文件，经过压缩算法处理后，能够在不丢失关键信息的情况下，使文件的体积大大减小。这就像诗人把一幅复杂的画面和细腻的情感压缩成几句诗词一样，让文件在存储和传输过程中更加高效、便捷。

文件压缩的本质是去除文件中的冗余信息以及对数据编码进行优化。

压缩的基本原理

去除冗余信息

重复数据消除：许多文件中存在大量重复出现的数据。例如，在一个文本文件中，如果多次出现相同的单词或短语，压缩算法会识别这些重复部分，并在存储时只记录一次该重复数据，然后通过标记来表示其在文件中的重复出现位置。

压缩前的数据	djfakjfd777777777qeajivod777777777fkjsdorfjvnvdvfla777777777
压缩过程	重复出现的字段为"777777777"，因此可以用"~"代替该内容
压缩后的数据	djfakjfd~qeajivod~fkjsdorfjvnvdvfla~

（ps.上面表格中所展示的是一个非常简化的例子，只是为了方便理解）

相似数据处理：对于一些相似但不完全相同的数据，如图像文件中颜色相近的像素区域，压缩算法会利用数学模型来找出它们之间的规律，用更简洁的方式表示这些相似数据。

编码优化

霍夫曼（Huffman）编码：这是一种常用的编码方式。它根据字符在文件中出现的频率来分配不同长度的编码。出现频率高的字符被分配较短的编码，而出现频率低的字符则被分配较长的编码。这样可以使文件整体的编码长度更短。例如，在一个特定文件中，字符 “A” 出现的频率非常高，那么它可能被分配一个较短的二进制编码，如 “0”，而其他不常出现的字符则会被分配相对较长的编码。

【详细举例 - Huffman是如何实现优化的】

数据内容：aaaabbbccd
数据所占内存空间大小分析：每个字符占8bit，一共10个字符，即80bit

Huffman编码优化：

首先统计字符的频率：
a 出现了 4 次。
b 出现了 3 次。
c 出现了 2 次。
d 出现了 1 次。

构建哈夫曼树，得到每个字符对应的Huffman编码

分配编码：
d：111
c：110
b：10
a：0

编码结果：
aaaabbbccd 编码为 0000101010110111 👉 16 bit < 80 bit

Huffman 编码如何实现文件压缩

一、Huffman 算法基础

Huffman 树是一种 带权路径长度最短 的二叉树.

👉带权路径：带权路径是指在树结构中从根节点到某一节点的路径长度与该节点权值的乘积。

既然 Huffman 树是一种 带权路径长度最短 的二叉树. 想要带权路径最短就要让权值大的数处在更短的路径上。接下来讲解如何创建 Huffman 🌳

1. 统计字符频率

首先，对需要压缩的文件进行字符统计。例如，对于一个文本文件，统计文件中每个字符出现的次数。假设文件内容是 “ aaaabbbccd ”，那么字符‘a’出现 4 次，‘b’出现 3 次，‘c’出现 2 次，‘d’出现 1 次。
这些频率信息将作为构建 Huffman 树的基础。

2. 构建 Huffman 树

将每个字符及其频率看作一个节点。例如，有节点（a，4）、（b，3）、（c，2）、（d，1）。
从这些节点中选取频率最小的两个节点，创建一个新的父节点，其频率为这两个子节点频率之和。比如先选取（d，1）和（c，2），创建一个新节点（新节点_1，3）。
重复这个过程，直到所有节点都合并成一棵树。接着刚才的例子，再将（新节点_1，3）和（a，4）合并为（新节点_2，7），最后将（新节点_2，7）和（b，3）合并为根节点（根，10）。

二、生成 Huffman 编码

从根节点开始编码

从构建好的 Huffman 树的根节点开始，向左分支标记为 0，向右分支标记为 1（即左1右0，或者相反）。
对于每个叶子节点（即原始字符节点），从根节点到该叶子节点的路径上的 0 和 1 组成的二进制串就是该字符的 Huffman 编码。

⭐Huffman🌳是压缩和解压缩的关键，而围绕Huffman🌳有两个重点。①构建Huffman🌳需要什么；②Huffman🌳可以得到什么
--->即把一个关键转化为两个方面：①字符出现的频次信息；②字符对应的Huffman编码

文件压缩：
读取要压缩的文件 👉 获取构建Huffman树的必要信息 👉 成功构建Huffman树 👉 获取字符对应的Huffman编码 👉 替换字符为编码 👉 存储编码后的文件

文件解压缩：

读取要解压缩的文件 👉 读取构建huffm树的必要信息 👉 成功构建Huffman树 👉 获取字符对应的Huffman编码 👉 替换编码为字符 👉 存储解码后的文件

【class HuffmanTree🌳】

可以看到文件压缩和解压缩的准备动作都和Huffman🌳有关，因此有必要封装一个Huffman的类来实现这些统一的动作。接下来我们将实现一个HuffmanTree类。

首先。老习惯，先来理清框架：

类之间的依赖关系
*class HuffmanTree* 》》----------*depend on---------》》 class HuffmanNode*

class HuffmanNode
Type		Variable Name
待实例化（W）		_weight（权重值）
pointer	->HuffmanNode（指针指向的变量类型）	_pleft
pointer	->HuffmanNode（指针指向的变量类型）	_pright

实现的重点在于 👉 根据给定的数据创建huffman树 👉 实现HuffmanTree的构造函数

构造思路：1. 总是先要选出最小的两个值 → 则把这些数据放在一个小堆中存储，这里用到了优先级队列。
2. 按 Huffman🌳的构造流程一步步实现即可
❓------这里我遇到一个问题：优先级队列中是应该存储指针还是 结点值 呢？（如图）

解决方式：最后还是认为存储指针更方便，对于比较大小的问题，可以用仿函数来控制。

（💡提醒：一开始用了 lambda 表达式 来进行大小比较的控制 👉 priority_queue<pNode, vector<pNode>, lambda 表达式> HuffmanForest 但是，lambda 是一种匿名函数对象！是不能作为一个模板参数的！模板参数只能传递类型！）

示例代码：

#pragma once#include<iostream>
#include<vector>
#include<queue>
using std::vector;
using std::priority_queue;template<class W>
struct HuffmanNode
{HuffmanNode(const W& weight = W()):_weight(weight), _pleft(nullptr), _pright(nullptr){}W _weight;HuffmanNode<W>* _pleft;HuffmanNode<W>* _pright;
};template<class W>
class HuffmanTree
{typedef HuffmanNode<W>* pNode;typedef HuffmanNode<W> Node;struct _greater{bool operator()(pNode left, pNode right){return left->_weight > right->_weight;}};public:HuffmanTree():_proot(nullptr){}HuffmanTree(const vector<W>& DataSource){priority_queue<pNode, vector<pNode>, _greater> HuffmanForest;for (auto e : DataSource){pNode pNewNode = new Node(e);HuffmanForest.push(pNewNode);}while (!HuffmanForest.empty()){pNode pleft = HuffmanForest.top();HuffmanForest.pop();pNode pright = HuffmanForest.top();HuffmanForest.pop();pNode pNewNode = new Node(pleft->_weight + pright->_weight);pNewNode->_pleft = pleft;pleft->_pparent = pNewNode;pNewNode->_pright = pright;pright->_pparent = pNewNode;if (HuffmanForest.empty()){_proot = pNewNode;break;}HuffmanForest.push(pNewNode);}}pNode GetProot(){return _proot;}~HuffmanTree(){Destroy(_proot);}private:void Destroy(pNode& proot){if (proot == nullptr)return;Destroy(proot->_pleft);Destroy(proot->_pright);delete proot;proot = nullptr;}pNode _proot = nullptr;
};

三、文件压缩过程

封装一个类，实现文件压缩和解压缩的方法。

根据上述分析可知，文件压缩要通过Huffman🌳实现，而Huffman🌳构建的关键在于提供的频次频次信息。
👉因此，频次信息就是文件压缩与Huffman🌳之间的桥梁。
👉因此，需要一个存储频次信息的变量。💡频次信息不单单只有频率这么简单：字符 + 出现次数 + 对应Huffman编码 这三项都是围绕Huffman树的重要数据

根据上面的分析，要把 字符 + 出现次数 + 对应Huffman编码 封装起来。

先来理清框架：

类之间的依赖关系
*class FileCompress* 》》----------*depend on---------》》 class DataINFO*

class DataINFO
Type		Variable Name
unsigned char		_ch（字符）
size_t		_frequency（出现频率/次数）
string		_code（对应Huffman编码）

对应代码：

#pragma once
#include"HuffmanTree.h"
#include<string>
using std::string;struct DataINFO
{DataINFO(char ch = 0, size_t frequency = 0, const string& code = ""):_ch(ch), _frequency(frequency), _code(code){}unsigned char _ch;size_t _frequency;string _code;
};class FileCompress
{vector<DataINFO> fileDate;public:FileCompress();void Compress(const string& FilePath); // 对给定的FilePath的文件进行压缩操作，并生成压缩文件void UnCompress(const string& FilePath);// 对给定的FilePath的文件进行解压缩操作，并生成解压缩文件
};

class FileCompress 初始化：

将变量 fileDate 的下标值看成ASCII码值 👉 下标即字符（这也是为什么要用 unsigned char 而不是 char 的原因）。同时，下标对应的位置存储的数据代表该字符的出现次数。

FileCompress::FileCompress()
{fileDate.resize(256);for (size_t i = 0; i < 256; ++i){fileDate[i]._ch = i;}
}

1. 替换字符为编码

对文件中的每个字符，用其对应的 Huffman 编码进行替换。
由于 Huffman 编码是变长编码，而且出现频率高的字符编码较短，所以整体编码后的二进制串长度通常比原始文件的二进制表示长度要短。

2. 存储编码后的文件

将编码后的二进制串存储为压缩文件。同时，为了能够正确解压缩文件，还需要存储 Huffman 树的信息（可以在文件开头或者其他特定位置存储），以便在解压缩时重建 Huffman 树并还原字符编码。

四、解压缩过程

1. 读取 Huffman 树信息

当解压缩文件时，首先读取存储的 Huffman 树信息，重建 Huffman 树。

2. 解码二进制串

从压缩文件中读取编码后的二进制串，从 Huffman 树的根节点开始，根据二进制串中的 0 和 1 沿着树的分支向下走，直到到达叶子节点，叶子节点对应的字符就是解码出的字符。
例如，遇到编码 00，就沿着根节点的左分支再左分支找到叶子节点‘d’，以此类推，将整个二进制串解码还原出原始文件内容。

以上是对Huffman算法的讲解和实现，以及整体框架的搭建和梳理。下篇文章将详细讲解文件压缩和解压缩的过程。

END