摘 要 该文对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位。
代码长度缩减的规律是:设n为字符当前所在层数,则当字符的重复出现次数为28-n时,代码长度减少1位。
代码长度的缩减会带来一个十分关键的问题:当码树各结点值是静态的时候,一字符对应了某一高层结点后,此结点的所有下层枝叶将不能再对应其它字符,否则一些代码将是另一些代码的前缀,这将使还原过程无法进行。因此代码缩减将使编码路径数减少,一些后继字符将无法由码树编码。为此,该算法采取的策略是:按字符出现的次序将它们集中排列在码树的一侧叶子上,通过移动和交换分枝点之值的方法,使各层结点之值重新组合,从而使被占用结点的下属枝叶可“稼接”到未用的结点上。因此,当高层结点被占用后,其下属结点仍可使用,不会减少编码路径数。具体来说,当一后继字符出现并且其对应叶子的父结点已被占用,它将改变原有的编码路径,通过搜索找出一个未用的上层结点并由此得到其代码。
同样,当一字符须上升一层时,并不是升到其父结点中,而是升到上层中一个未用过的结点之中。当该字符再度出现时,它将沿新路径得到其代码,此代码的长度不仅为原代码长度减1,而且此代码的各个位也与原代码不同。下面以一具体例子加以说明。
设字符串为ababcabdabc……各字符的编码路径如图2所示。其中的Xi表示X的第i次出现。
@@09A04901.GIF;图2 字符编码路径示意图@@
由此可看出,由该算法给出的编码方法是逐步达到最佳码长的。一字符的压缩代码不仅与字符出现的次数有关(长度不同),而且与字符在文件中的位置有关(编码路径不同)。
LHARC建立了两个表专门用来记录码树的占用情况及各字符出现的次数,以便确定对码树的各种调整。当压缩后的数据达到32K时,将对表及码树进行“重组”,删除表中部分累积的数据后再继续进行压缩,以后将每隔16K“重组”一次。