 |
| 使用Huffman算法对文本进行压缩与解压缩 （Java语言实现） |
|
Jagie 原创 更新：2008-04-09 15:38:36 版本: 1.0
|
|
Huffman算法简介
Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码，对于使用频率越高的字符，其编码也越短。但是任何2个字符的编码，是不能出现向前包含的。也就是说字符A的编码的前段，不可能为字符B的编码。经过编码后的文本文件，主要包含2个部分：Huffman码表部分和压缩内容部分。解压缩的时候，先把Huffman码表取出来，然后对压缩内容部分各个字符进行逐一解码,形成源文件。
由此可见，使用Huffman算法的关键是形成Huffman码表。怎样才能生成一个“使用频率越高的字符，其编码也越短”的码表呢?这里就要用到Huffman树的数据结构。当把一棵Huffman树生成后，码表也就生成了。以下举例说明，假定我们的原始文本为"abcbbcccc"
Huffman树生成步骤:
1.扫描源文件，对字符频率进行统计。
对于我们的样例，统计结果是:a:1 b:3 c:5 (按频率升序排列)
2.从上述队列中取出频率最低的2个节点，合并成一个频率为2节点频率之和的树枝节点X，加入到原队列中，加入后，继续保持队列按频率升序排列.
3.重复步骤2，直到队列中只有一个节点。
4.这样，我们就形成了一棵Huffman树。叶子节点为字符，从树根节点到叶子节点的路径即为该字符的Huffman编码。从一个节点导航到其左孩子，该段路径为0，导航到右孩子，该段路径为1.所以，a字符的编码就是00,b字符的编码为01,c字符的编码为1，符合"使用频率越高的字符，编码越短"的要求。理论论证过程见<算法导论>P233
5.Huffman码表生成后，原文本"abcbbcccc"就变成了0001101011111的位串，按每个字符占用2个byte计算，大小由原来的18个字节(9*2),共144个bit,变成了13个bit,2个字节。达到了压缩的目的。
解压缩过程:
解压缩也分成2部分进行，首先是根据压缩文件中的Huffman码表，在内存中生成一棵Huffman树，然后，根据Huffman树，对压缩内容进行解压缩。比如如果压缩内容为位串0001101011111，那么从树根节点起，因为第一个bit为0，先转向左子树，第二个bit为0,再转向左子树,到达叶子a,所以解码出来的第一个字符就是a,每次解压一个字符，都从根节点起，根据bit流，向左或向右转，直到到达叶子节点，也就是解压出来的字符。一直重复此过程，直到所有的字符都被解压缩。
压缩文件格式
使用Huffman压缩算法对文本文件压缩后，就形成了一个压缩文件，该压缩文件包含2部分，一部分为Huffman码表，也就是Huffman树，第二部分为根据码表生成的内容位串。如何设计Huffman树的存储格式呢?本文采用从上到下，从左到右分层遍历节点，顺序存储的方式。如下图:
也就是说，对于前述的Huffman树，其持久化形式为:0xfffe 0xfffe 0x0063 0x0061 0x0062,其中0xfffe代表树枝节点,而0x0061,0x0062,0x0063分别为a,b,c的Unicode码。因为所有的树枝节点的值都是0xfffe，所有树枝节点都有2个孩子，节点排列方式是按从上到下，从左到右分层排列，所以能根据此持久化字节数组，把Huffman树在内存中重新生成。
另外为了升级版本，嵌入了magic number和version。
完整工程下载
本文涉及到的完整的eclipse工程，可以从这里下载。注:内含测试样例《平凡的世界》文本文件，体积较大，请使用下载工具下载。另外，本程序中采用了泛型，请在至少在JDK1.5版本上编译运行。
代码简要说明
1.HuffmanTextEncoder类完成压缩功能，可直接运行，压缩测试用文本文件。
2.HuffmanTextDecoder类完成解压缩功能，可直接运行，解压缩 压缩后的文本文件。
3.BitReader,工具类，实现对BufferedInputStream的按位读取。
4.BitWriter,工具类，实现按位写入的功能。该类来自网络。
5.MinHeap<T> ,模板工具类，实现了一个最小堆。生成Huffman树时使用。
压缩效果
使用本程序对《平凡的世界》做压缩测试，压缩前为文本文件，大小为1.7M,压缩后为二进制文件，大小接近1M（988,817byte）,而zip压缩后体积为920,997byte,比zip差，压缩文件存储格式待改善。另外，因为从Huffman压缩算法的原理可知，该算法对字符重复率高的文本最有效，比如长篇小说或者英文小说。
作者信息
Jagie，移动开发爱好者，可以通过chen_cwf@163.com与他联系。本文来源于 http://chencwf.googlepages.com/huffman
|
|
|
评论人：liuchenyu
|
发表时间: Wed Apr 09 17:45:19 CST 2008
|
|
顶顶
|
|
|
评论人：useryu
|
发表时间: Mon Apr 14 16:03:59 CST 2008
|
|
喜欢<平凡的世界>
|
|
|
评论人：laonongfu
|
发表时间: Mon Apr 14 21:03:39 CST 2008
|
|
不错哦！谢谢啦！
|
|
|
评论人：laonongfu
|
发表时间: Mon Apr 14 21:04:36 CST 2008
|
|
觉得自己又学到些东西！谢谢了！
|
|
|
评论人：Jagie
|
发表时间: Tue Apr 15 09:09:25 CST 2008
|
|
如果你看不到图片，也下载不了源码，请设置浏览器代理访问，因为这些资源都放在google pages上，访问google pages有时需要代理
|
|
|
评论人：zf534685796
|
发表时间: Thu Apr 17 20:46:02 CST 2008
|
|
hhujuyi
|
|
|
评论人：0505010218
|
发表时间: Wed Aug 20 00:13:28 CST 2008
|
果然,看不到图片也下不了代码.
为了看下下东西还有去弄什么代理?可恶...
|
|
|
评论人：edwards0307
|
发表时间: Thu Aug 21 12:18:15 CST 2008
|
|
终于见到可以实践的东西了呀
|
|
|
|
|
|
13 
0
