我编写了这个函数。它对我输入的文件(要压缩的文件)做了一些神奇的事情 – 一个 .txt(文本)文件,但是输出(压缩)文件比原始文件大。例如:我输入了一个 1169MB 的文件,程序返回了一个 1687MB 的文件。
怎样才能解决这个问题?
也许我应该使用其他方法或变体来使用 Huffman 算法压缩文件?
struct HuffNode{
unsigned data;
struct HuffNode *left;
struct HuffNode *right;
struct HuffNode *parent;
int is_leaf;
};
typedef struct HuffNode HuffNode;
void count_frequency(FILE *fp, unsigned *freq) {
size_t original_pos = ftell(fp);
int ch;
while ((ch = fgetc(fp)) != EOF) {
if (ch >= 0 && ch < 256)
freq[ch]++;
}
fseek(fp, original_pos, SEEK_SET);
}
void construct_huffman(unsigned *freq_in, HuffNode *tree) {
int count = 256;
unsigned freq[256] = {0};
HuffNode *node[256];
for (int i = 0; i < 256; i++) {
freq[i] = freq_in[i];
tree[i].data = i;
tree[i].left = NULL;
tree[i].right = NULL;
tree[i].parent = NULL;
tree[i].is_leaf = 1;
node[i] = &tree[i];
}
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 256 - i - 1; j++) {
if (j + 1 < 256 && (freq[j] < freq[j + 1] || (freq[j] == freq[j+1] && j < j + 1))) {
unsigned t = freq[j];
freq[j] = freq[j + 1];
freq[j + 1] = t;
HuffNode *p = node[j];
node[j] = node[j + 1];
node[j + 1] = p;
}
}
}
while (count > 1) {
int pos = 512 - count;
HuffNode *parent = &tree[pos];
int i = count - 2, j = count - 1;
parent->left = node[j];
parent->right = node[i];
node[j]->parent = parent;
node[i]->parent = parent;
node[i]->is_leaf = 0;
node[j]->is_leaf = 0;
node[i] = parent;
freq[i] += freq[j];
for (; i > 0 && freq[i] > freq[i - 1]; i--) {
unsigned t = freq[i];
freq[i] = freq[i - 1];
freq[i - 1] = t;
HuffNode *p = node[i];
node[i] = node[i - 1];
node[i - 1] = p;
}
count--;
}
node[0]->parent = NULL;
}
void encode_stream(FILE *fin, FILE *fout, HuffNode *tree, unsigned *padding) {
int n;
unsigned char ch;
unsigned char buff = 0, nbuf = 0;
HuffNode *p;
unsigned char code[256] = {0};
while ((n = fgetc(fin)) != EOF) {
if(n < 0 || n >= 256){
printf("invalid characters in the file");
return;
}
ch = n;
p = &tree[ch];
int code_length = 0;
while (p->parent) {
if (p == p->parent->right) {
code[code_length] = 1;
}
p = p->parent;
code_length++;
}
for (int i = code_length - 1; i >= 0; i--) {
buff |= code[i] << nbuf;
nbuf++;
if (nbuf == 8) {
fputc(buff, fout);
nbuf = 0;
buff = 0;
}
}
}
if (nbuf > 0) {
fputc(buff, fout);
}
*padding = 8 - nbuf;
}
void compress_file(FILE *fin, FILE *fout) {
unsigned freq[256] = {0}, padding = 0; //- хз
int flag = 0;
size_t padding_pos;
HuffNode tree[512];
if (flag == 0) {
count_frequency(fin, freq);
construct_huffman(freq, tree);
rewind(fin);
for (int i = 0; i < 256; i++) {
fwrite(&freq[i], sizeof(unsigned), 1, fout);
}
padding_pos = ftell(fout);
fwrite(&padding, sizeof(unsigned), 1, fout);
encode_stream(fin, fout, tree, &padding);
fseek(fout, padding_pos, SEEK_SET);
fwrite(&padding, sizeof(unsigned), 1, fout);
}
}
我不知道为什么它不能正确压缩文件。
9
最佳答案
2
在考虑输出的大小之前,您需要首先确保输出实际上是霍夫曼编码。目前还不是。绝大多数输出字节都是0xff
。在断定它正常工作之前,您至少应该看看输出中的内容。
您真正需要做的是编写配套解压程序,并通过大量测试让两者正常工作,以验证压缩和解压是否无损。然后,您可以检查输出是否小于您期望可压缩的内容的输入,例如英文文本。
通过对 Huffman 树进行编码,您可以大大减少小输入的输出大小,而不是发送所有 256 个频率,每个频率 4 个字节,总共 1K。遍历树并1
为每个分支写入一个位,然后为叶子写入一个位,0
后面跟着字符的 8 个位。此树表示是自终止的。然后是 Huffman 编码数据。对于n 个编码字节,这将需要10n-1位。如果所有可能的字节都进行了编码,则最多需要 ~320 个字节。很可能不是所有字节都进行了编码。(还有其他使用规范 Huffman 代码的更紧凑的代码编码,但这是一个容易上手的方法。)
|
霍夫曼算法产生的压缩文件比原始文件更大
原始文件很可能已被压缩或只是大量随机数据。
并非所有文件都可压缩。
如果所有文件都是可压缩的,则可以对生成的文件重新应用压缩。通过重复,我们最终可以达到 0 的大小。
|
–
–
0xff
。首先在小示例上进行调试。我建议您编写一个配套的解压缩程序,因为这是验证两者是否正常工作的唯一方法。–
&& j < j + 1
?–
encode_stream()
:中有一个错误,code
它最初被置零,但随后只填充了 1。要在if (p == p->parent->right) { code[code_length] = 1; }
添加后修复它else { code[code_length] = 0; }
。或者if
使用 更改整个语句code[code_length] = (p == p->parent->right);
–
|