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

湖北自考网来源：时间：2005-11-09 00:00:00

+领取

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

结束

本文标签

特别声明：1.凡本网注明稿件来源为“湖北自考网”的，转载必须注明“稿件来源：湖北自考网（www.hbzkw.com）”,违者将依法追究责任；
2.部分稿件来源于网络，如有不实或侵权，请联系我们沟通解决。最新官方信息请以湖北省教育考试院及各教育官网为准！

上一篇：自考“中国近现代史纲要”复习资料第一章下一篇：可移植的256色图形用户界面的设计

"LHARC中的动态限长编码压缩算法" 相关文章推荐

限时，免费获取学历提升方案

已帮助10w万+意向学历提升用户成功上岸

武汉自考工具箱

自考流程报名时间考试时间考场查询成绩查询成绩复查自考违规免考办理转考办理实践考核毕业申请学位申请学位外语自考助学成人高考

推荐信息

2023自考助学班

武汉自考专题推荐

自考视频课程自考模拟真题

毛泽东思想概论
培训优势：课时考点精讲+刷题+冲刺，熟练应对考试题型。全程督促学习，安排好学习计划。毛泽东思想概论...自考培训
英语二
本课程既是一门语言实践课程,也是拓宽知识、了解世界文化的重要素质课程,它以培养学习者的综合语言应用能力为目标，使他们在学习、工作和社会交往中能够使用英语进行有效的交流。英语二...自考培训
马克思主义基本原理概论
本书包括两个部分：自学考试大纲和基本原理。主要内容有，马克思主义是关于工人阶级和人类解放的科学，物质世界及其发展规律，认识的本质及其规律，人类社会及其发展规律，资本主义的形成及其发展，资本主义发展的历史进程，社会主义社会及其进程，共产主义社会及其进程等。马克思主义基本原理概论...自考培训
思想道德修养与法律基础
《思想道德修养与法律基础》课具有鲜明的政治性、思想性、理论性、针对性、科学性、知识性以及实践性和修养性。它包罗政治、思想、道德、心理本质、学习成才和法律本质等内容，指导和回答大学生在人生、抱负、信念等方面遍及关心和迫切需要解决的问题。思想道德修养与法律基础...自考培训
中国近代史纲要
“中国近现代史纲要”全国高等教育自学考试指定教材，依据中央审定的普通高等学校“中国近现代史纲要”编写大纲以及马克思主义理论研究和建设工程重点教材《中国近现代史纲要》，结合自学考试的特点设计了十章，集中讲述1840年鸦片战争爆发一直到2007年中国共产党第十七次全国代表大会召开的160多年的中国近现代历史。中国近代史纲要...自考培训