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

本栏目责任编辑：贾薇薇计算机工程应用技术

基于Ｈｕｆｆｍａｎ编码的压缩技术的Ｊａｖａ实现

陈旭辉，范肖南，巩天宁

（安徽理工大学，安徽淮南２３２００１）

摘要：当前，广泛采用的无损压缩技术主要有２种，一种是短语式压缩，另一种是编码式压缩。本文介绍采用ｊａｖａ编程语言利用Ｈｕｆｆｍａｎ算法实现文件的压缩功能，是实现的编码式压缩技术。

关键词：压缩技术；霍夫曼编码；ｊａｖａ

中图分类号：ＴＰ３９３．０９文献标识码：Ａ文章编号：１００９－３０４４（２００８）１１－２０３４９－０２

ＣｏｍｐｒｅｓｓｅｄＴｅｃｈｎｏｌｏｇｙＢａｓｅｄｏｎＨｕｆｆｍａｎＣｏｄｅｂｙＪａｖａ

ＣＨＥＮＸｕ－Ｈｕｉ，ＦＡＮＸｉａｏ－Ｎａｎ，ＧＯＮＧＴｉａｎ－Ｎｉｎｇ

（ＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｈｕａｉｎａｎ２３２００１，Ｃｈｉｎａ）

Ａｂｓｔｒａｔｃｔ：Ｔｈｅｒｅａｒｅｔｗｏｍａｉｎｌｙｗａｙｓｉｎｕｎｌｏｓｓｉｎｇｃｏｍｐｒｅｓｓｅｄｔｅｃｈｎｏｌｏｇｙｎｏｗａｄａｙｓ：ｏｎｅｉｓｓｈｏｒｔ－Ｖａｃａｂｕｌａｒｙ－Ｃｏｍｐｒｅｓｓ，ｔｈｅｏｔｈｅｒｉｓＥｎ－ｃｏｄｉｎｇ－Ｃｏｍｐｒｅｓｓ．ＴｈｉｓａｒｔｉｃｌｗｉｌｌｍａｎｉｆｅｓｔｔｈｅｃｏｍｐｒｅｓｓｅｄｔｅｃｈｎｏｌｏｇｙｏｆＵｓｉｎｇＨｕｆｆｍａｎａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｂｅｌｏｎｇｓｔｏＴｈｅＥｎｃｏｄｉｎｇ－Ｃｏｍｐｒｅｓｓｅｄ－Ｔｅｃｈｎｏｌｏｇｙ．

Ｋｅｙｗｏｒｄｓ：ＣｏｍｐｒｅｓｓｅｄＴｅｃｈｎｏｌｏｇｙ；ＨｕｆｆｍａｎＣｏｄｅ；Ｊａｖａ

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

本文用ｊａｖａ实现的Ｈｕｆｆｍａｎ编码压缩技术是实现的编码式压缩技术。

１Ｈｕｆｆｍａｎ编码原理

霍夫曼（Ｈｕｆｆｍａｎ）编码是１９５２年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。

构造Ｈｕｆｆｍａｎ编码的可以先将原始数据构造成一棵带权值的Ｈｕｆｆｍａｎ树。步骤如下：

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

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

（３）重复进行步骤１和２直到概率相加的结果等于１为止。

（４）在合并运算时，概率大的符号用编码０表示，概率小的符号用编码１表示。

（５）记录下概率为１处到当前信号源符号之间的０，ｌ序列，从而得到每个符号的编码。

例如电文“ＡＢＡＣＣＤＡ”，有４种字符。可以用两位二进制代码：００，０１，１０，１１分别表示Ａ，Ｂ，Ｃ，Ｄ。译码为”０００１００１０１０１１００”。这样的二进制串长度为１６位。比原始的字符串长度８＊８＝６４远小。若采用Ｈｕｆｆｍａｎ编码，则得：Ａ：１；Ｂ：０００Ｃ：０１；Ｄ：００１。译码字符串为：１０００１０１０１００１１。长度为１３位，比１６又小。对于应用文档来说，一般会有大量词汇重复出现，这样两者之间的差距也随着文件的大小与词汇重复出现的频率而越来越高。

２用ｊａｖａ实现ｈｕｆｆｍａｎ压缩算法的程序流程

图１程序流图

３程序实现

根据上面的流程以及ｈｕｆｆｍａｎ算法的原理，有如下的程序类组织结构：

３．１程序相关类

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

ＨｕｆｆｍａｎＮｏｄｅ类：利用Ｈｕｆｆｍａｎ算法的特点，进行Ｈｕｆｆｍａｎ数据结构定义，如图２。

ＢｕｉｌｄＨｕｆｆｍａｎ类：初始化Ｈｕｆｆｍａｎ树，并得到编码。其中包括生成Ｈｕｆｆｍａｎ树结构的函数（具体实现参看附程序），编码函数，写二进制文件函数，解码函数等，结构参看图３。

３．１．１在Ｆｒａｍｅ类中，可能会遇到的问题

收稿日期：２００８－０２－２７

作者简介：陈旭辉（１９７９－），男，湖南益阳人，硕士研究生，研究方向：数据库方向；范肖男（１９５６－），男，安徽合肥人，教授，研究方向：矿物加工方面的教学与研究；巩天宁（１９８２－），男，安徽泗县人，研究方向：单片机技术。

３４９

电脑知识与技术

本栏目责任编辑：贾薇薇计算机工程应用技术在图１的步骤１中（也就是在统计字符串频率时），对于简单的英文字母与数字字符来说，没有什么难度。而对于统计中文字符或其他一些由２个字节构成的字符时，可能会遇到某些问题。因为在对文件进行遍历统计频率时，需要对读入字符的步长加以控制。如果是单字节的字母，则步长为１，而如果是２个字节的字符，步长就需要相应的改为２。这样，就存在一个步长控制问题了。根据目前国际通用的Ｕｎｉｃｏｄｅ代码表示的汉字存储区位，位于４Ｅ００￣９ＦＦＦ的为中日韩文字，其他双字节字符也有相应固定的区位。有这样的ｕｎｉｃｏｄｅ编码条件，问题就可能解决了：在读入字符时，只需要判断读入的字符是否是位于双字节字符的存储区中。而对于ｊａｖａ１．５以上的版本中，ｃｈａｒａｃｔｅｒ类中提供了ｉｓＨｉｇｈＳｕｒｒｏｇａｔｅ函数。该函数能判断能判断所读入的字符是否是双字节字符的前半部分。这样就能有效解决读入字符步长控制问题。从而正确统计各种类型的字符出现频率（代码可以见附表）。

３．１．２构造ＨｕｆｆｍａｎＮｏｄｅ类

ＨｕｆｆｍａｎＮｏｄｅ是一个定义的典型的Ｈｕｆｆｍａｎ型的数据结构。具体形式如图２。

图２就是即将构造的Ｈｕｆｆｍａｎ结构。接下来需要将按频率已经排好序的各字符初

始化成该类的实例（具体方法参见上述１中的原理与附录中的程序片段），构造一棵带

有各字符符号及出现频率的Ｈｕｆｆｍａｎ树。这样，从树根开始遍历各个叶子结点。按照每

经历一次左孩子取０，经历一次右孩子取１的方法，得到各个叶子接点的Ｈｕｆｆｍａｎ编

码。并将该编码存入该类实例的变量：ｂｈ中，以备解码时或其他需要（编码函数见附录

的Ｅｎｃｏｄｅ函数）。

３．１．３ＢｕｉｌｄＨｕｆｆｍａｎ类上面生成Ｈｕｆｆｍａｎ树对于本程序来说是关键的一步。现在假设已经获得各字符的

Ｈｕｆｆｍａｎ编码，并将待压缩文件所有字符都化为了“０１”

类型的Ｈｕｆｆｍａｎ编码并存入变量之中了。接下来的工作就是将写编码了。需要注意的是在写入文件的编码时，需要写

入二进制代码。比如某个字符“Ａ”对应的编码是“００１”

。如果直接写入字符类型的“００１”

，这不但没有起到压缩的效果，反而比原字符所占内存增加了２倍。所以必须写入二进制类型的“００１”

。此时，问题出现了。大家知道，１．６及以下的ｊａｖａ版本并不能直接将“００１”转化成简单的“００１”

二进制序列。那么，采取什么样有效的措施才能达到压缩的效果呢。其实，ｊａｖａ中ＤａｔａＯｕｔｐｕｔＳｔｒｅａｍ类中的ｗｒｉｔｅ函数，可以写入ｂｙｔｅ类型的数据。

这样，解决问题的方法就在于将字符型的“０１”

序列转化为Ｂｙｔｅ型的数据了。有了这个思想，我们可以将带压缩的编码以８位为步长，将其对应转化为ｂｙｔｅ型的数据，存入一

个ｂｙｔｅ的数组中去。这样，每位８字节的“０１”

序列就压缩成为了最多８位的长度了，从而间接实现了压缩的目的。这样做，在解压的时候，需要重新将这些ｂｙｔｅ数还原成０１

序列，然后再将０１序列去与对应的Ｈｕｆｆｍａｎ树去匹配，还原得到相应的字符。４压缩效率分析

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

５部分ｊａｖａ

源程序

（下转第３７９页

）

图２ＨｕｆｆｎａｍＮｏｄｅ

类图图３ＢｕｉｌｄＨｕｆｆｍａｎ类图３５０

本栏目责任编辑：贾薇薇

计算机工程应用技术

（上接第３５０页）

６结束语

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

参考文献：

［１］ＴｈｏｍａｓＨ．Ｃｏｒｍｅｎ，ＩＮＴＲＯＤＵＣＴＯＩＮＴＯＡＬＧＯＲＩＴＨＭＳ［Ｍ］，北京：高等教育出版，２００６．

［２］郑丽，王言行，马素霞．Ｊａｖａ语言程序设计［Ｍ］，北京：清华大学出版社，２００６．

［３］严蔚敏吴伟民，数据结构（Ｃ语言版）

，人民邮电出版社２０００．

据通信格式和键盘发送数据的时序图如图４所示。图４条形码扫描器发送数据时序

由于ＰＳ／２接口的条形码扫描器数据通信格式与时序同于键盘，当ＳＩＯ和ＳＣＫ同时为高电平时，条形码扫描器可以发送数据给单片机，如果单片机将ＳＣＫ拉低，则禁止条形码扫描器发送数据。因此，只需单片机在要接收数据前，先把ＳＣＫ和ＳＩＯ都拉高，释放总线，条形码就能自行控制总线，完成数据正确发送，但主机可在任意时刻拉低ＳＣＫ来终止扫描器发送数据。根据时序图，可把时钟的第１个下降沿作为条形码扫描器开始发送数据的标志。因此，可接至单片机的外部中断０引脚上，采用中断方式完成数据的接收，以后每个时钟下降沿时刻，送出的数据有效，上升沿改变数据，其同步时钟频率约为１０－２０ｋＨｚ，周期为５０－１００μｓ，按照上述时序进行操作，单片机可正确读取所有数据。

４软件设计

系统的软件主要包括７个模块：主程序模块，数据采集模块，显示模块，称重和计价管理模块、串行通信模块、条码扫描器管理

模块、打印购物清单等［４］。

（１）主程序模块：主程序模块主要完成系统及可编程芯片的初始化及按需要调用各模块。

（２）数据采集模块：该模块完成对数据的采集及处理，采用中断读取Ａ／Ｄ转换数据。首先启动Ａ／Ｄ转换，然后等待连续的５次中断，将每次中断所对应的各位ＢＣＤ码读出，之后存储在内部ＲＡＭ单元。采用１６次滑动平均数字滤波方法提高测量的稳定性和精确性。

（３）显示模块：主要用于显示各级菜单、

实时显示货物重量、单价、总价等参数。（４）串行通信模块：该模块完成串行口的初始化、

波特率和数据格式的设置，并将采集的数据传给ＰＣ，以便于上微机的管理，实现网络化管理。

（５）称重和计价管理模块：主要完成去皮、

调零、称重、计价、累加等功能。（６）打印购物清单模块：主要完成打印购物清单等功能。打印内容包括：货物名称、

重量、单价、总价、时间、日期、收银员等。（７）条码扫描器模块：主要完成从条码扫描器输入货物名称、

单价等参数。５结论

本文创新点如下：（１）以单片机为核心的智能称重系统设计的实现，提高了称重测量的智能化程度，在测量精度、灵敏度、稳定性和性价比上有明显改善；（２）将称重与计价相结合，具有实用电子称和收银机双重功能，且成本低、可靠性高、实用性强等特点；

（３）从条码扫描器输入货物名称、

单价等参数提高了电子计价秤的使用效率；（４）具有通信功能，便于上微机的管理，实现了网络化管理。

参考文献：

［１］肖奇军等，智能电子称重系统，肇庆学院学报，２００５，２６（２）：５１－５３．

［２］陈安，ＰＩＣ单片机在超市收银台自动传送带中的应用，工业控制计算机，２００４，１７（８）：４３－４４．

［３］贾转红，ＰＣ机与多台单片机实时通信系统的设计与实现，微计算机信息，２００７，（１）：１４３－１４５．

［４］任治斌，ＭＣＳ５１单片机在电子皮带秤自动化中的应用，现代电子技术，２００５，（１４）：７３－７４．

３７９