c语言如何将一个由五个字符组成的文本文件用哈夫曼压缩,并生成一个压缩文件。并写出注释
时间: 2023-11-27 15:50:23 浏览: 79
用Huffman编码对文件进行压缩的C语言实现
首先要理解哈夫曼编码的原理和实现过程。哈夫曼编码是一种变长编码方式,它使用较短的编码表示出现频率较高的字符,而使用较长的编码表示出现频率较低的字符。通过这样的编码方式,可以有效地减少文本文件的数据量,从而达到压缩的效果。
对于一个由五个字符组成的文本文件,在使用哈夫曼编码进行压缩之前,需要先进行字符频率统计,即统计每个字符在文本文件中出现的次数。根据统计结果,可以构建出哈夫曼树,并得到每个字符对应的哈夫曼编码。然后将文本文件中的每个字符替换成对应的哈夫曼编码,并生成一个压缩文件。
以下是一份使用C语言实现哈夫曼编码压缩的示例代码,其中注释部分为详细解释说明:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define CHAR_NUM 256 // 字符集大小
#define FILE_BUF_SIZE 1024 // 文件读写缓冲区大小
// 哈夫曼树节点结构体
typedef struct _HuffmanNode {
char ch; // 字符
int weight; // 权重
struct _HuffmanNode *left; // 左子树节点指针
struct _HuffmanNode *right; // 右子树节点指针
} HuffmanNode;
// 哈夫曼编码结构体
typedef struct _HuffmanCode {
char ch; // 字符
unsigned char code[CHAR_NUM / 8]; // 编码
int length; // 编码长度
} HuffmanCode;
// 统计字符在文件中出现的次数
bool _count_chars(const char *file_path, int *char_weights) {
FILE *fp = fopen(file_path, "rb");
if (!fp) {
printf("Failed to open file %s\n", file_path);
return false;
}
char buf[FILE_BUF_SIZE];
int read_size = 0;
while ((read_size = fread(buf, 1, sizeof(buf), fp)) > 0) {
for (int i = 0; i < read_size; ++i) {
++char_weights[buf[i]];
}
}
fclose(fp);
return true;
}
// 建立哈夫曼树
HuffmanNode *_build_huffman_tree(int *char_weights) {
// 初始化哈夫曼树节点数组
HuffmanNode *node_array[CHAR_NUM];
for (int i = 0; i < CHAR_NUM; ++i) {
node_array[i] = (HuffmanNode *)malloc(sizeof(HuffmanNode));
memset(node_array[i], 0, sizeof(HuffmanNode));
node_array[i]->ch = (char)i;
node_array[i]->weight = char_weights[i];
}
// 通过构建小根堆化的哈夫曼树来合并节点
int node_count = CHAR_NUM;
while (node_count > 1) {
// 找到最小权重的两个节点
HuffmanNode *min_node1 = NULL, *min_node2 = NULL;
for (int i = 0; i < node_count; ++i) {
HuffmanNode *node = node_array[i];
if (!node->left && !node->right) {
if (!min_node1 || node->weight < min_node1->weight) {
min_node2 = min_node1;
min_node1 = node;
} else if (!min_node2 || node->weight < min_node2->weight) {
min_node2 = node;
}
}
}
// 合并节点
HuffmanNode *new_node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
memset(new_node, 0, sizeof(HuffmanNode));
new_node->left = min_node1;
new_node->right = min_node2;
new_node->weight = min_node1->weight + min_node2->weight;
// 插入合并节点到节点数组
node_array[node_count - 1] = new_node;
--node_count;
}
return node_array[0];
}
// 递归计算哈夫曼编码
void _calc_huffman_code(HuffmanNode *node, HuffmanCode *code_array, unsigned char *code_bits, int code_len) {
if (!node->left && !node->right) {
HuffmanCode *code = &code_array[(unsigned char)node->ch];
code->ch = node->ch;
memcpy(code->code, code_bits, code_len < CHAR_NUM / 8 ? code_len : CHAR_NUM / 8);
code->length = code_len;
} else {
if (node->left) {
code_bits[code_len / 8] &= ~(1 << (code_len % 8));
_calc_huffman_code(node->left, code_array, code_bits, code_len + 1);
}
if (node->right) {
code_bits[code_len / 8] |= (1 << (code_len % 8));
_calc_huffman_code(node->right, code_array, code_bits, code_len + 1);
}
}
}
// 生成哈夫曼编码
HuffmanCode *_gen_huffman_code(HuffmanNode *root) {
HuffmanCode *code_array = (HuffmanCode *)malloc(sizeof(HuffmanCode) * CHAR_NUM);
memset(code_array, 0, sizeof(HuffmanCode) * CHAR_NUM);
// 递归计算哈夫曼编码
unsigned char code_bits[CHAR_NUM / 8] = { 0 };
_calc_huffman_code(root, code_array, code_bits, 0);
return code_array;
}
// 将文本文件用哈夫曼编码进行压缩,并生成压缩文件
bool huffman_compress(const char *file_path) {
int char_weights[CHAR_NUM] = { 0 };
if (!_count_chars(file_path, char_weights)) {
return false;
}
HuffmanNode *root = _build_huffman_tree(char_weights);
if (!root) {
printf("Failed to build Huffman tree\n");
return false;
}
HuffmanCode *code_array = _gen_huffman_code(root);
if (!code_array) {
printf("Failed to generate Huffman code\n");
return false;
}
char huff_file_path[256] = { 0 };
sprintf(huff_file_path, "%s.huff", file_path);
FILE *fp_in = fopen(file_path, "rb"), *fp_out = fopen(huff_file_path, "wb");
if (!fp_in || !fp_out) {
printf("Failed to open file\n");
return false;
}
unsigned char bit_buf = 0, bit_count = 0;
int read_size = 0;
while ((read_size = fread(&bit_buf, 1, 1, fp_in)) > 0) {
HuffmanCode *code = &code_array[bit_buf];
for (int i = 0; i < code->length; ++i) {
if (bit_count == 8) {
fwrite(&bit_buf, 1, 1, fp_out);
bit_count = 0;
bit_buf = 0;
}
if (code->code[i / 8] & (1 << (i % 8))) {
bit_buf |= (1 << bit_count);
}
++bit_count;
}
}
if (bit_count > 0) {
fwrite(&bit_buf, 1, 1, fp_out);
}
fclose(fp_in);
fclose(fp_out);
return true;
}
int main(int argc, char *argv[]) {
if (argc != 2) {
printf("Usage: huffman_compress <file_path>\n");
return 0;
}
if (!huffman_compress(argv[1])) {
printf("Failed to compress file %s\n", argv[1]);
return 1;
}
printf("Compress file %s succeeded\n", argv[1]);
return 0;
}
```
阅读全文