28、C++项目实战：哈夫曼编码压缩工具

哈夫曼编码，说白了就是给数据里的每个字符重新分配一套「可变长度」的二进制编号。出现频率高的字符，编号短一点；出现频率低的，编号长一点。这样整体算下来，数据体积就变小了。

我记得刚入行那会儿，第一次接触这个算法是在一个嵌入式项目里。那时候存储空间金贵得很，一个字节都恨不得掰成两半用。哈夫曼编码帮我省下了将近40%的空间，老板当场就给我加了鸡腿——嗯，虽然只是口头上的。

今天我们就手撸一个完整的哈夫曼压缩工具。我会把每个环节拆开讲，包括你可能会踩的坑。

核心原理：一棵树搞定一切

哈夫曼编码的核心，是一棵二叉树。这棵树叫「哈夫曼树」，也叫最优二叉树。它的构造过程其实不复杂：

1. 统计每个字符出现的次数（权重）
2. 把每个字符当成一个叶子节点
3. 每次挑两个权重最小的节点，合并成一个父节点
4. 重复第三步，直到只剩一个节点——那就是根节点

从根节点走到叶子节点，向左走是0，向右走是1。这条路径上的0和1串起来，就是该字符的哈夫曼编码。

我曾经在项目里吃过这个亏。当时图省事，自己拍脑袋设计了一套变长编码，结果解码时经常对不上。后来老老实实用了哈夫曼树，问题瞬间解决。

整体架构设计

这个工具我打算分成三个模块：

• 统计模块：读文件，统计每个字节的出现频率
• 编码模块：构建哈夫曼树，生成编码表，压缩数据
• 解码模块：读取压缩数据，还原原始文件

下面这张图可以帮你快速理解整个流程：

数据结构定义

先定义几个核心结构。我个人习惯把哈夫曼树的节点和编码表分开定义，这样逻辑更清晰。

// 哈夫曼树节点
struct HuffmanNode {
    unsigned char data;      // 字符
    int freq;                // 频率
    HuffmanNode* left;
    HuffmanNode* right;
    
    HuffmanNode(unsigned char d, int f) 
        : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 编码表：字符 -> 二进制编码
struct HuffmanCode {
    unsigned char data;
    std::string code;        // 比如 "101"
};

// 比较器，用于优先队列（最小堆）
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

构建哈夫曼树

构建过程其实就三步：建堆、合并、取根。代码写出来很简洁：

HuffmanNode* buildHuffmanTree(const std::map<unsigned char, int>& freqMap) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> 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();
        
        // 合并后的父节点，频率相加，data随便填
        HuffmanNode* parent = new HuffmanNode(0, left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        
        pq.push(parent);
    }
    
    // 第三步：堆里只剩一个节点，就是根节点
    return pq.top();
}

这里有个细节要注意。合并时父节点的data字段其实用不上，但为了统一管理，我习惯给它赋个0。你想想看，反正解码时只用到叶子节点的data，父节点是什么值无所谓。

生成编码表

有了哈夫曼树，生成编码表就是一次深度优先遍历。向左走加'0'，向右走加'1'：

void generateCodes(HuffmanNode* root, std::string code, 
                   std::map<unsigned char, std::string>& codeMap) {
    if (!root) return;
    
    // 叶子节点：记录编码
    if (!root->left && !root->right) {
        codeMap[root->data] = code;
        return;
    }
    
    generateCodes(root->left, code + "0", codeMap);
    generateCodes(root->right, code + "1", codeMap);
}

压缩与解压

压缩时，我们把原始文件的每个字节替换成对应的哈夫曼编码。但这里有个问题：编码是变长的，最后可能凑不满一个字节。我的做法是补0，并在文件头记录有效位数。

// 压缩核心逻辑
std::vector<unsigned char> compress(const std::vector<unsigned char>& data,
                                     const std::map<unsigned char, std::string>& codeMap) {
    std::string bitStream;
    for (unsigned char c : data) {
        bitStream += codeMap.at(c);
    }
    
    // 补0到8的倍数
    int padding = 8 - (bitStream.size() % 8);
    if (padding != 8) {
        bitStream.append(padding, '0');
    } else {
        padding = 0;
    }
    
    // 每8位转成一个字节
    std::vector<unsigned char> result;
    result.push_back(static_cast<unsigned char>(padding)); // 记录补位数
    
    for (size_t i = 0; i < bitStream.size(); i += 8) {
        unsigned char byte = 0;
        for (int j = 0; j < 8; ++j) {
            if (bitStream[i + j] == '1') {
                byte |= (1 << (7 - j));
            }
        }
        result.push_back(byte);
    }
    
    return result;
}

解压时反过来。先读补位数，然后把每个字节拆成8位，最后根据哈夫曼树从根节点开始走，遇到叶子就输出字符：

std::vector<unsigned char> decompress(const std::vector<unsigned char>& compressed,
                                       HuffmanNode* root) {
    int padding = compressed[0];
    std::string bitStream;
    
    // 把字节转成二进制串
    for (size_t i = 1; i < compressed.size(); ++i) {
        for (int j = 7; j >= 0; --j) {
            bitStream += (compressed[i] >> j) & 1 ? '1' : '0';
        }
    }
    
    // 去掉补的0
    if (padding > 0) {
        bitStream = bitStream.substr(0, bitStream.size() - padding);
    }
    
    // 遍历哈夫曼树解码
    std::vector<unsigned char> result;
    HuffmanNode* current = root;
    for (char bit : bitStream) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
        
        if (!current->left && !current->right) {
            result.push_back(current->data);
            current = root;
        }
    }
    
    return result;
}

文件格式设计

压缩后的文件需要包含频率表，否则解压时没法重建哈夫曼树。我设计了一个简单的文件头：

字段	大小	说明
魔数	2字节	固定为0x484D（"HM"）
字符种类数	2字节	频率表中包含多少种字符
频率表	变长	每个字符1字节 + 频率4字节
补位数	1字节	最后一个字节补了多少个0
压缩数据	变长	哈夫曼编码后的字节流

性能优化建议

这个工具虽然能跑，但还有不少优化空间。我列几个方向供你参考：

• 内存管理：哈夫曼树节点用new分配，记得写析构函数释放。或者直接用智能指针
• 位操作优化：压缩时频繁拼接字符串效率低，可以改用std::bitset或直接操作字节
• 多线程：大文件可以分块压缩，每个块独立构建哈夫曼树
• 自适应编码：对于流式数据，可以动态更新频率表，不需要先统计完整文件

嗯，说到多线程，我记得有一次优化一个视频文件的压缩模块。单线程跑了3分钟，改成4线程后只用了50秒。不过要注意，分块压缩的压缩率会略低于整体压缩，因为每个块都有自己的频率表。

总结

哈夫曼编码压缩工具，说白了就是「统计频率 → 建树 → 编码 → 存储」这四个步骤。代码量不大，但涉及的知识点挺多：二叉树、优先队列、位运算、文件I/O。做完这个项目，你对C++的数据结构和文件操作会有更深的理解。

如果你在实际编码中遇到问题，比如解压出来的文件乱码了，先检查频率表是否保存正确，再检查补位数有没有算错。这两个地方是bug的高发区。

---

公众号:蓝海资料掘金营，微信deep3321