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编码是