网站首页
手机版

LHARC中的动态限长编码压缩算法

更新时间:2006-01-06 16:11:40作者:未知

   摘 要 该文对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“重组”一次。
 

作者:傅晓玲

本文标签:

为您推荐

IT市场初长成

1. 合肥IT业(市场)现状 合肥,位于安徽省中部,可辐射面积大;背靠内陆一些欠发达的地区如大别山区。由于历史、体制等方面的原因,信息化建设起步晚,基础薄,合肥地区生产计算机及其外围设备、通信器材产品的企业很少,基本上完全是一个消费性市场,无论是规模还是

2011-11-10 16:10

定性仿真综述

本文首先介绍了定性仿真的产生背景及理论发展状况,然后说明了定性仿真在各领域的应用情况,最后对定性仿真的发展方向进行了探讨。

2011-11-10 16:06

关于计算机普及教育的几个问题

一、当前计算机普及的形势 一般理论课程采用的方法是∶先理论,后实际;先抽象,后具体;先一般,后个别。我认为对计算机应用课程应当采用的方法是∶从实际到理论;从具体到抽象;从个别到一般;从零碎到系统。事实证明,这样的方法是十分有效的,是符合广大计算机初学

2011-11-10 16:05

新世纪的软件产业与集成电路产业

为推动我国信息产业和集成电路的发展,增强信息产业创新能力和国际竞争能力,带动传统产业改造和产品升级换代,国家实行集成电路税收优惠、软件企业上市优先的政策,国务院已于1999年7月印发了《鼓励软件产业和集成电路产业发展的若干政策》。 为打破几十年来,国内硬

2011-11-10 16:04

定性仿真理论及其应用

本文首先介绍了定性仿真的产生背景及理论发展状况,然后说明了定性仿真在各领域的应用情况,最后对定性仿真的发展方向进行了探讨。

2011-11-10 16:03

浅谈中职学校计算机理论课程教学的改革

计算机 作为现代高科技的产物,其理论知识专业性强。并且,教师不注意教学方法的选择,学生接受起来有很大困难,学生普遍反映计算机理论课程太难、太枯燥。笔者从中职学校的计算机理论课程的培养目标出发,通过对中职学校的计算机理论课程的教学目标与教学现状存在弊端

2011-11-10 16:01

加载中...