在C++实现Huffman编码压缩时，如何将编码以二进制存储而非字符串？

你当前用字符串存储Huffman编码的方式会导致编码体积膨胀（每个二进制位占1个字节），完全失去压缩意义。要实现真正的二进制存储，需要通过位操作直接将编码写入字节流，具体步骤如下：

1. 重构编码存储结构 #

把原来的unordered_map<char, string>替换为存储编码值和编码长度的映射——因为变长编码需要明确记录每个字符的编码位数：

// key: 目标字符, value: 第一个元素是编码的二进制数值，第二个是编码的总位数
unordered_map<char, pair<uint64_t, int>> encoding;

2. 修改编码生成函数 #

不再用字符串拼接构建编码，而是通过位运算直接生成二进制编码值，同时跟踪编码长度：

void store_huffman_codes(Node* root, uint64_t code, int length) {
    if (root == nullptr) return;
    // 叶子节点，记录当前字符的编码值和长度
    if (root->val != '$') {
        encoding[root->val] = {code, length};
        return;
    }
    // 左子树：编码左移1位后补0，长度+1
    store_huffman_codes(root->left, (code << 1) | 0, length + 1);
    // 右子树：编码左移1位后补1，长度+1
    store_huffman_codes(root->right, (code << 1) | 1, length + 1);
}

调用时传入初始参数：

store_huffman_codes(root, 0, 0);

3. 二进制流输出实现 #

用一个字节缓冲区累积二进制位，每满8位就写入文件；最后处理剩余的不足8位的部分（需记录剩余有效位数，方便解压时识别）：

// 打开二进制输出文件
ofstream out_file("compressed.bin", ios::binary);
if (!out_file) {
    cerr << "无法打开输出文件" << endl;
    return;
}

// 先写入编码映射（必须保存，否则解压时无法还原字符）
// 示例逻辑：先写字符种类数，再逐个写入字符、编码长度、编码值
size_t char_count = m.size();
out_file.write(reinterpret_cast<const char*>(&char_count), sizeof(size_t));
for (const auto& entry : encoding) {
    char c = entry.first;
    int code_len = entry.second.second;
    uint64_t code_val = entry.second.first;
    out_file.write(&c, sizeof(char));
    out_file.write(reinterpret_cast<const char*>(&code_len), sizeof(int));
    out_file.write(reinterpret_cast<const char*>(&code_val), sizeof(uint64_t));
}

uint8_t buffer = 0; // 8位缓冲区，用于累积二进制位
int bit_count = 0;  // 当前缓冲区已填充的位数

for (char c : test) {
    auto& code_info = encoding[c];
    uint64_t code_val = code_info.first;
    int code_len = code_info.second;

    // 将编码逐位填充到缓冲区
    for (int i = code_len - 1; i >= 0; --i) {
        buffer <<= 1;
        if (code_val & (1ULL << i)) {
            buffer |= 1;
        }
        bit_count++;

        // 缓冲区满8位，写入文件
        if (bit_count == 8) {
            out_file.write(reinterpret_cast<const char*>(&buffer), sizeof(uint8_t));
            buffer = 0;
            bit_count = 0;
        }
    }
}

// 处理剩余的不足8位的部分
if (bit_count > 0) {
    // 左移补0填满8位，写入文件
    buffer <<= (8 - bit_count);
    out_file.write(reinterpret_cast<const char*>(&buffer), sizeof(uint8_t));
    // 记录剩余有效位数，建议写入文件开头或末尾
    out_file.write(reinterpret_cast<const char*>(&bit_count), sizeof(int));
}

out_file.close();

关键注意事项 #

• 必须保存**Huffman编码映射（或树结构）**到压缩文件中，否则解压时无法将二进制流还原为原字符。
• 最后剩余的不足8位部分，要记录实际有效位数，解压时才能正确截断补位的无效0。
• 务必使用ios::binary模式打开文件，避免系统自动转换换行符等特殊字符破坏二进制流。

内容的提问来源于stack exchange，提问作者Falcon