C语言Huffman压缩和解压
2024-10-20 13:49:22
符号表结构体：
struct node
{
// 字符串形式存储的Huffman编码
char code[MAX_CODE_LENGTH];
// 这个字符在文件中出现的次数
long count;
// 在生成Huffman树的时候是否已经被当作叶子节点
int checked;
// 符号
char sym;
// left和right只在生成Huffman树的时候有用
struct node* next,*left,*right;
};全局变量：
const int BIT_WIDTH_CHAR = 8;
const int END_SYM_FLAG = 200;// 符号的范围是-127~128
int gl_total_node_num = 0;// 符号表的总长度
int gl_source_file_length = 0;// 源文件的总长度辅助函数：
// 在链表中查找指定的字符
// 参数：符号表
// 参数：字符
// 返回值：找到的节点的指针
struct node* content_char(struct node*,char);
// 在链表中查找指定编码
// 参数：符号表
// 参数：编码
// 返回值：找到的节点的指针
struct node* content_code(struct node* list,const char* ch);
// 根据字符创建一个新的节点
// 参数：字符
// 参数：计数
// 返回值：新节点指针
struct node* create_new_node(char ch,int count);
// 插入新节点到符号表的最前面
// 参数list：目标链表
// 参数new_node：新节点
// 返回值：插入后的链表
struct node* insert_node(struct node *list,struct node *new_node);
// 输出链表
// 参数list：目标链表
void print_list(struct node *list);
// 获取到最小的未被检查的count的节点，返回它的指针，并将其设置为检查过的
// 参数list_addr：链表头
// 返回值：第一个未检查的最少出现次数的结点指针
struct node* get_smallest_node(struct node *list_addr);压缩：
第一步：建立符号表
在main函数中：获取文件的总长度，用于生成进度条
// 获取文件长度，以实现进度条
fseek(source_file,0,SEEK_END);
gl_source_file_length = ftell(source_file);
fseek(source_file,0,SEEK_SET);
扫描源文件，按字符读取，建立符号表，统计每个字符出现的次数
首先提示进度条，10个'.'为结束
将读取到的字符在已有的符号表中查找，如果已存在就将该节点的count+1，否则就创建新节点并插入到符号表中
统计符号表中总节点数
// 生成符号链表（含频率）
// 参数：源文件
// 参数：目标链表
// 返回值：符号链表
struct node* generate_count(FILE* f,struct node*list)
{
printf("counting");
int count=0;
char ch;
struct node *content_node;
while(fread(&ch,sizeof(char),1,f)==1)
{
// 进度条
count++;
if(count%(gl_source_file_length/10+1)==0)
printf(".");
// 插入符号表
content_node = content_char(list,ch);
if(content_node)
content_node->count++;
else
{
gl_total_node_num++;
list=insert_node(list,create_new_node(ch,1));
}
}
printf("\n");
return list;
}第二步：生成Huffman树
生成Huffman树
使用先前统计的符号表总数进行计数循环，因为生成树的所有非叶子节点共有叶子节点-1个
首先输出进度条
视初始时所有的符号表中的节点为只有一个节点的子树，获取两个最小的count的子树根节点指针，这是通过节点的checked属性实现的，如果使用了两个子树根节点生成新的子树，那么这两个子树根节点的checked将会设为1，在寻找最小节点的时候将会跳过
将新的树的中间节点插入到符号表中
最终的效果是符号表中只有最前面的一个节点的checked为0
// 生成Huffman树
// 参数：符号链表
// 返回值：含有Huffman树的链表，非叶节点将插入到链表前面，并有左右孩子属性，叶节点没有左右孩子属性
struct node* generate_tree(struct node* list)
{
printf("generate_tree");
// 生成树
for(int i=1;i<gl_total_node_num;i++)
{
// 进度条
if(i%(gl_total_node_num/10+1)==0)
printf(".");
// 获取最小出现次数的两个符号，并生成新的节点插入符号表
struct node *sm_left=get_smallest_node(list);
struct node *sm_right=get_smallest_node(list);
struct node *new_node=create_new_node('\0',sm_left->count+sm_right->count);
new_node->left=sm_left;
new_node->right=sm_right;
list = insert_node(list,new_node);
}
printf("\n");
return list;
}第三步：生成编码
从Huffman树中生成符号表的编码属性
因为这是一棵树，所以用递归的方式进行
某节点的左孩子的编码将在继承其父节点编码的基础上扩展'0'，右孩子将在继承其父节点的编码的基础上扩展'1'
最终所有叶子节点的编码就是Huffman编码
// 递归的生成Huffman编码于符号链表
// 参数：Huffman树
void generate_code(struct node*list)
{
// 生成Huffman编码
if(!list)return;
// 左子树扩展'0'
if(list->left)
{
strcat(list->left->code,list->code);
strcat(list->left->code,"0");
generate_code(list->left);
}
// 右子树'1'
if(list->right)
{
strcat(list->right->code,list->code);
strcat(list->right->code,"1");
generate_code(list->right);
}
}因为之后树就没什么用了，只有叶子节点有用，所以将其他节点释放掉
// 释放Huffman树的非叶子节点，只留下符号链表
// 参数：Huffman树
// 返回值：不含Huffman树的符号链表
struct node* free_tree(struct node*list)
{
struct node*free_node=list;
while(list->left && list->right)// 左右子树不为空的节点都是需要释放的
{
free_node=list;
list=list->next;
free(free_node);
}
return list;
}第四步：生成目标文件
首先将符号表写入到目标文件头部，再次扫描源文件，将每个字符转换为对应的编码，并以二进制的形式存储在目标文件中
// 生成目标文件
// 参数：源文件
// 参数：目标文件
// 参数：符号链表
void generate_des_file(FILE* sf,FILE* df,struct node*list)首先，为了解压，要把符号表的内容写入到目标文件前面
其中符号和编码时两两配对的，最后通过一个符号表不可能取到的值标记结束
标识符之间是通过空格隔开，最终结束时以换行符结尾。这里的规则将在解压的时候需要严格遵守
// 符号表以文本形式写入到目标文件的前端，解压时需要的信息
struct node* index=list;
while(index)
{
fprintf(df,"%d %s ",index->sym,index->code);
index=index->next;
}
// 指示结尾，"END"实际上没有用到，只用于和END_SYM_FLAG配对
fprintf(df,"%d %s\n",END_SYM_FLAG,"END");
变量：
// 实际文件内容（二进制形式）
// 前者是从源文件中读取的字符，后置是对Huffman编码进行二进制形式转换后取8位形成的字符
char ch,des_ch='\0';
// 目标字符知否足够8位可以进行写入？
int des_ch_length=0;
// 因为之前进行了读取，所以这里回到文件头
fseek(sf,0,SEEK_SET);
int count=0;// 程序执行进度提示
while循环读文件：
while(fread(&ch,sizeof(char),1,sf)==1)输出进度条，并根据从源文件中读取的字符找符号表中对应的节点
// 进度条
count++;
if(count%(gl_source_file_length/10+1)==0)
printf(".");
// 在符号表中找这个字符
// 没有找到一定是出错了
struct node *content_node = content_char(list,ch);
if(!content_node)
{
printf("error:cannot match with sym list\n");
exit(0);
}
现在需要将符号对应的字符串Huffman编码转化为一个个8位char类型，其中每一位代表一位Huffman编码
对这个编码每一位循环处理：将已经部分生成的目标字符左移一位，如果当前的编码位为1就用掩码0000 0001和目标字符按位或，那么最后一位将为1，其余不变，当前编码位为0就不做操作，因为本来左移就补0
当记录的长度达到8的时候就将这个字符写入到目标文件，将记录长度清零，继续对编码的每一位循环
// 对这个符号对应的Huffman编码进行二进制转化
char* current_code=content_node->code;
for(int i=0;i<strlen(current_code);i++)
{
// 每次循环左移一位，长度+1
des_ch=des_ch<<1;
des_ch_length++;
// 末位默认位0，否则置1
if(current_code[i]=='1')des_ch |= (char)1;
// 已经足够了一个字符，就写入，并清0
if(des_ch_length==8)
{
if(!fwrite(&des_ch,sizeof(char),1,df))
{
printf("error:cannot write to des file.\n");
exit(0);
}
des_ch_length=0;
des_ch=0;
}// 形成了一个字符
}// Huffman编码
但是最后一位不一定够8位，这需要额外的说明
将剩下的这个字符左对齐，并在目标文件的最后一个字符说明前一个字符有几位有效
// 最后一个字符，没有满足8位
if(des_ch_length!=0)
{
des_ch=des_ch<<BIT_WIDTH_CHAR-des_ch_length;
if(!fwrite(&des_ch,sizeof(char),1,df))
{
printf("error:cannot write to des file.\n");
exit(0);
}
}
// 最后这个一定是一个字符（1-8），表示最后一个有效字符的长度
fprintf(df,"%d",des_ch_length);
解压：
第一步：从目标文件读取符号表
首先从源文件头读取并创建符号表
值得注意的是读取字符串的时候用fscanf将会在遇到空格的时候结束，而用其他的方式将会在换行符时结束，但是我们在生成的时候全都生成在一行
在读取结束的时候需要将换行符读掉，否则接下来将会读到换行符并解析
// 获取文件头的符号表
// 参数：源文件
// 返回值：符号表
struct node* de_get_sym_list(FILE* f)
{
printf("getting sym list...\n");
char code[MAX_CODE_LENGTH];
int ch_int;
struct node* list=NULL;
fscanf(f,"%d %s",&ch_int,code);
// 如果没有读到结束标志
while(ch_int!=END_SYM_FLAG)
{
// 创建新节点并插入符号表
struct node* new_node=create_new_node((char)ch_int,0);
strcpy(new_node->code,code);
list=insert_node(list,new_node);
fscanf(f,"%d %s",&ch_int,code);
}
fgetc(f);// 将换行符读掉，按照生成的规则，最后是一个换行符
return list;
}第二步：解析压缩内容
// 生成解压后的文件
// 参数：源文件
// 参数：目标文件
// 参数：符号链表
void de_generate_des_file(FILE* sf,FILE* df,struct node* list)变量：
// 存储未形成一个有效的Huffman编码的字符串
char temp_code[MAX_CODE_LENGTH] = {'\0'};
int last_length;// 最后一个字符的有效位长度
// 分别指向实际的压缩内容（去除头部的符号表）的头和尾
long current_file_index,file_length;
// 位操作的掩码，首位为1其余为0
char mask=((char)1)<<BIT_WIDTH_CHAR-1;
// 用于扩展Huffman编码的字符串，"0"或者"1"
char append[]={'0','\0'};
对文件的长度进行测量，并将最后一个字符有效位数读取进来，如果不记录长度，在之后的循环读取中想要跳过最后一个符号将会有些麻烦
记得要将文件的游标移动到合适的位置
// 记录此时符号表读取结束的位置
current_file_index = ftell(sf);
// 从文件尾获取最后一个字符的长度，以及文件的长度
fseek(sf,-(sizeof(char)),SEEK_END);
file_length = ftell(sf);
last_length = fgetc(sf)-'0';
// 回复当前位置到符号表结束的位置
fseek(sf,current_file_index,SEEK_SET);
因为已知了长度，所以读文件的时候可以计数循环，而不是检测文件尾。跳过最后一个字符（当然，这里的最后一个不包括后面的那个表示它的有效位数的数字字符）
for(int i=current_file_index;i<file_length-1;i++)首先时进度条，并进行读取：
// 进度条
if(i%((file_length-current_file_index)/10+1)==0)
printf(".");
// 读取是否成功
if(fread(&ch,sizeof(char),1,sf)!=1)
{
if(ferror(sf))
printf("error:cannot read file.\n");
if(feof(sf))
printf("end of reading file.\n");
exit(0);
}
对这个字符的每一位循环，将这个位转化为字符形式扩展到已有的字符串上，每扩展一位就检测一下符号表中有没有这个编码，有了就将对应的字符输出到文件中，并将字符串清空
位操作需要获取的是第一个位，所以掩码是第一位为1其余为0，按位与将获取第一个位：非0为1，0为0
// 将这一个字符的每一位扩展到未竟的Huffman编码上
for(int j=0;j<BIT_WIDTH_CHAR;j++)
{
append[0]='0' + ((ch & mask)==0?0:1);
strcat(temp_code,append);
ch=ch<<1;
// 尝试在符号表中寻找
the_node = content_code(list,temp_code);
if(the_node)
{
// 如果找到了就把其代表的符号写入文件
if(fwrite(&(the_node->sym),sizeof(char),1,df)!=1)
{
printf("error:failed to write file.\n");
exit(0);
}
// 清零临时字符串
temp_code[0]='\0';
}// 如果在符号表中找到
}// 对一个字符的每一位
最后一个字符，利用之前的长度进行循环，而不是8位
// 最后一个字符
if(fread(&ch,sizeof(char),1,sf)!=1)
{
printf("error:cannot read file.\n");
exit(0);
}
for(int i=0;i<last_length;i++)
{
append[0]='0' + ((ch & mask)==0?0:1);
strcat(temp_code,append);
ch=ch<<1;
// 尝试在符号表中寻找
the_node = content_code(list,temp_code);
if(the_node)
{
// 如果找到了就把其代表的符号写入文件
if(fwrite(&(the_node->sym),sizeof(char),1,df)!=1)
{
printf("error:failed to write file.\n");
exit(0);
}
// 清零临时字符串
temp_code[0]='\0';
}// 如果在符号表中找到
}
辅助函数：
// 根据字符创建一个新的节点
// 参数：字符
// 参数：计数
// 返回值：新节点指针
struct node* create_new_node(char ch,int count)
{
struct node *new_node = (struct node*)malloc(sizeof *new_node);
if(!new_node)
{
printf("error:failed to malloc.\n");
exit(0);
}
new_node->code[0]='\0';
new_node->sym=ch;
new_node->count=count;
new_node->next=NULL;
new_node->checked=0;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
}// 插入新节点
// 参数list：目标链表
// 参数new_node：新节点
// 返回值：插入后的链表
struct node* insert_node(struct node *list,struct node *new_node)
{
if(list)
new_node->next=list;
return new_node;
}// 获取到最小的未被检查的count的节点，返回它的指针，并将其设置为检查过的
// 参数list_addr：链表头
// 返回值：第一个未检查的最少出现次数的结点指针
struct node* get_smallest_node(struct node *list)
{
while(list && list->checked)list=list->next;// 获取到首个未检查的节点
struct node *smallest=list;
// 获取到最小的count的节点
while(list)
{
if(!list->checked && (list->count < smallest->count))
smallest=list;
list=list->next;
}
if(smallest)smallest->checked++;
return smallest;
}执行程序：
我用的是Windows10下的gcc编译器，命令行执行，并通过命令行参数传递源文件名和目的文件名
编译：gcc Huffman.c -o Huffman.exe
执行：Huffman.exe sourcefile desfile
执行之后会询问是执行压缩还是解压还是结束程序
执行压缩会把源文件压缩另存为目的文件
解压会将源文件解压另存为目的文件
需要注意的问题：
文件打开的时候是要用二进制流的形式打开，因为要对其进行位操作。如果用文本模式打开，在解压非文本文件的时候在中途程序就可能会认为自己读到的是EOF而结束读取。
因为符号是char类型的字符，所以符号表最大是256，编码的长度最长为255
将char解释为int类型时其取值范围为-127~128，所以想要标记压缩文件中符号表内容的结束，需要用这个范围之外的数
源码地址：
https://github.com/biaoJM/Huffman-Compression
最新文章
- 基于Metronic的Bootstrap开发框架经验总结（5）--Bootstrap文件上传插件File Input的使用
- MVC3.0 EF增删改查的封装类
- paip.文件读写api php java python总结.txt
- [转] error LNK2026: 模块对于 SAFESEH 映像是不安全的
- POJ3922 A simple stone game
- python学习1（小白记录）
- 康复计划#4 快速构造支配树的Lengauer-Tarjan算法
- TypeScript入门，使用TypeScript编写第三方控件的方式！
- ssh优缺点
- win10更改无线网卡的MAC地址
- wordpress安装教程
- xgboost安装 win10 64位 annaconda
- 往github上传代码忽略node_modules文件夹
- nginx 504 Gateway Time-out
- 鸟哥的Linux私房菜：基础学习篇 —— 第五章笔记
- 默认五笔输入法qq
- kylin-cube存储结构
- JavaScript数组（参考资料）
- STM32F10X固件库函数——串口清状态位函数分析
- Linux日知录(常用问题笔记)