基于哈夫曼编码对文件进行压缩和解压缩（详细讲解）

本文对应c++代码实现链接

一、背景

利用特定的算法来压缩数据的工具，压缩后生成的文件称为压缩包。如果想使用其中的数据，就得用压缩软件对数据进行解压。利用压缩软件对文件中重复的数据进行压缩，可以减小文件中的字节总数，常用的压缩软件有rar、zip等。

二、编码介绍

2.1 等长编码

任何文件在计算中都是以字节为最小单位进行存储的，所以可以把任何文件看作是利用8位（一个字节）作为等长编码编码方式，编码而成的文件。往往这种编码方式并不是最优的编码方式。

例如：对电文“ababababaaaccd”利用8位的ASCII码进行等长编码，其编码如下：

原文字符	等长编码
a	01100001
b	01100010
c	01100011
d	01100100

则源文件存储的编码为（注：为便于察看，在每个字符编码之间添加了空格，实际编码时没有这个空格）：

01100001 01100010 01100001 01100010 01100001 01100010 01100001 01100010 01100001 01100001 01100001 01100011 01100011 01100100

可以计算出上述纯文本文件的编码长度为14个字节112位（注：当文件的大小不足1K，操作系统也会给它分配1K的存储空间）

2.2 哈夫曼编码

同样地，如果对电文“ababababaaaccd”进行哈夫曼编码，则其编码方式如下：

原文字符	字符频度	哈夫曼编码
a	7	0
b	4	10
c	2	110
d	1	111

则源文件可以利用哈夫曼编码，编码为：0 10 0 10 0 10 0 10 0 0 0 110 110 111
可以计算出上述编码长度为24位，共需要3个字节（注：计算机以字节为单位，所以当存储哈夫曼编码的时候，若编码长度不是8的倍数时，最后一个字节需要补充为一个字节）

三、功能描述

对文本文件、图像文件重新编码。统计文件中256种不同字节重复的次数，以每种字节重复的次数作为权值(weight），构造一棵最多具有256个叶子结点的二叉树，使得带权路径长度达到最小，即Huffman树。给Huffman树上的所有叶子节点编码，形成的编码就是哈夫曼编码，类似如下图所示。

使用Huffman编码对原文件中的字节重新编码。重复次数较多的字节，Huffman编码的长度较短。原文件中每个字节的编码长度都是8位，而重复次数较多的字节的Huffman编码，长度比8位短得多，因此可能实现压缩。为了能够还原，保存压缩文件时应添加相应的文件信息，以达到解压的功能。

四、设计步骤

本方法需要通过读取文件，生成一棵带权的二叉树。树在程序中可以用链式、顺序结构两种方式。由于这里构造的Huffman树的叶子节点数为256，因此空间固定，这里介绍用顺序结构表示二叉树。

4.1 定义存储结构

主要是结构的定义及函数的声明、实现。定义一个结构体HuffNode表示二叉树的结点，记录每个结点的字节值、权值、父节点、左孩子、右孩子及该节点的哈夫曼编码，可参考下面的结构。

定义哈夫曼树结构，它是一个HuffNode结构体数组，定义如：HuffNode HuffTree[512]

数组存储这棵哈夫曼树的所有结点及逻辑关系，其中前256个元素存储Huffman树的叶子结点，其余存储的是非叶子结点。
说明：

• 一个字节可采用unsigned char表示，同时也可表示该字节位于数组的下标，如十六进制为0x00，转化成int即为0，故数组下标为0表示字节00的信息。
• 由于叶子结点为256个，非叶子结点为255，所以编码长度不可能超过256。

4.2 读写文件

本程序将使用二进制字节流的方式来读、写bmp文件。通过读取文件，统计256种字节出现的次数。文件正常打开后，可以逐字节读取文件数据，统计文件中出现的总字节数，及256种字节出现的次数，将其保存哈夫曼树相应的叶子结点权值（出现的频率）。

4.3 创建Huffman树

4.3.1 初始化

对树进行初始。由于Huffman树的结点不会超过512，可以采用顺序存储结构，初始数组HuffTree[512]中所有元素包括以下信息：

• b（节点表示的字节）:节点表示的字节值，初始可为’\0’。
• count（权值）：前面读文件时已统计，此处无需统计。
• parent（父节点）：此时哈夫曼树未建立，故设为-1。
• lchild（左孩子）：此时哈夫曼树未建立，故设为-1。
• rchild（右孩子）：此时哈夫曼树未建立，故设为-1。
• bits数组（结点对应的哈夫曼编码）：此时哈夫曼树并未建立，可不设置或bits[0]为’\0’。

4.3.2 选择叶子节点

图片中可能会出现256种字节，但可能某些字节并未出现，因此判断HuffTree数组前256个元素有权值的元素，让这些元素做为Huffman树的叶子结点，其它的颜色不参于树的生成，提高效率。

可采用排序，将HuffTree数组前256个元素按权值从大到小排序，从而找到有权值的元素个数，记录叶子节点的个数，得到哈夫曼树的总结点数。

4.3.3 生成Huffman树

每次选HuffTree数组中权值最小的两个元素，其中最小值作为树的左孩子，次小值做为树的右孩子，并将该树的根结点作为Huffuman树的非叶子结点。为了保存它们之间的逻辑关系，需保存以下信息：

• 设置左、右孩子的parent
• 将根结点的权值设置为左、右孩子权值之和
• 设置根结点的lchild、rchild

具体原理可参考如下讲解：

假设初始有4个节点{d,c,b,a}，其权值分别为{1,2,4,7}，初始时哈夫曼树存储结构：

A 、 在parent值是-1的结点中选取count值最小的两个结点进行合并，可以规定最小的合并为左孩子，第二小值合并为右孩子，合并生成的根结点的count值为左右孩子权值之和。

B、重复上述过程，直到所有结点合并成一棵树

（备注：从存储哈夫曼树的结构体数组的最终结果中可以看出，parent=-1，表示该结点是整棵树的根结点，lch=-1和rch=-1则表示该结点是叶子结点。）

4.4 Huffman编码

创建好哈夫曼树需将所有叶子结点（共n个）进行哈夫曼编码，即按顺序生成0x00~0xff中的n个字节（n<=256）对应的Huffman编码。哈夫曼树从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树分支编码为0，右子树分支编码为1，从根到每个叶子相应路径上的0和1组成的序列就是这个叶子节点的编码。

实现思想：可从叶子结点出发去判断分支编码为0或为1，当到达根结点时编码结束。初始时字符数组bits只有一个结束符。

举例：若文本文件存储信息：‘ABBCCCDDDD’， 原本文件每个字符存占一个字节，共10字节。 哈夫曼编码之后，若A的编码为 ‘100’ ，B 为 ‘101’ ，C为 ‘11’ ，D 为 ‘0’ ，则原文本信息哈夫曼编码为：10010110,11111110,000，若哈夫曼编码即为写入的二进制内容，此处只需要3个字节，达到压缩的效果。

4.5 压缩文件

4.5.1 压缩文件数据

写入压缩文件的内容不仅只是原文件字节对应的哈夫曼编码，还需要写入其它辅助信息。压缩文件的内容可参考如下图所示。

4.5.2 编码原文件

A、以二进制流方式只读打开原文件，逐字节读取文件中的数据，使用Huffman编码对原文件中的字节重新编码，获得压缩后的文件数据，保存在字符数组buf中。

B、拆分
buf数组保存字节对应的哈夫曼编码，因此重新编码后的数据可能是一个很长的字符串，因此统计buf当前的长度。分以下两种情况处理。

• 如果大于等于8，则进行拆分。每长度为8的字符串转成一字节，写入压缩文件。
• 如果小于8，若文件中还可以读取字节，则等待下一个字节的编码。否则，如果文件的最后一个字节已读取，buf的长度仍不足8，则补0凑满一字节，写入压缩文件。

举例：A的编码为 ‘100’ ，B 为 ‘101’ ，C为 ‘11’ ，D 为 ‘0’ ，读取原文件的内容“ABBCCCDDDD”
读取A，得到buf=”100”，不够8位，读取B，buf=”100101”，不够8位,继续读入B，buf=”100101101”，此时buf的长度超过8位，则需要将buf的前8个字符”10010110”转换成二进制10010110，将8位二进制写入文件。之后buf=”1”（即舍去已处理的8位），等待读取原文件的其他内容，同样处理。

C、字符串转码
将长度为8的字符串转成相应的8位的二进制。利用左移位<< 操作完成字符串转成相应的二进制。

举例：用一个unsigned char类型的变量c表示一个8位二进制，初始为00000000，根据字符串的编码进行相应处理，若读入的编码是1，则将c左移一位并与1按位或，若读入的编码是0，则直接将c左移一位。
举例：如字符串“1001001”转成二进制1001001（一字节）

D、写入压缩文件
把长度为8的编码转成二进制（一个字节）写入压缩文件。

E、补0
当文件读完，buf中的内容不足一个字节，则需要补0，再对哈夫曼编码位操作，把最后一个字节写入压缩文件。

4.5.3 写入剩余文件信息

上一步已把原文件所有字节对应的Huffman编码写入压缩文件。接下来写入的文件信息包括压缩后文件的长度（字节数），叶子结点的数目，每个字节的值、对应的编码长度及相应的huffman编码。
注意：每次写入都是字节的n倍，因此，huffman编码长度不为8的倍数时，则补足0。

举例：比如某字节编码若为110，则补0变成11000000
　　　编码若为01010101 10，则补0变为01010101 10000000

具体步骤如下：

1. 设置好压缩文件指针，并写入文件长度，节点总数信息
2. 写入huffman树中的n个叶子结点的信息，包括每个字符值、对应的哈夫曼编码位数及哈夫曼编码
3. 计算压缩百分比

4.6 解压文件

经过前面的开发，.bmp的图片文件已经压缩成了.huf文件，之后设计解压文件步骤

4.6.1 文件操作

以二进制方式读取.huf文件，打开写入的解压缩文件。

4.6.2 扫描文件信息生成Huffman树和Huffman编码表

A、读取文件信息，并将文件指针定位好为下面构造树做准备。

B、重构Huffman树及Huffman编码
利用压缩文件中的n个叶子节点的信息重新构造树。在此过程中每次取出一个字节，需要将一个字节转化为8个“01”字符。可以使用itoa函数进行转换，但不足8位要进行补0。

4.6.3 将Huffman编码转换成对应的字符完成解压

A、根据编码长度将结点排序
由于Huffman编码的长度不一，为了能保证最长的Huffman编码能正确转换，因此先求出最长的Huffman编码。当取出的字符个数大于等于最长的编码长度，保证可以转换。这里利用排序算法将前n个结点排序，编码短的在前面，最长的编码在HuffTree数组下标为n-1的位置。

B、定位文件指针，读取压缩文件中原文件的对应的Huffman编码信息。
每次读取一字节转成8个“01”字符后暂存在字符数组bx中，直到bx的长度大于等于huffman编码的最大长度，才将相应的编码转化成相应的字节值。
需要注意的是：这里读取一字节利用itoa函数转换，如长度不足8位要在前面补足0（同上）。

C、将Huffman编码转换成对应的字节。
当暂存huffman编码的bx的长度大于等于huffman编码的最大长度则可以在已生成的Huffman树中解码，得到编码对应的原字符。直到所有的huffman编码都比较完，完成解压缩。

五、结果展示

左侧为源文件，中间是压缩之后的文件，右侧是完成解压之后的文件