第26卷 第4期2010年2月

甘肃科技

Vol.26 No.4Feb. 2010

几种无损数据压缩算法的探讨及在JAVAWeb程序中的应用

肖武德

(甘肃广播电视大学定西市分校,甘肃定西743000)

摘 要:随着知识爆炸式的发展,数据压缩在计算机领域起到举足轻重的作用。Huffman编码是一种常用的压缩方法,其原理是将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。LZ77算法通过使用已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。LZW算法是基于LZ77思想的一个变种。由于专利权原因,LZW没有得到像LZ77一样的流行。DEFLATE方法是LZ77算法与Huffman编码的组合,具有LZ77与Huffman编码的优势。DEFLATE方法具有开源通用高压缩率的优势,因此,得到了广泛的应用。将采用DEFLATE方法的GZIP压缩应用到B/S架构的企业应用中可以减小网络传输的数据量,进而提高系统的整体性能。

关键词:无损压缩;Huffman编码;LZ77;DEFLATE;LZW;GZIPJAVA中图分类号:TP751.1

码代替,每个数据的代码各不相同。这些代码都是

1 引言

自从有计算机以来,它的数据存储和传播能力一直在不断的发展,到目前已经达到了非常强大的地步。然而,这一时期也是人类的知识爆炸式发展的一个时期,很难衡量他们哪一个的速度更快。但是我们总能听到电脑用户抱怨磁盘空间不足,花费太长的时间下载需要的文件,从人们在使用计算机的过程中可以看到我们仍然期望计算机存储数据和传播数据的能力不断提高。当然我们可以升级计算机硬件,来提高电脑的性能,同时,计算机厂家不断涌现的新型号也意味着这一策略的庞大成本。在同样的硬件条件下,采用数据压缩可以存储更多的数据、获得更高的传输性能。另外,便捷终端、微型设备的出现更是需要很好的压缩算法来支持。比方说,遍布于数码录音笔、数码相机、数码随身听、数码摄像机等各种数字设备中的音频、图像、视频信息,就必须经过有效的压缩才能在硬盘上存储或是通过USB电缆传输。主要讨论几种常见的无损压缩算法,分析其原理,并通过对比给出其优缺点。最后给出GZIP在JavaWeb程序中的一种应用。

二进制码,且码的长度是可变的。如:有一个原始数据序列,ABACCDAA则编码为A(0),B(10),C(110),(D111),压缩后为010011011011100。

Huffman编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示,而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而,它并不处理符号的顺序和重复或序号的序列。而且产生霍夫曼编码需要对原始数据扫描两遍,第一遍扫描要精确地统计出原始数据中的每个值出现的频率,第二遍是建立霍夫曼树并进行编码,由于需要建立二叉树并遍历二叉树生成编码,因此数据压缩和还原速度都较慢。2.1 Huffman编码的压缩原理

Huffman编码是一种可变长编码方式,是由美国数学家DavidHuffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。Huffman算法的最根本的原则是:累计的(字符的统计数字*字符的编码长度)为最小,也就是权值(字符的统计数字*字符的编码长度)的和最小。2.2 Huffman树

,2 Huffman编码

Huffman编码是一种常用的压缩方法。是1952年为文本文件建立的,其基本原理是频繁使用的数