摘 要 该文对DOS下常用的数据压缩软件LHARC的算法进行了分析。该算法中采用了一种动态限长变化的不等长编码方法,使最短码2位,而最长码不超过8位,达到了最佳压缩效果。
一、前言
LHARC是DOS下的数据压缩软件之一,与同类软件如ARJ、PKZIP、PKARC等相比,具有如下几个特点。
1.压缩比高
LHARC采用先进的字符串自适应压缩与单个字符的限长变化编码压缩相结合的方法,对文件进行双重压缩,尽可能地减少了冗余,对各类文件的压缩效果都很好。
2.保密性好
除应具有保存文件、节约存储空间的功能外,提高数据的保密性也是压缩软件的一个重要功能。LHARC由于采取了与众不同的动态限长编码压缩技术,使字符与其压缩代码之间无固定的对应关系,压缩后的数据更具保密性。
3.软件短小精悍
LHARC整个软件集压缩、还原于一身,只有30余K,而其它同类软件均有100余K。
LHARC的基本压缩原理是,将待压缩文件看作是字符流(字节流),将其中的冗余信息分成两类:
(1) 同一字符的离散出现
如 abcda……
这里,字符a出现了两次。
2.字符串的重复出现
如 abcdabcd……或abcd…abcd……
这里,字符串abcd出现了两次。值得说明的是,这里串的概念是LZW方法意义下的,即将字符流中每一字符均看作是一个串的起始字符。
压缩时,首先对字符流中的字符串进行识别,将其中的重复串用压缩格式记载,然后再将处理后的数据用不等长编码进行代码变换及压缩。下面仅就其中的动态限长变化编码方法进行介绍。
二、动态限长编码方法
1.基本原理
经重复串压缩后的数据中,重复串已大大减少,而同一字符的分布式冗余问题则比较突出。由于256个字符的使用概率一般不同,往往相差悬殊,若采用不等长编码,将高频字符用较短代码表示,低频字符用较长码表示,则提高了整体的压缩比。
Haffman编码是最佳不等长编码,它根据文件中各字符的统计概率来分配代码长度。如设文件中不同字符数为n,第i个字符的概率为Pi,代码长度为li,则当概率满足P1≥P2≥…≥Pn时,Haffman编码的码长满足l1≤l2≤…≤ln,此时,代码平均长度的数学期望=∑ni=1Pi·li达到最小。
在一般的数据压缩过程中,Haffman编码的算法实现为:先统计出待压文件中各字符的出现概率,据此动态建立一棵Haffman树,并以二分树的序列形式存入压缩数据文件首部以用于还原过程。在压缩过程中,由Haffman树实现字符的ASCII码(等长码)与其压缩代码(Haffman不等长码)的转换。这种处理方法需对待压缩文件进行两遍扫描,且Haffman树须保存于压缩数据文件中而占用额外的存储空间。
在LHARC的算法中,对Haffman编码的实现采用了新的方法。其基本原理是:在压缩前动态建立一棵初始译码树,在压缩过程中不断调整译码树的结构,使各字符的压缩代码长度随字符出现的次数增加而逐步缩减。最短码的长度可达到2位,而最长码不超过8位(二进制),从而获得很高的压缩比。该算法的其它优点还有:(1)无须事先统计各字符的出现概率,一次扫描即可;(2)译码树须保存在压缩数据文件中,还原时同样生成即可;(3)字符与其压缩代码之间无固定对应关系,使压缩后的数据具有一定的保密性。
2.压缩的实现及码树的调整
压缩前动态建立一棵初始译码树,每个叶结点对应一个字符。由于压缩前可以认为各字符的出现概率相等,故初始码树应为一有256片叶子的平衡二叉树,如图1所示。显然每个字符的初始代码长度均为8位。
@@09A04900.GIF;图1 初始译码树@@
当压缩开始,第一个字符出现时,将其对应第一个叶结点,沿码树向上的通路至根,所经各边标号(左0右1)组成的0、1序列构成该字符的初始代码。输出代码后,调整码树,将该字符对应的叶结点之值与上一层某一结点之值互换,当该字符再次出现时,其路径长度就会减少一结点。如字符原对应8位长代码,则再次出现后就对应7位代码了。如该字符继续不断地出现,其所对应的叶结点将逐级上升到第6层、第5层、甚至第2层,而此字符的码长随之减至6位、5位、直至2位[1] [2] 下一页
|
