哈弗曼压缩与解压的原理及对象化实现

哈弗曼压缩与解压的原理及对象化实现2014-05-24 iteye cq520这一次主要是跟大家探讨一下哈弗曼压缩的原理及实现，由于过程化的实现更加容易理解也更加直观，所以这里首先会分步骤跟大家讲解一下哈弗曼压缩的具体实现方法，然后再与大家分享一下对象化的实现。

首先，我们要知道文件为什么能压缩？

文件是由字节所组成的，一个字节的长度为8位，所以最多只存在256种字节，而一个文件中一般存在许多相同的字节，我们把相同的字节以一种更加精简的方式表示，就完成了我们所说的压缩。

哈弗曼压缩的原理是什么？

上次博客中提到了哈弗曼编码，但是只是粗略的带过了，这一次举一个具体的例子来更加直观的说明哈弗曼压缩的原理。

假设一个文件中是这样的一串字节ABBCCCDDDD，那么这个文件的大小就是10个byte。那么接下来就是我们的哈弗曼压缩的第一步：

一．读取文件，统计每一种字节出现的次数，将出现的字节种类与对应的次数保存起来（可采用数组或者是HashMap，或者是其他的数据结构）

保存完了之后干什么呢？？当然是构建哈弗曼树呀。第二步：

二. 利用得到的字节与对应的频次构建哈弗曼树，需要注意的是，构建树的时候是以字节出现的频次作为我们的评判标准，出现次数越多的放在越上层。

比如我们上面所说的这个文件，它所构成的树应该是这样的：

我们现在得到的树还处于未编码的状态，那么第三步毫无疑问就是我们所说的编码了：

三. 将得到的哈弗曼树进行编码

编码之后的树就变成这个样子了（采取向左编1的方式）：

到了这一步其实我们的压缩就已经完成一半了，听到这里，你可能纳闷了，不对呀，不是还没开始么？？