下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
精品文档-下载后可编辑LHARC中的动态限长编码压缩算法摘要该文对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,而且此代码的各个位也与原代码不同。下面以一具体例子加以说明。
设字符串为ababcab
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2021-2022学年江苏省常州市勤业中学中考数学考试模拟冲刺卷含解析
- 2022年山东省临沂平邑县联考中考数学模拟预测题含解析
- 2022届河北省唐山路南区四校联考中考联考数学试卷含解析
- 2024-2030年旅居车行业市场发展分析及发展趋势前景预测报告
- 2024-2030年新版中国高压电器设备项目可行性研究报告
- 2024-2030年新版中国金卡项目可行性研究报告
- 2024-2030年新版中国环保型汽车电器研制项目可行性研究报告
- 2024-2030年新版中国可塑剂项目可行性研究报告
- 2024-2030年新型观光电动汽车市场前景分析及投资策略与风险管理研究报告
- 2024-2030年数码照相机行业市场深度分析及发展策略研究报告
- 立德树人与数学教学改革
- 国漫行业分析
- 10万洁净车间标准
- 2024年保密法培训课件-(含附件)
- 培训机构提成方案
- 新公司运营方案模板
- 《高温熔融金属吊运安全规程》(AQ7011-2018)
- 部编版道德与法治三年级下册第二单元 我在这里长大 单元作业设计
- 新能源技术推广与行业发展研究
- 国家开放大学电大考试《工程建设监理概论》考题题库及答案
- 鹦鹉宠物行业现状分析
评论
0/150
提交评论