用 Huffman 树实现文件压缩并解压

一、前言

如果你学习数据结构,就一定会学到Huffman树,而Huffman编码实际上上就是zip压缩的核心部分,所以,如果已经学习了Huffman树,为何不尝试写一个压缩程序出来呢?

如果你没有学习Huffman树,那咱们就一起先学习一下Huffman树吧。

二、Huffman 树压缩文件

定义:Huffman树,又称为最优二叉树,是加权路径长度最短的二叉树。

建立:

这样建立的树,保证所有数据成员都在叶子节点上,且数越小,离根节点越远,越大,离根节点越近,那么这样的特点应用于压缩中是很关键的,我们可以让出现次数少的字符编码长一些,次数多的字符编码短一些。接下来我们看看压缩的步骤吧~

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

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

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

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

3>得到Huffman编码

怎么得到呢?向右为1,向左为0,就是这么简单,我画图示意一下:

原本用一个char表示的字符,现在只占了几个位,这就是为什么能将文件压缩。

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

写入的时候,满8个位写进去,如果最后不足8个位,先补齐,解压的时候要注意,解压到源文件字符数的时候停止即可。源文件的总字符数可以在第一次遍历统计出现的字符个数时统计,还有一种方法就是,仔细观察Huffman树就知道,它的根节点的大小,其实就是所有叶子节点相加的和。所以,根节点的大小就是源文件里所有字符出现的总次数。

至此,压缩就结束了。

但是,怎么解压缩呢?解压缩至少也得已知这样的一颗树才行啊,所以,我们在压缩完成后要建立一个配置文件。

5>建立配置文件

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

三、解压缩

1>读取配置文件,重新构建Huffman树

2>读取压缩文件

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

解压到这里成功。可以先使用小文件测试,若没有问题则找个大点的文件,还有各类格式的文件都拿来压一压测一下。

四、我遇到的问题

1>编译时不通过,一大堆的错误,我找了半天!最后发现是一个很简单的问题,我的Huffman树使用的是C++模板实现的,模板不能分离编译,而我在压缩时建立Huffman树是在另一个文件中进行的,所以编译不通过。

解决方法:.h后缀改成.hpp,重新包一下头文件ok。

2>文件的打开方式。这里打开文件一定要用二进制形式,”wb”,”rb”.因为二进制打开和文本打开其实是有区别的。文本方式打开,会对‘n’进行特殊处理,那如果这个字符本身就是’n’.这就会出现问题,所以使用二进制打开,特点:不进行任何处理,是什么就是什么。

3>压缩后解压缩的图片打不开,经过我反复查找,终于发现是配置文件里对‘’的处理问题,我在写配置文件起初是用一个string把字符和它出现的次数连接起来放进去。比如:a,3   这样带来的问题是  ,200  写的时候是以c字符串的形式写的,所以遇见”就终止了,那么在解压缩的时候就会出问题。

解决方法:先把字符放进去,再把剩下的构建成string对象放进去。

五、源码

1>Huffman树

2>压缩和解压缩

最后,文件大了之后怎么对比两个文件是否一致呢?我用的是beyond Compare这个软件,很方便,能对比各种类型的文件。

2 3 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部