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中的动态限长编码压缩算法(一)
