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

1、LHARC中的动态限长编码压缩算法摘要该文对下常用的数据压缩软件的算法进行了分析。该算法中采用了一种动态限长变化的不等长编码方法，使最短码2位, 而最长码不超过8位，达到了最佳压缩效果。、前言是下的数据压缩软件之一，与同类软件如、等相比，具有如下几个特点。1压缩比高采用先进的字符串自适应压缩与单个字符的限长变化编码 压缩相结合的方法，对文件进行双重压缩，尽可能地减少了冗余，对各类文件 的压缩效果都很好。2保密性好除应具有保存文件、节约存储空间的功能外，提高数据的保 密性也是压缩软件的一个重要功能。由于采取了与众不同的动态限长编码压缩技术，使字符与其压缩代码 之间无固定的对应关系，压缩后的数据更

2、具保密性。3软件短小精悍整个软件集压缩、还原于一身，只有30余，而其它同类 软件均有100余。的基本压缩原理是，将待压缩文件看作是字符流字节流，将其中的冗余 信息分成两类1同一字符的离散出现如这里，字符出现了两次。2字符串的重复出现如或这里,字符串出现了两次。值得说明的是，这里串的概念是方法意义下的，即将字符流中每一字符均看作是一个串的起始字符。压缩时 ,首先对字符流中的字符串进行识别 ,将其中的重复串用压缩格 式记载 ,然后再将处理后的数据用不等长编码进行代码变换及压缩。面仅就其中的动态限长变化编码方法进行介绍。、动态限长编码方法 1 基本原理经重复串压缩后的数据中 ,重复串已大大减少 ,而

3、同一字符的分布式冗余问题则比较突出。由于 256 个字符的使用概率一般不同 ,往往相差悬殊 ,若采用不等长编 码 ,将高频字符用较短代码表示 ,低频字符用较长码表示 ,则提高了整体的压 缩比。编码是最佳不等长编码 ,它根据文件中各字符的统计概率来分配代码长度。如设文件中不同字符数为,第个字符的概率为 ,代码长度为 ,则当概率满足1 2时扛编码的码长满足1 2冬此时，代码平均长度的数学期望二刀二达到最小。在一般的数据压缩过程中,编码的算法实现为先统计出待压文件中各字符的出现概率 ,据此动态建立一棵树 ,并以二分树的序列形式存入压缩数 据文件首部以用于还原过程。在压缩过程中 ,由树实现字符的码等长

4、码与其压缩代码不等长码的转 换。这种处理方法需对待压缩文件进行两遍扫描 ,且树须保存于压缩数据文件中而占用额外的存储空间。在的算法中 ,对编码的实现采用了新的方法。其基本原理是在压缩前动态建立一棵初始译码树,在压缩过程中不断调整译码树的结构 ,使各字符的压缩代码长度随字符出现的次数增加而逐 步缩减。最短码的长度可达到 2 位,而最长码不超过 8 位二进制 ,从而获得很高 的压缩比。该算法的其它优点还有 1 无须事先统计各字符的出现概率 ,一次扫描 即可 ;2 译码树须保存在压缩数据文件中 ,还原时同样生成即可 ;3 字符与其 压缩代码之间无固定对应关系 ,使压缩后的数据具有一定的保密性。2 压

5、缩的实现及码树的调整压缩前动态建立一棵初始译码树,每个叶结点对应一个字符。由于压缩前可以认为各字符的出现概率相等,故初始码树应为一有 256片叶子的平衡二叉树 ,如图 1 所示。显然每个字符的初始代码长度均为 8 位。0904900;图 1 初始译码树 当压缩开始 ,第一个字符出现时 ,将其 对应第一个叶结点 ,沿码树向上的通路至根 ,所经各边标号左 0右 1组成的 0、 1 序列构成该字符的初始代码。输出代码后 ,调整码树 ,将该字符对应的叶结点之值与上一层某一结点 之值互换 ,当该字符再次出现时 ,其路径长度就会减少一结点。如字符原对应 8位长代码 ,则再次出现后就对应 7位代码了。如该字

6、符继续不断地出现 ,其所对应的叶结点将逐级上升到第 6 层、第 5层、甚至第 2 层,而此字符的码长随之减至 6 位、5 位、直至 2 位。代码长度缩减的规律是设为字符当前所在层数,则当字符的重复出现次数为 28-时,代码长度减少 1 位。代码长度的缩减会带来一个十分关键的问题当码树各结点值是静态 的时候 ,一字符对应了某一高层结点后 ,此结点的所有下层枝叶将不能再对 应其它字符 ,否则一些代码将是另一些代码的前缀 ,这将使还原过程无法进 行。因此代码缩减将使编码路径数减少 ,一些后继字符将无法由码树编码。为此 ,该算法采取的策略是按字符出现的次序将它们集中排列在码树 的一侧叶子上 ,通过移动

7、和交换分枝点之值的方法 ,使各层结点之值重新组 合,从而使被占用结点的下属枝叶可稼接到未用的结点上。因此 ,当高层结点被占用后 ,其下属结点仍可使用 ,不会减少编码路径数。具体来说 ,当一后继字符出现并且其对应叶子的父结点已被占用,它将 改变原有的编码路径 ,通过搜索找出一个未用的上层结点并由此得到其代 码。同样 ,当一字符须上升一层时 ,并不是升到其父结点中 ,而是升到上层中 一个未用过的结点之中。当该字符再度出现时 ,它将沿新路径得到其代码 ,此代码的长度不仅为 原代码长度减 1,而且此代码的各个位也与原代码不同。面以一具体例子加以说明。设字符串为各字符的编码路径如图2所示。其中的表示的第次出现。0904901;图 2 字符编码路径示意图 由此可看出 ,由该算法给出 的编码方法是逐步达到最佳码长的。一字符的压缩代码不仅与字符出现的次数有关长度不同，而且与字符在文