c++怎么实现哈夫曼树编码压缩_c++ 字符频率统计与变长编码【案例】

哈夫曼压缩核心是按频率构建最小堆二叉树并生成唯一变长编码：需以unsigned char统计0–255字节频次，自定义priority_queue升序比较器，合并时权重小者为左子树（编0），大者为右（编1），空文件或单字符需特判；编码表须按“字符+长度+对齐比特”二进制格式写入头部，并校验编码唯一性。

怎么用 C++ 构建哈夫曼树并生成变长编码

核心是：先统计字符频率，再用优先队列（最小堆）构建带权路径最短的二叉树，最后递归/迭代生成每个字符的编码。关键不在“写树”，而在「保证构建过程严格按权重合并」和「编码方向不能反」。

常见错误是把左子树当 1、右子树当 0（或反之），导致解码失败；或者没处理单字符输入（比如文件只含一个 'a'），堆里只剩一个节点时直接崩溃。

• 用 std::priority_queue 时必须自定义比较器，让它按 freq 升序——默认是大顶堆，得翻过来
• 树节点建议用结构体而非类，避免虚函数开销；叶子节点需存原始字符（char 或 int），内部节点设为 -1 或 0 标记
• 编码生成推荐 DFS 递归：进左子树拼 "0"，进右子树拼 "1"；别用 BFS，容易乱序且难回溯路径

struct Node {
    int freq;
    char ch;
    Node* left;
    Node* right;
    Node(int f, char c) : freq(f), ch(c), left(nullptr), right(nullptr) {}
};
struct Compare {
    bool operator()(Node* a, Node* b) { return a->freq > b->freq; }
};
// 构建过程节选
std::priority_queue, Compare> pq;
// ... 插入所有叶子节点
while (pq.size() > 1) {
    Node* l = pq.top(); pq.pop();
    Node* r = pq.top(); pq.pop();
    Node* merged = new Node(l->freq + r->freq, '\0');
    merged->left = l;
    merged->right = r;
    pq.push(merged);
}

字符频率统计要注意哪些边界情况

不能简单用 std::map 然后 fstream.get() 逐字节读——遇到空字符 '\0'、换行符 '\n'、高位字节（如 UTF-8 中文）会截断或误判。实际压缩对象是字节流，不是“字符流”。

• 必须以 unsigned char 视角读取文件，映射到 int 范围 [0, 255]，用 std::array 统计最稳
• 文件末尾的 EOF 不算有效字节，istream::get() 返回 int，需判断是否等于 EOF 再转 unsigned char
• 若输入为空文件，频率数组全零，后续建树要提前检查 total_count == 0 并跳过压缩

std::array freq{};
std::ifstream fin("input.bin", std::ios::binary);
int byte;
while ((byte = fin.get()) != EOF) {
    freq[static_cast(byte)]++;
}

怎么把编码表高效存进压缩文件头部

不能直接写字符串如 "a:010\nb:11\n"——这本身就在膨胀数据。标准做法是：先写字符（1 字节），再写其编码长度（1 字节），最后写编码比特（按字节对齐，高位在前）。

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

HaiSnap

一站式AI应用开发和部署工具

下载

例如字符 'x' 编码是 "1011"（4 位），就写：0x78（'x' 的 ASCII）、0x04、0xB0（10110000，后 4 位补零凑满 1 字节）。解压时靠长度字段截取有效比特。

• 编码长度超过 8 位？正常，哈夫曼树深度可能达 256，但实际英文文本一般 ≤ 32
• 务必在头部末尾写一个结束标记（如 0xFF），否则解压器无法知道头在哪结束
• 别用 std::string 拼接编码比特——它按字节存，而你需要按位写入，得手写 bit writer 类或用 std::vector（注意它不是容器，别用 data()）

为什么压缩后文件反而变大了

小文件（

• 测试时用 >10 KB 的纯英文文本（如《The Raven》），才能看到 30%~40% 压缩率
• 如果源文件已用 gzip 压过，再套哈夫曼只会更大——熵已经极低，变长编码失去优势
• 真正工程中不会单独用哈夫曼，而是作为 DEFLATE（zip）的后端；自己实现时，至少加一层游程编码预处理，对付重复字节

最容易被忽略的是：没做「编码唯一性校验」。两个不同字符生成相同编码（比如都成了 "0"），整个压缩就不可逆。构建完树必须遍历所有叶子，确认无重复编码串——哪怕只是调试时用 std::set<:string> 临时塞一遍。