C++实现文件压缩工具 基本压缩算法实践解析

答案是使用C++实现哈夫曼编码压缩工具，通过统计字节频率构建最小堆哈夫曼树，生成变长编码并逐位写入比特流，同时保存频率表用于解压，最终实现文件压缩与解压，压缩率可达30%-50%，适用于理解无损压缩核心原理。

文件压缩在现代软件开发中非常常见，C++作为高性能语言，非常适合实现压缩工具。本文带你用C++实现一个简易但完整的文件压缩工具，采用哈夫曼编码这一经典无损压缩算法，解析其核心原理与代码实现。

哈夫曼压缩原理简述

哈夫曼编码是一种基于字符出现频率的变长编码方式，出现频率高的字符用短编码，频率低的用长编码，从而减少整体存储空间。

实现步骤包括：

• 统计文件中每个字节的出现频率
• 构建哈夫曼树（优先队列实现最小堆）
• 生成每个字节对应的二进制编码
• 将原始文件内容替换为编码后的比特流
• 保存编码表和压缩数据到输出文件

核心数据结构与编码实现

定义哈夫曼树节点：

立即学习“C++免费学习笔记（深入）”；

struct Node {
    uint8_t byte;
    int freq;
    Node *left, *right;
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, decltype(cmp)> pq(cmp);
// 统计频率后，将每个字节作为叶子节点入队
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
pq.push(new Node(static_cast(i), freq[i]));
}
}
// 构建树
while (pq.size() > 1) {
Node left = pq.top(); pq.pop();
Node right = pq.top(); pq.pop();
Node *parent = new Node(0, left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
递归生成编码表：

							

								
								

									Lessie AI
									
一款定位为「People Search AI Agent」的AI搜索智能体
								
								下载 
							
						
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;
void writeBit(std::ofstream& out, int bit) {
buffer |= (bit << (7 - bitCount));
bitCount++;
if (bitCount == 8) {
out.write(reinterpret_cast(&buffer), 1);
buffer = 0;
bitCount = 0;
}
}
解压时从哈夫曼树根节点开始，读每一位，0向左，1向右，到达叶子节点输出字节，再从根重新开始。
使用示例与效果
调用方式简单：
compress("input.txt", "output.bin");
decompress("output.bin", "restored.txt");
对文本文件压缩率通常可达30%-50%，二进制文件效果取决于数据分布。虽然不如zlib等库高效，但有助于理解压缩本质。
基本上就这些。掌握哈夫曼编码的实现，为进一步学习LZ77、DEFLATE等复杂算法打下基础。整个过程不复杂但容易忽略细节，比如比特对齐和文件头设计。