我的压缩文件比原始文件大

Question

我只能使用队列库编写霍夫曼编码代码。但是当我保存文件进行压缩时，它的字节大小比原始文件大。

。filesize.txt有17个字节，它包含一个字符串" stressed -甜品"而

compressedfile.bin有44个字节，包含原始文件的霍夫曼码"01111011000011110001001100100011110010010111"

这是我的全部代码

#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();
}

我应该得到一个比原始文件字节大小更小的压缩文件。我试图在不使用位操作的情况下编写代码，无序的映射或映射。我只对程序使用priority_queue。

Answer 1

你的输出是每比特8位，所以它比它应该的大8倍。你想写一个比特一个比特。要写入位，您需要将它们一个接一个地累加到字节缓冲区中，直到有8个字节，然后写入该字节。最后，写入剩余的位。使用位运算符<<和|将位放入字节缓冲区。例如，对于每个等于0或1的bit:

unsigned buf = 0, n = 0;
...
buf |= bit << n;
if (++n == 8) {
fp.put(buf);
buf = n = 0;
}
...
if (n)
fp.put(buf);

你的代码还有很多其他的错误。

1. 由于c是有符号字节类型，freq[c]++;对于大于127字节的输入将失败，因为c将为负。你需要int c;而不是char c。
2. 使用while(!fp.eof())将导致获得-1作为您的最后一个字符，这是一个EOF指示，并且再次用负数索引您的数组。执行while ((c = fp.get()) != -1).
3. 您在第一次读取文件时使用一系列get()'s，这是正确的。然而，第二次读取该文件时，使用单个getline()。这只得到第一行，它省略了新的行字符。使用一系列get()'s，两次以相同的方式读取文件。
你只是在写代码。在它们之前没有对霍夫曼码的描述，所以解码器没有办法理解你发送的比特。一旦您将其修改为每比特发送一个比特而不是每比特发送一个字节，您的输出将小于数据实际可以压缩到的值。当添加树时，输入和输出的长度将大致相同。
4. 每次要编码一个字符时，都要遍历整个树!您需要通过遍历树一次来制作代码表，然后使用该表进行编码。
5. 没有办法知道有多少字符被编码，这将导致最后一个字节中任何额外的位的模糊性。您需要在编码字符之前发送字符数，或者在编码流结束指示符时再包含一个符号。

Answer 2

您在encoded中拥有的是0和1的字符串。它们本身就是字符。您可能想要将字符串转换为二进制然后存储它?

如果你使用字符(一个字节)来存储0和1，它将占用更多的空间。它不是使用1位来存储数字，而是使用1字节。所以如果你把数据转换成位，它应该是(44/8)+1