基于huffman树的文件压缩工具

通过对文件压缩的内部原理的学习，让我现在也有了想要自己实现一个文件压缩工具的想法。那么，想要实现这样一个工具，首先我们先梳理一下，需要用到那些知识点。

1.什么是文件压缩？为什么要进行文件压缩

文件压缩就是通过某一种机制让文件变得更小，并且还能够通过对应的方式进行还原，如果不能进行还原，那么压缩就没有意义了。压缩的目的就是为了让文件的存储更加节省空间，也可以便于传输。

2.文件压缩的分类？

通常我们把文件压缩可以分为两类：无损压缩和有损压缩。

无损压缩：解压缩之后的文件与源文件完全相同。

有损压缩：解压缩之后并不能够做到与源文件完全相同。比如将一部高清电影压缩再解压缩之后，画质稍微有点影响，但是损伤程度在可接受范围内，这样的有损压缩我们一般也是可以接受的。

3.如何实现文件压缩？

比如对于一个下面的文本文件，里面写入ABBBCCCCCDDDDDDD这样的内容，由于每个字符都是以1字节存储的，文本就是16个字节。而每个字节占据8比特位，如果我现在通过两个字节0和1的组合根据某种编码规则，将每个字符转换成2个或3个比特位的形式来标记，这就可以直接实现将文本的内容进行压缩了。

这里我们选取的编码方式是不等长编码，对比两种编码方式，我们可以知道，等长编码的思路更加简单，在小文件中找编码规则比较简单，但是在大文件中通常就很难找到一种适合的编码规则了。而不等长编码，一般来说，编码形式由于不固定，因此想要**也更加安全。

这里我们的编码规则，是通过huffman树来实现的，我们将所有字符出现的次数都设定成huffman树的权值存放在叶子节点，再把左子树都设成0，右子树都设定成1.就可以找出对应的huffman编码。

这里既然用到了huffman编码，我们就必须再了解一下huffman树的规则。

所谓的huffman树，就是从二叉树的根结点到二叉树中所有叶结点的路径长度与相应权值的乘积之和为该二叉树的带权路径长度WPL。在所有的由相同权值形成的二叉树森林里，将带权路径最小的二叉树称为Huffman树。这样我们创建一个huffman树，通常就是将权值最大的叶子节点，想办法放到更靠近根节点的位置。

而创建一棵huffman树，我们是这样的，

1. 由给定的n个权值{ w1, w2, w3, … , wn}构造n棵只有根节点的二叉树森林F={T1, T2 , T3, … ,Tn},每棵二叉树Ti只有一个带权值wi的根节点，左右孩子均为空。
2. 重复以下步骤，直到F中只剩下一棵树为止，在F中选取两棵根节点权值最小的二叉树，作为左右子树构造一棵新的二叉树,新二叉树根节点的权，值为其左右子树根节点的权值之和，在F中删除这两棵二叉树，把新的二叉树加入到F中

那么，对于我们这个这个项目的实现，我们就可以分为以下几个模块：

1.压缩
   1. 打开被压缩文件，获取文件中每个字符串出现的总次数。
   2. 以每个字符出现的总次数为权值构建huffman树。
   3. 通过huffman树获取每个字符的huffman编码。
4. 读取源文件，对源文件中的每个字符使用获取的huffman编码进行改写，将改写结果写到压缩文件中，直到文件结束。

2.压缩文件的格式
假设按照上述操作已经对源文件压缩完毕，怎么解压缩？解压缩之后文件的后缀怎么与源文件保持一致？因
此：压缩文件中除了保存压缩数据外，还必须保存解压缩所需的信息。压缩文件格式：

3. 解压缩
    1. 从压缩文件中获取源文件的后缀
    2. 从压缩文件中获取字符次数的总行数
    3. 获取每个字符出现的次数
    4. 重建huffman树

 5.解压压缩数据

       a. 从压缩文件中读取一个字节的获取压缩数据ch
       b. 从根节点开始，按照ch的8个比特位信息从高到低遍历huffman树：该比特位是0，取当前节点的左孩子，否则取右孩子，             直到遍历到叶子节点位置，该字符就被解析成功，将解压出的字符写入文件，如果在遍历huffman过程中，8个比特位已经        比较完毕还没有到达叶子节点，从a开始执行
       c. 重复以上过程，直到所有的数据解析完毕

6.测试
1. 用不同格式的文件测试程序，对比是否正确(可使用BeyondCompare工具)
2. 测试huffman编码的压缩率
3. 文本文件与二进制格式文件的压缩比率
4. 测试程序的压缩性能
5. 对压缩文件进行二次压缩，多次压缩，给出结果

这里是我自己的实现,我把它放在GitHub上了，大家可以了解一下：https://github.com/sunjiyuansjy/myproject_FileCompress