仅用priority_queue实现的Huffman编码压缩后文件体积偏大问题求助

问题现象 #

我仅使用queue库中的priority_queue实现了Huffman编码，但压缩后生成的文件体积反而大于原文件：

• 原文件filesize.txt大小为17字节，内容为字符串Stressed-desserts
• 压缩后的compressedfile.bin大小为44字节，存储的是Huffman编码字符串01111011000011110001001100100011110010010111

实现限制：不能使用位操作、unordered_map或map，仅允许使用priority_queue

完整代码如下：

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

struct HuffNode{
    int my_Frequency;
    char my_Char;
    string my_Code;
    HuffNode* my_Left;
    HuffNode* my_Right;
};

//global variables
int freq[256] = {0};
string encoded = "";
string filename;

//Comparing the frequency in the priority queue
struct compare_freq {
    bool operator()(HuffNode* l, HuffNode* r) {
        return l->my_Frequency > r->my_Frequency;
    }
};

priority_queue <HuffNode*, vector<HuffNode*>, compare_freq> freq_queue;

//get the file from user
string get_file_name()
{
    cout << "Input file name to compress: ";
    cin >> filename;
    return filename;
}

//Scan the file to be compressed and tally all the occurence of all characters.
void file_getter()
{
    fstream fp;
    char c;

    fp.open(get_file_name(), ios::in);
    if(!fp)
    {
        cout << "Error: Couldn't open file " << endl;
        system("pause");
    }
    else
    {
        while(!fp.eof())
        {
            c = fp.get();
            freq[c]++;
        }
    }
    fp.close();
}

//HuffNode to create a newNode for queue containing the letter and the frequency
HuffNode* set_Node(char ch, int count)
{
    HuffNode* newNode = new HuffNode;
    newNode->my_Frequency = count;
    newNode->my_Char = ch;
    newNode->my_Code = "";
    newNode->my_Right = nullptr;
    newNode->my_Left = nullptr;
    return newNode;
}

//Sort or Prioritize characters based on numbers of occurences in text.
void insert_Node(char ch, int count)
{
    //pass the ch and count to the newNodes for queing
    freq_queue.push(set_Node(ch, count));
}

void create_Huffman_Tree()
{
    HuffNode* root;
    file_getter();
    
    //insert the characters in the their frequencies into the priority queue
    for(int i = 0; i < 256; i++)
    {
        if(freq[i] > 0)
        {
            insert_Node(char(i), freq[i]);
        }
    }

    //build the huffman tree
    while(freq_queue.size() > 1)
    {
        //get the two highest priority nodes
        HuffNode* for_Left = freq_queue.top();
        freq_queue.pop();
        HuffNode* for_Right = freq_queue.top();
        freq_queue.pop();

        //Create a new HuffNode with the combined frequency of the left and right children
        int freq = for_Left->my_Frequency + for_Right->my_Frequency;
        char ch = '$';
        root = set_Node(ch, freq);
        root->my_Left = for_Left;
        root->my_Right = for_Right;

        //Insert the new node into the priority_queue.
        freq_queue.push(root);
    }

    // The remaining HuffmanNode in the queue is the root of the Huffman tree
    root = freq_queue.top();
}


void preOrderTraverse(HuffNode* root, char c, string code) 
{
    if (root == nullptr) {
        // If the tree is empty, return
        return;
    } 
    if (root->my_Char == c) 
    {
        // If the current HuffmanNode is a leaf HuffmanNode, print the code for the character.
        root->my_Code = code;
        encoded += code;
        return;
    } 
    // Otherwise, recurse on the left and right children
    preOrderTraverse(root->my_Left, c, code + "0");
    preOrderTraverse(root->my_Right, c, code + "1");
}

void encode_File(string ccode)
{
    HuffNode* root = freq_queue.top();
    for(int i = 0; i < ccode.length(); i++)
    {
        char c = ccode[i];
        string code = "";
        preOrderTraverse(root, c, code);
    }
}

void save_Huffman_Code()
{
    fstream fp, fp2;
    fp.open("Compressed_file.bin", ios::out);
    fp2.open(filename, ios::in);
    
    string ccode;
    getline(fp2, ccode);
    encode_File(ccode);

    fp << encoded;
    
    fp.close();
    fp2.close();
}

int main()
{
    create_Huffman_Tree();
    HuffNode* root = freq_queue.top();
    save_Huffman_Code();
}

问题根源 #

1. 编码存储方式错误：你把Huffman编码的每一位（0/1）都存成了单个ASCII字符，每个字符占1字节。比如44位的编码直接占用44字节，远大于原文件的17字节。真正的Huffman压缩需要将编码按位打包成字节存储，而非字符串形式的0和1。
2. 文件读取逻辑bug：file_getter中while(!fp.eof())的写法会多读一个EOF字符，导致频率统计错误。
3. 编码效率低下：每次编码字符都要遍历整棵树查找，重复计算但不是体积变大的直接原因。
4. 小文件元数据开销：原文件仅17字节，哈夫曼树的元数据（若要支持解压）会占一定比例，但核心问题还是编码存储方式错误。

修复方案（符合限制要求） #

1. 预先生成所有字符的编码映射（用数组替代map） #

利用字符范围0-255的特性，用string code_map[256]数组存储每个字符的Huffman编码，避免重复遍历树：

#include <cmath> // 后续转二进制会用到

// 新增全局数组存储编码映射
string code_map[256] = {""};

// 一次性遍历树生成所有字符的编码
void generate_codes(HuffNode* root, string current_code) {
    if (root == nullptr) return;
    // 叶子节点，记录编码
    if (root->my_Left == nullptr && root->my_Right == nullptr) {
        code_map[(unsigned char)root->my_Char] = current_code;
        return;
    }
    generate_codes(root->my_Left, current_code + "0");
    generate_codes(root->my_Right, current_code + "1");
}

// 修改create_Huffman_Tree，末尾调用生成编码的函数
void create_Huffman_Tree() {
    HuffNode* root;
    file_getter();
    
    for(int i = 0; i < 256; i++)
    {
        if(freq[i] > 0)
        {
            insert_Node(char(i), freq[i]);
        }
    }

    while(freq_queue.size() > 1)
    {
        HuffNode* for_Left = freq_queue.top();
        freq_queue.pop();
        HuffNode* for_Right = freq_queue.top();
        freq_queue.pop();

        int freq_sum = for_Left->my_Frequency + for_Right->my_Frequency;
        char ch = '$';
        root = set_Node(ch, freq_sum);
        root->my_Left = for_Left;
        root->my_Right = for_Right;

        freq_queue.push(root);
    }

    root = freq_queue.top();
    generate_codes(root, ""); // 新增：生成所有字符的编码
}

2. 修复文件读取bug #

将while(!fp.eof())改为正确的先读再判断的方式：

void file_getter()
{
    fstream fp;
    char c;

    fp.open(get_file_name(), ios::in);
    if(!fp)
    {
        cout << "Error: Couldn't open file " << endl;
        system("pause");
        return;
    }
    // 正确读取：先获取字符，再判断是否成功
    while(fp.get(c)) {
        freq[(unsigned char)c]++;
    }
    fp.close();
}

3. 模拟位打包存储编码（不用位操作） #

将编码字符串按8位分组，转换为字符写入文件，不足8位补0：

void save_Huffman_Code() {
    fstream fp, fp2;
    fp.open("Compressed_file.bin", ios::out);
    fp2.open(filename, ios::in);
    
    string ccode;
    getline(fp2, ccode);
    // 拼接完整编码字符串
    encoded = "";
    for (int i = 0; i < ccode.length(); i++) {
        char c = ccode[i];
        encoded += code_map[(unsigned char)c];
    }
    
    // 补0凑整字节
    int padding = 8 - (encoded.length() % 8);
    if (padding != 8) {
        encoded += string(padding, '0');
    }
    
    // 将每8位二进制字符串转成字符写入
    for (int i = 0; i < encoded.length(); i += 8) {
        string byte_str = encoded.substr(i, 8);
        char byte = 0;
        // 不用位操作，用十进制计算转换
        for (int j = 0; j < 8; j++) {
            if (byte_str[j] == '1') {
                byte += (int)pow(2, 7 - j);
            }
        }
        fp.put(byte);
    }
    
    // 写入补0的数量，方便解压时去除冗余
    fp.put((char)padding);
    
    fp.close();
    fp2.close();
}

修复后的效果 #

修复后，原17字节的文件编码后会被打包成6字节的编码内容，加上补0标记和哈夫曼树的存储（若需解压），总大小会明显小于44字节，甚至接近原文件大小（小文件的元数据开销不可避免，但大文件压缩效果会显著）。

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