数据压缩技术通过将原始数据转换为占用空间更小的编码形式，能够有效减少存储占用和传输带宽消耗，在文件存储、网络传输等场景中应用非常广泛。在C++中实现压缩算法，需要结合具体的压缩原理设计编码逻辑，同时处理好数据的读写和位操作等细节。
数据压缩的核心分类
常见的数据压缩算法可以分为无损压缩和有损压缩两类，两者的适用场景和实现逻辑有明显区别：
- 无损压缩：压缩后可以完全还原原始数据，不会丢失任何信息，适合文本、程序、归档文件等场景，哈夫曼编码、LZ77都属于这类算法。
- 有损压缩：压缩过程中会丢弃部分人类感知不敏感的信息，压缩比更高，适合音频、视频、图像等场景，比如常见的JPEG、MP3格式就采用了有损压缩。
哈夫曼编码的实现原理
哈夫曼编码是最经典的无损压缩算法之一，核心思想是为出现频率高的字符分配更短的编码，为出现频率低的字符分配更长的编码，从而降低整体的编码长度。实现步骤主要分为三步：
1. 统计字符频率
首先遍历原始数据，统计每个字符出现的次数，作为后续构建哈夫曼树的权重依据。
2. 构建哈夫曼树
将所有字符作为叶子节点，每次选取权重最小的两个节点合并为一个新的父节点，父节点的权重为两个子节点权重之和，重复这个过程直到只剩下一个根节点，就得到了哈夫曼树。
3. 生成编码并压缩
从根节点出发，向左走标记为0，向右走标记为1，到达叶子节点时的路径就是对应字符的哈夫曼编码，最后用生成的编码替换原始字符完成压缩。
C++实现哈夫曼压缩的完整示例
下面是哈夫曼编码压缩的完整C++实现代码，包含频率统计、哈夫曼树构建、编码生成和压缩逻辑：
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>
#include <bitset>
// 哈夫曼树节点定义
struct HuffmanNode {
char data; // 字符
int freq; // 出现频率
HuffmanNode* left; // 左子节点
HuffmanNode* right; // 右子节点
HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};
// 用于优先队列的比较函数，频率小的节点优先级更高
struct CompareNode {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->freq > b->freq;
}
};
// 统计字符频率
std::unordered_map<char, int> countFrequency(const std::string& data) {
std::unordered_map<char, int> freqMap;
for (char c : data) {
freqMap[c]++;
}
return freqMap;
}
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const std::unordered_map<char, int>& freqMap) {
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNode> pq;
// 将所有字符节点加入优先队列
for (auto& pair : freqMap) {
pq.push(new HuffmanNode(pair.first, pair.second));
}
// 合并节点直到只剩根节点
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
// 创建父节点，字符设为空，频率为两个子节点之和
HuffmanNode* parent = new HuffmanNode(' ', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 生成哈夫曼编码表
void generateCodes(HuffmanNode* root, const std::string& code, std::unordered_map<char, std::string>& codeMap) {
if (root == nullptr) return;
// 如果是叶子节点，将编码存入映射表
if (root->left == nullptr && root->right == nullptr) {
codeMap[root->data] = code;
return;
}
// 递归遍历左子树，编码加0
generateCodes(root->left, code + "0", codeMap);
// 递归遍历右子树，编码加1
generateCodes(root->right, code + "1", codeMap);
}
// 压缩数据
std::string compressData(const std::string& data, const std::unordered_map<char, std::string>& codeMap) {
std::string compressed;
for (char c : data) {
compressed += codeMap.at(c);
}
return compressed;
}
// 释放哈夫曼树内存
void deleteTree(HuffmanNode* root) {
if (root == nullptr) return;
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
int main() {
std::string originalData = "this is an example for huffman encoding";
std::cout << "原始数据: " << originalData << std::endl;
std::cout << "原始数据长度: " << originalData.size() << " 字节" << std::endl;
// 统计频率
auto freqMap = countFrequency(originalData);
// 构建哈夫曼树
HuffmanNode* root = buildHuffmanTree(freqMap);
// 生成编码表
std::unordered_map<char, std::string> codeMap;
generateCodes(root, "", codeMap);
// 输出编码表
std::cout << "n哈夫曼编码表:" << std::endl;
for (auto& pair : codeMap) {
std::cout << "'" << pair.first << "': " << pair.second << std::endl;
}
// 压缩数据
std::string compressed = compressData(originalData, codeMap);
std::cout << "n压缩后的二进制数据: " << compressed << std::endl;
std::cout << "压缩后二进制长度: " << compressed.size() << " 位" << std::endl;
// 计算压缩比，1字节=8位
double compressionRatio = (double)compressed.size() / (originalData.size() * 8) * 100;
std::cout << "压缩比: " << compressionRatio << "%" << std::endl;
// 释放内存
deleteTree(root);
return 0;
}
实现压缩算法的注意事项
在实际开发中实现压缩算法时，还需要注意以下几个问题：
- 位操作处理：压缩后的数据是二进制位流，需要用位运算来处理字节的读写，不能直接按字符存储，否则会导致编码错误。
- 编码表存储：解压时需要用到和压缩时相同的编码表，因此压缩文件中需要额外存储编码表信息，或者提前约定固定的编码规则。
- 大文件处理：处理大文件时不能一次性将所有数据读入内存，需要采用流式读写的方式，分块处理数据。
哈夫曼编码是比较基础的压缩算法，实际工业级压缩工具还会结合其他算法优化压缩效果，比如先用LZ77算法做重复序列替换，再用哈夫曼编码做进一步压缩，这也是DEFLATE算法的核心思路。