基于Huffman编码的压缩技术的Java实现

摘要：当前，广泛采用的无损压缩技术主要有2种，一种是短语式压缩，另一种是编码式压缩。本文介绍采用java编程语言利用huffman算法实现文件的压缩功能，是实现的编码式压缩技术。

关键词：压缩技术；霍夫曼编码；java

中图分类号：TP393.09文献标识码：A文章编号：1009-3044(2008)11-20349-02

在某一个特定的文件系统中，某些字符可能会累计重复出现多次。编码压缩技术采用的原理就是统计这些字符出现的频率，并根据频率的高低对该字符进行编码。这样，处理全部信息的总码长一定小于实际信息的符号长度，从而达到压缩的目的。

本文用java实现的Huffman编码压缩技术是实现的编码式压缩技术。

1 Huffman编码原理

霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。 霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。

构造Huffman编码的可以先将原始数据构造成一棵带权值的Huffman树。步骤如下：

（1）将信号源的符号按照出现概率递减的顺序排列。

（2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。

（3）重复进行步骤1和2直到概率相加的结果等于1为止。

（4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。

（5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。

例如电文“ABACCDA”,有4种字符。可以用两位二进制代码：00，01，10,11分别表示A,B,C,D。译码为”00010010101100”。这样的二进制串长度为16位。比原始的字符串长度8*8=64远小。若采用Huffman编码，则得：A:1; B: 000 C:01；D:001。译码字符串为：1000101010011。长度为13位，比16又小。对于应用文档来说，一般会有大量词汇重复出现，这样两者之间的差距也随着文件的大小与词汇重复出现的频率而越来越高。

2 用java实现huffman压缩算法的程序流程

3 程序实现

根据上面的流程以及huffman算法的原理，有如下的程序类组织结构：

3.1 程序相关类

Frame类：框架类，用于实现程序的界面，其中还包括文件的读入，统计字符的频率，各字符按频率排序等函数

HuffmanNode类：利用Huffman算法的特点，进行Huffman数据结构定义，如图2。

BuildHuffman类：初始化Huffman树，并得到编码。其中包括生成Huffman树结构的函数（具体实现参看附程序），编码函数，写二进制文件函数，解码函数等，结构参看图3。

3.1.1 在Frame类中，可能会遇到的问题

在图1的步骤1中（也就是在统计字符串频率时），对于简单的英文字母与数字字符来说，没有什么难度。而对于统计中文字符或其他一些由2个字节构成的字符时，可能会遇到某些问题。因为在对文件进行遍历统计频率时，需要对读入字符的步长加以控制。如果是单字节的字母，则步长为1，而如果是2个字节的字符，步长就需要相应的改为2。这样，就存在一个步长控制问题了。根据目前国际通用的Unicode代码表示的汉字存储区位，位于4E00~9FFF的为中日韩文字，其他双字节字符也有相应固定的区位。有这样的unicode编码条件，问题就可能解决了：在读入字符时，只需要判断读入的字符是否是位于双字节字符的存储区中。而对于java1.5以上的版本中，character类中提供了isHighSurrogate函数。该函数能判断能判断所读入的字符是否是双字节字符的前半部分。这样就能有效解决读入字符步长控制问题。从而正确统计各种类型的字符出现频率（代码可以见附表）。

3.1.2 构造HuffmanNode类

HuffmanNode是一个定义的典型的Huffman型的数据结构。具体形式如图2。

图2就是即将构造的Huffman结构。接下来需要将按频率已经排好序的各字符初始化成该类的实例（具体方法参见上述1中的原理与附录中的程序片段），构造一棵带有各字符符号及出现频率的Huffman树。这样，从树根开始遍历各个叶子结点。按照每经历一次左孩子取0，经历一次右孩子取1的方法，得到各个叶子接点的Huffman编码。并将该编码存入该类实例的变量：bh中，以备解码时或其他需要（编码函数见附录的Encode函数）。

3.1.3 BuildHuffman类

上面生成Huffman树对于本程序来说是关键的一步。现在假设已经获得各字符的Huffman编码，并将待压缩文件所有字符都化为了“01”类型的Huffman编码并存入变量之中了。接下来的工作就是将写编码了。需要注意的是在写入文件的编码时，需要写入二进制代码。比如某个字符“A”对应的编码是“001”。如果直接写入字符类型的“001”，这不但没有起到压缩的效果，反而比原字符所占内存增加了2倍。所以必须写入二进制类型的“001”。此时，问题出现了。大家知道，1.6及以下的java版本并不能直接将“001”转化成简单的“001”二进制序列。那么，采取什么样有效的措施才能达到压缩的效果呢。其实，java中DataOutputStream类中的write函数，可以写入byte类型的数据。这样，解决问题的方法就在于将字符型的“01”序列转化为Byte型的数据了。有了这个思想，我们可以将带压缩的编码以8位为步长，将其对应转化为byte型的数据，存入一个byte的数组中去。这样，每位8字节的“01”序列就压缩成为了最多8位的长度了，从而间接实现了压缩的目的。这样做，在解压的时候，需要重新将这些byte数还原成01序列，然后再将01序列去与对应的Huffman树去匹配，还原得到相应的字符。

4 压缩效率分析

在程序运行过程中，对系统资源的大量占用主要在读/写文本以及程序中其他一些不超过2层的循环语句的使用。系统执行时间在程序结构上应小于为O(N2) 其中N是待压缩文件中字符的个数，但实际上，写文件的时间耗费较大。经过压缩的文件，在重复量不同的情况下，平均水平超过50%。对于文件中重复字符较多的文件，压缩效率明显较好。据多次统计：文件所占空间为原文件的25%左右。而对于重复量较小的文件，压缩效果不太明显，但也能达到原文件的60%左右。

5 部分java源程序

6 结束语

压缩技术作为当前网络传输与存储的一种必要的数据处理技术现在已经比较成熟，而本文所采用的Huffman算法实现的编码压缩技术也是部分压缩工具所采用的算法。本文从java编程实际出发，提出了一些可能遇到的问题与解决方案。其实，如果做进一步拓展，我们还可以将出现频率较高的部分词汇进行编码，这样压缩的效率将进一步提高。但可以肯定的是，程序运行的时间复杂度和空间复杂度也会相应提高。

参考文献：

[1] Thomas H.Cormen ,INTRODUCTOIN TO ALGORITHMS[M],北京:高等教育出版,2006.

[2] 郑丽,王言行,马素霞. Java语言程序设计[M],北京：清华大学出版社 ,2006.

[3] 严蔚敏 吴伟民，数据结构（C语言版）,人民邮电出版社 2000.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文