答案是使用C++实现哈夫曼编码压缩工具，通过统计字节频率构建最小堆哈夫曼树，生成变长编码并逐位写入比特流，同时保存频率表用于解压，最终实现文件压缩与解压，压缩率可达30%-50%，适用于理解无损压缩核心原理。
文件压缩在现代软件开发中非常常见，C++作为高性能语言，非常适合实现压缩工具。本文带你用C++实现一个简易但完整的文件压缩工具，采用哈夫曼编码这一经典无损压缩算法，解析其核心原理与代码实现。
哈夫曼压缩原理简述
哈夫曼编码是一种基于字符出现频率的变长编码方式，出现频率高的字符用短编码，频率低的用长编码，从而减少整体存储空间。
实现步骤包括：
- 统计文件中每个字节的出现频率
- 构建哈夫曼树（优先队列实现最小堆）
- 生成每个字节对应的二进制编码
- 将原始文件内容替换为编码后的比特流
- 保存编码表和压缩数据到输出文件
核心数据结构与编码实现
定义哈夫曼树节点：
立即学习“C++免费学习笔记（深入）”；
struct Node {
uint8_t byte;
int freq;
Node *left, *right;
<pre class='brush:php;toolbar:false;'>Node(uint8_t b, int f) : byte(b), freq(f), left(nullptr), right(nullptr) {}};
使用优先队列构建哈夫曼树：
auto cmp = [](Node* a, Node* b) { return a->freq > b->freq; };
std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> pq(cmp);
<p>// 统计频率后，将每个字节作为叶子节点入队
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
pq.push(new Node(static_cast<uint8_t>(i), freq[i]));
}
}</p><p>// 构建树
while (pq.size() > 1) {
Node <em>left = pq.top(); pq.pop();
Node </em>right = pq.top(); pq.pop();
Node *parent = new Node(0, left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}</p>递归生成编码表：
void buildCode(std::string code, Node* node, std::string codes[256]) {
if (!node) return;
if (!node->left && !node->right) {
codes[node->byte] = code.empty() ? "0" : code;
}
buildCode(code + "0", node->left, codes);
buildCode(code + "1", node->right, codes);
}
压缩与解压文件操作
压缩时，将编码写入比特流。由于文件以字节为单位存储，需手动处理比特拼接：
- 使用一个缓存字节和位计数器
- 逐位写入编码，满8位写入文件
- 压缩头信息中保存编码表（字节+频率）用于解压
示例写入比特：
uint8_t buffer = 0;
int bitCount = 0;
<p>void writeBit(std::ofstream& out, int bit) {
buffer |= (bit << (7 - bitCount));
bitCount++;
if (bitCount == 8) {
out.write(reinterpret_cast<char*>(&buffer), 1);
buffer = 0;
bitCount = 0;
}
}</p>解压时从哈夫曼树根节点开始，读每一位，0向左，1向右，到达叶子节点输出字节，再从根重新开始。
使用示例与效果
调用方式简单：
compress("input.txt", "output.bin");
decompress("output.bin", "restored.txt");
对文本文件压缩率通常可达30%-50%，二进制文件效果取决于数据分布。虽然不如zlib等库高效，但有助于理解压缩本质。
基本上就这些。掌握哈夫曼编码的实现，为进一步学习LZ77、DEFLATE等复杂算法打下基础。整个过程不复杂但容易忽略细节，比如比特对齐和文件头设计。
