C/C++基于哈夫曼树的文件压缩软件[2023-07-06]

案例 2 基于哈夫曼树的文件压缩软件
2.1 简介
数据压缩分为两大类：无损压缩和有损压缩。无损压缩是指压缩后还能还原回原来的
数据的压缩方法，有损压缩一般是针对图像、视频或音频进行的压缩，在压缩后图像、视频
或音频的质量会有所下降，这种压缩一般不能再还原回原来的数据。本次课程设计主要研究
无损压缩，不但设计压缩算法，还要设计解压缩算法。
数据压缩有许多不同的方法，其中一种重要的方法是利用了哈夫曼编码。用哈夫曼编
码压缩的数据可以节约 20%到 85%的空间储蓄。这种算法是根据它的发明者 David Huffman
的名字命名的，他是一位信息理论学家和计算机科学家，他在 20 世纪 50 年代发明了此项
技术。当压缩数据的时候，通常会把组成数据的字符转换成一些其他表现以节省空间。一种
典型的压缩方法是把每个字符转换成二进制字符代码或者位字符串。例如，把字符“a”编
码成 000，字符“b”编码成 001，而字符“c”则变成 010，如此等等。这种方法被称为是
固定长度编码。
但是，还可以用一种更好的方法，就是使用可变长度编码。既然某些字符会多次用到，
所以这些最频繁出现在字符串内的字符具有较短的编码，而具有较低出现频率的字符则拥有
较长的编码。编码的过程就是依据某个字符的出现频率把位字符串赋值给该字符的过程。哈
夫曼编码算法每次将最小的两个子树树根作为两个孩子重新生成一棵树，树根的权值为两个
孩子的权值之和，重复这一过程，直至只有一个树根为止。把到达每个左孩子节点的路径设
置为二进制字符 0，而把到达每个右孩子节点的路径设置为二进制字符 1。
例如：设存入 10000 个字符，出现的频率如下：

A：25% 
B：20% 
C：15% 
D：10% 
E：10% 
F：10% 
G：5% 
H：5% 

构造树，如下图所示，根据该哈夫曼树，得到各个字母的编码如下：

A：01 
B：11 
C：001 
D：100 
E：101 
F：0001 
G：00000 
H：00001

图 2-1 最优二叉树的一个例子
压缩后，总共需要的二进制位个数为：
25002+20002+15003+10003+10003+10004+5005+5005
=28500
它的字节数为 28500/8=3562，与压缩前相比，长度只有原来的三分之一。
2.2 数据结构的定义
2.2.1 内存中的存储结构定义

typedef struct 
{ 
char ch; //字符名称 
int weight; //权值(字符出现的次数) 
}charweight; 
typedef struct hftnode 
{ 
int weight; //权值 
int parent,lchild,rchild;//双亲、左孩子、有孩子的存储位置(数组下标) 
}HFMNode; 
typedef struct hc 
{ 
char ch; //字符名称 
12int start; //字符编码存储的起始为止，即从数组从 start 到 299 的各个字符为编码 
char link[300];//用来存放 ch 的编码的字符数组 
}HFMCode; 
//哈夫曼树的叶子节点个数，即被压缩文件出现的不同字符数。 
int HFMCodeLength; 
charweight flist[256]; //存放被压缩文件各个字符出现的次数 
HFMCode hfmcode[256]; //存放各个字符的 01 哈夫曼编码 

2.2.2 压缩文件的结构定义
按照存储的先后次序，压缩文件的内容依次包括：
(1)压缩文件内部标识'Y'和'S'(char 型，2 字节)
(2)树叶结点个数(short int 型，2 字节)
(3)各个树叶结点的 Huffman 编码，每个树叶结点的编码按下述格式存储:
a)树叶字符 Li的名称(char 型，1 字节)
b)树叶字符 Li的编码 01 二进制位个数(unsigned char 型，1 字节)
c)树叶字符 Li的编码长度 Ni2(unsigned char 型，1 字节)
d)树叶字符 Li的编码(char 型，Ni字节)
(4)8 位对齐补偿长度
(5)原始文件的 Huffman 编码长度 Ns(int 类型，4 字节)
(6)原始文件的 Huffman 编码(unsigned char 型，Ns字节)
2.3. 算法实现步骤
2.3.1 压缩算法实现步骤
(1)读取原始文件，统计各个字符出现的次数，把各个字符的名称和出现的次数放在结构体
数据组 flist 中。把不同的字符数保存在 HFMCodeLength 中。
(2)把原始文件中出现的字符保存在 hfmcode[i].ch 中，把 hfmcode[i].start 置初值 299，
把 hfmcode[i].link 数组初始化为全'0'的数组。
(3)用下述的哈夫曼树的算法，根据 flist 数组创建哈夫曼树，创建后的哈夫曼树保存在数
组 hfmtree 中。用下述的建哈夫曼编码的算法，创建哈夫曼编码，创建后的编码保存在数组
hfmcode 中。
(4)读取原始文件的各个字符，对每个字符
a)在 hfmcode 中查找与之对应的哈夫曼编码
b)把哈夫曼编码依次保存到字符数组 p 中，p 的每个字符，要么是'0',
要么是'1'。
(5)假设数组 p 中总共存储了 k 个字符，再增加 len_duiqi 个字符，使字符总数为 8 的整数
倍。
(6)创建压缩文件，将'Y'和'S'写入压缩文件，作为文件内部标识
(7)将树叶结点个数 cnum(short int 型)写入压缩文件
13下面的(8)(9)(10)(11)循环执行 cnum 次
(8)写入树叶字符 Li的名称(char 型)
(9)写入树叶字符 Li的编码 01 二进制位个数(unsigned char 型)
(10)将树叶字符 Li的编码有 01 字节编码转换为 01 二进制编码，然后
写入 01 二进制编码的长度 Ni(unsigned char 型)
(11)将转换后的二进制编码写入文件(Ni字节)
(12)写入 8 位对齐补偿长度 len_duiqi
(12)写入原始文件的 Huffman 编码长度 Ns(int 类型)
(13)将数组 p 中的 01 字节编码转换为 01 二进制编码，将该二进制编码写入文件
2.3.2 解压缩算法实现步骤
(1)从压缩文件读取两个字节的内部标识
(2)从压缩文件读取树叶结点个数 cnum
下面的(3)(4)(5)(6)循环执行 cnum 次
(3)读取树叶字符 Li的名称(char 型)
(4)读取树叶字符 Li的编码 01 二进制位个数(unsigned char 型)
(5)读取 01 二进制编码的长度 Ni
(6)读取 Ni个字节到数组 hcode 中，将 hcode 中的 01 二进制编码
转换为 01 字节编码，然后保存到 hfmcode[i].link[]中
(7)读取 8 位对齐补偿长度 len_duiqi
(8)读取 Huffman 编码长度 Ns(int 类型)
(9)读取 Ns个字节到数组 str 中，然后将 str 中的 01 二进制编码转换为 01
字节编码。
(10)舍去 str 中的最后 len_duiqi 个字符，得到 01 字节编码的长度 len
(11)创建解压缩文件，然后从前向后依次搜索 hfmcode 中的各个编码，
如果能搜到，则把与之对应的字符写入解压缩文件。
2.3.3 算法的伪代码
以下为创建哈夫曼树的伪代码，

/*w 存放 n 个字符的权值(均>0),构造哈夫曼树 HT,并求出 n 个字符的哈夫曼编码 HC.*/ 
void HuffmanCoding(HFMNode *HT, HFMCode *HC,int *w,int n) 
{ 
if(n<=1) return; 
m=2*n-1; 
for(p=HT,i=0;i<n;++i,++p,++w) *p={*w,0,0,0}; 
for(;i<m;++i,++p) *p={0,0,0,0}; 
//建哈夫曼树 
for(i=n+1;i<=m;++i) 
{ 
/*在 HT[1..i-1]选择 parent 为 0 且 weight 最小的两个结点, 
其序号分别为 s1 和 s2.*/ 
select(HT,i-1,s1,s2); 
HT[s1].parent=i;HT[s2].parent=i; 
1415 
HT[i].lchild=s1;HT[i].rchild=s2; 
HT[i].weight=HT[s1].weight+HT[s2].weight; 
} 
以下为创建哈夫曼编码的伪代码， 
//-----从叶子到根逆向求每个字符的哈夫曼编码----- 
//分配 n 个字符编码的头指针向量 
for(i=0;i<n;++i)//逐个字符求哈夫曼编码 
{ 
HC[i].start=n-1; 
//编码结束符位置 
//从叶子至根逆向求编码 
for(c=i,f=HT[i];f!=0;c=f,f=HT[f].parent) 
if(HT[f].lchild==c) 
HC[i].cd[--start]="0"; 
else 
HC[i].cd[--start]="1"; 
} 
} 

2.4. 程序的运行界面

注意：最后输出界面要在此基础上输出压缩前后字节大小！

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111