获得Huffman编码后，如何实现.txt文件的实际压缩？

现有实现代码 #

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

struct Node
{
  char ch;
  int freq;
  Node *left;
  Node *right;
  Node(char ch, int freq)
      : ch(ch), freq(freq), left(nullptr), right(nullptr)
  {
  }
  Node(char ch, int freq, Node *left, Node *right)
      : ch(ch), freq(freq), left(left), right(right)
  {
  }
};

struct compare
{
  bool operator()(Node *l, Node *r)
  {
    return l->freq > r->freq;
  }
};

void obtainHuffmanCode(Node *root, string str,
                       unordered_map<char, string> &huffmanCode)
{
  if (root == nullptr)
    return;
  if (!root->left && !root->right)
  {
    huffmanCode[root->ch] = str;
  }

  obtainHuffmanCode(root->left, str + "0", huffmanCode);
  obtainHuffmanCode(root->right, str + "1", huffmanCode);
}

unordered_map<char, string> buildHuffmanTreeNaive(unordered_map<char, int> freq)
{

  priority_queue<Node *, vector<Node *>, compare> pq;
  for (auto pair : freq)
  {
    pq.push(new Node(pair.first, pair.second));
  }
  while (pq.size() != 1)
  {
    Node *left = pq.top();
    pq.pop();
    Node *right = pq.top();
    pq.pop();
    int sum = left->freq + right->freq;
    pq.push(new Node('\0', sum, left, right));
  }
  Node *root = pq.top();

  unordered_map<char, string> huffmanCode;
  obtainHuffmanCode(root, "", huffmanCode);

  return huffmanCode;
}

string encode(string txt, unordered_map<char, string> huffmanCode)
{
  string str = "";
  for (char ch : txt)
  {
    str += huffmanCode[ch];
  }
  return str;
}

技术疑问解答 #

1. 压缩过程中需要哪些元数据？应输出另一个.txt文件还是以对象形式存储二进制数据？ #

• 必需元数据：
  • Huffman编码映射表：记录每个字符对应的二进制编码，是解压时还原原始数据的核心依据。
  • 原始编码总有效比特数：将编码字符串转为二进制文件时，最后一个字节通常会补0凑成完整字节，这个数值用来标记解压时需要读取的有效比特数量，避免把填充的0当成有效数据。
  • （可选）字符频率表：如果不想直接存储编码表，也可以存储频率表，解压时重新构建Huffman树生成编码，但存储编码表能减少解压时的计算量，提升效率。
• 存储方式：绝对不能用.txt文件存储压缩结果。.txt是文本格式，会将二进制数据转换为ASCII字符存储，不仅会大幅增加文件体积，还可能丢失二进制信息。必须使用二进制文件存储，可将元数据与压缩后的二进制流放在同一个文件中，比如按「元数据长度 → 元数据 → 总有效比特数 → 压缩二进制流」的顺序写入，方便解压时读取解析。

2. 当前字符的Huffman编码以字符串形式生成，如何获取实际二进制值并保留前导0（例如编码001）？ #

不能直接将编码字符串转为整数（比如用stoi），因为整数会自动丢弃前导0，且编码长度可能超过普通整数的比特范围。正确的做法是逐位拼接成字节写入二进制文件，步骤如下：

1. 定义临时变量：unsigned char current_byte = 0（存储正在构建的字节），int bit_count = 0（记录当前已填充的比特数）。
2. 遍历编码字符串的每一位字符：
   • 将current_byte左移1位，腾出最低位。
   • 如果当前位是'1'，则给current_byte的最低位赋值1；如果是'0'则保持0。
   • bit_count加1，当bit_count达到8时，将current_byte写入二进制文件，然后重置current_byte为0，bit_count为0。
3. 遍历结束后，如果bit_count不为0，说明还有未填满一个字节的剩余比特，将current_byte左移(8 - bit_count)位补0，然后写入文件，同时记录下总有效比特数（即编码字符串的总长度）。

• 示例：编码字符串为"001"，总有效比特数是3。处理时：
  • 第一位'0'：current_byte左移1位为0，补0后还是0，bit_count=1。
  • 第二位'0'：current_byte左移1位为0，补0后还是0，bit_count=2。
  • 第三位'1'：current_byte左移1位为0，补1后变为1，bit_count=3。
  • 此时bit_count<8，将current_byte左移5位（8-3）得到0b00001000，写入文件。解压时根据总有效比特数3，只取该字节的最后3位（001）即可还原原始编码。

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