File-compression

利用Huffman编码可对任意文件（包含图片、视频、音频）进行压缩和解压缩。

---

概述：

• 利用Huffman编码可对任意文件（包含图片、视频、音频）进行压缩和解压缩。

使用技术：

• 运用到的数据结构：Heap堆、Huffmantree哈夫曼树、Huffmancode哈夫曼编码

思想：

• 压缩文件时利用小堆建立哈夫曼树，依据建立的哈夫曼树产生哈夫曼编码。利用哈夫曼编码对文件进行压缩，产生压缩文件和配置文件。

---

压缩

1. 统计要压缩的文件中字符出现的次数。

   • 遍历一遍文件，将字符出现的次数统计在一个结构体数组里，数组里包含字符，字符出现的次数，对该字符的编码。

2. 用得到的数组构建一个Huffman树。

   • 因为每次要取最小值，所以这里考虑建立一个小堆。

3. 得到Huffman编码

   • 向右为1，向左为0

4. 向压缩文件里写入Huffman编码。

   • 写入的时候，满8个位写进去，如果最后不足8个位，先补齐，解压的时候要注意，解压到源文件字符数的时候停止即可。源文件的总字符数可以在第一次遍历统计出现的字符个数时统计，还有一种方法就是，仔细观察Huffman树就知道，它的根节点的大小，其实就是所有叶子节点相加的和。所以，根节点的大小就是源文件里所有字符出现的总次数。至此，压缩就结束了。但是，怎么解压缩呢？解压缩至少也得已知这样的一颗树才行啊，所以，我们在压缩完成后要建立一个配置文件。

5. 建立配置文件

   • 配置文件里要存储源文件字符及出现的次数。有了这样的配置文件，就可以再次构建Huffman树！

解压缩

1. 读取配置文件，重新构建Huffman树

2. 读取压缩文件

   • 由压缩时的原理可知，此时读到1指针向右移动，0向左移，到叶子节点停下，将字符还原。不停的循环，直到文件结束或者总字符数变为0.这里就能体现出，Huffman压缩是一种无损的压缩，如果代码没有问题，它会原原本本的还原源文件。