基于Huffman编码译码的文件压缩器
最开始是两个周之前帮同学写的一个小工具，一直没有完善和收尾，趁这次五一假期，终于弄了出来。开始时同学的要求是基于二进制Huffman编码，对bmp图片进行译码、解码，从而实现压缩和解压缩的功能。我在写的过程中对这份要求进行了大大的扩展，已经能够实现对任意大小（内存等硬件限制除外）的文件，并且任意格式的文件而不只限于bmp文件，进行压缩、解压缩。界面如下：
开发工具选的是Java，后来才感受到，如果换成c或者c++来写，在存储时，大概会省去许多麻烦。因为，Java毕竟是擅长开发一些比较大的应用的，对于比较底层的二进制位存储，是不支持的，只有自己花了点时间写了一个字节缓冲，来实现二进制存储。
收获也不小，首先对Java的IO有了更深的实际了解，以前总是靠C、V大法贴来的东西怎么说也不如自己研究的可靠，然后就是刚才提到的8位二进制缓冲存储，这一点是我没有意料到的，现在想想，很像计算机网络中的IP打包吧，呵呵，这想法真不错。对于Huffman树，使用了将近压缩极限的存储方法，而至于Huffman编译码本身倒是没有什么含金量。将一些核心思想记录一下：
- Huffman树编译码：最优二叉树，没什么可谈的
- 编码后文件存储结构：分成存储树和存储编码两部分
存储树：从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进制整数，依次存储入文件的每个字节中。
- 恢复Huffman树及恢复文档：分成恢复Huffman树和译码两部分，同样设定缓冲结构，与存储时非常类似
- 解决了一个困让很久的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
- At 2008.05.14 18:31, lzh said:
好厉害啊
