基于Huffman编码译码的文件压缩器

最开始是两个周之前帮同学写的一个小工具,一直没有完善和收尾,趁这次五一假期,终于弄了出来。开始时同学的要求是基于二进制Huffman编码,对bmp图片进行译码、解码,从而实现压缩和解压缩的功能。我在写的过程中对这份要求进行了大大的扩展,已经能够实现对任意大小(内存等硬件限制除外)的文件,并且任意格式的文件而不只限于bmp文件,进行压缩、解压缩。界面如下:

huffman-encode-decode

开发工具选的是Java,后来才感受到,如果换成c或者c++来写,在存储时,大概会省去许多麻烦。因为,Java毕竟是擅长开发一些比较大的应用的,对于比较底层的二进制位存储,是不支持的,只有自己花了点时间写了一个字节缓冲,来实现二进制存储。

收获也不小,首先对Java的IO有了更深的实际了解,以前总是靠C、V大法贴来的东西怎么说也不如自己研究的可靠,然后就是刚才提到的8位二进制缓冲存储,这一点是我没有意料到的,现在想想,很像计算机网络中的IP打包吧,呵呵,这想法真不错。对于Huffman树,使用了将近压缩极限的存储方法,而至于Huffman编译码本身倒是没有什么含金量。将一些核心思想记录一下:

  1. Huffman树编译码:最优二叉树,没什么可谈的
  2. 编码后文件存储结构:分成存储树和存储编码两部分存储树:从00到FF依次存储其Huffman编码长度和Huffman编码,例如,对于4F这个字符,其Huffman编码为“01110000111100”,共14位,则存储结构为
    00001110 01110000 11110000
    第1字节,存储位数14,即二进制“00001110” 第2字节,存储前8个Huffman编码 第3字节,存储下8个Huffman编码,不足8位,后缀补0

    存储字符编码:读入一个字符,遍历Huffman树得到其Huffman编码后,写入文件,同样,设定一个缓冲字符串,让所有Huffman编码都通过这个缓冲字符串,同时不断的将缓冲字符串分割成8位并转换成16进制整数,依次存储入文件的每个字节中。

  3. 恢复Huffman树及恢复文档:分成恢复Huffman树和译码两部分,同样设定缓冲结构,与存储时非常类似
  4. 解决了一个困让很久的Swing线程疑惑:Swing中事件被触发时,并不是立刻执行,而是被放入了一个Swing事件队列中,等待Swing线程处理。因此,我在事件中启动了一个新的进程来处理与UI无关的事件,这样,让UI和其他代码分开执行,就不会产生那种“卡死”的效果了。

下面表格统计了压缩效率,随机找的文件,WinRAR采用rar格式最优压缩,比较有可参考性。

文件属性 随机bmp图片 普通doc文档 普通txt文本
此工具压缩时间 7s左右 瞬间 瞬间
此工具解压缩时间 4s左右 1s左右 瞬间
原始文件大小 571k 57k 6k
此工具压缩后大小 555k 47k 5k
WinRAR压缩后大小 471k 37k 3k

可以看出,进过这个小工具编码过后,文件确实有了一定的压缩比率,但是并不很理想。原因我考虑在于,这个工具已经几乎实现了二进制huffman编码压缩的极限,存储结构应该几乎没有再压缩的空间了。所以,相比较winrar高压缩比来说,这应该是huffman编码本身的局限性了。而从时间上考虑,比较挫,用了比较长的时间,可能,一些写的思路还有改进的空间吧,或者,也许就不应该用Java来写?

这个小工具做的时候更多的精力放在了功能上,没有考虑太多UI和极端的bug,因为这不是我这次做的重点。源文件和打包后的工具都附后,这个程序遵从GPL许可,感兴趣的话可以下来试用或指教^_^

JAR程序(需要JRE运行)及源码下载地址:
http://code.google.com/p/leon/downloads/list

Leave a Reply

2 Comments on "基于Huffman编码译码的文件压缩器"

avatar
newest oldest
Cherrot

学习了! 好牛X~~

lzh
lzh

:em00: 好厉害啊