一种改进的LZW编码数据压缩算法的设计与仿真

摘　要：分析了传统LZW编码算法的不足，根据语音数据的特点，对传统LZW编码数据压缩算法进行了改进，将字典初始化为16位，采用散列法和拉链法进行词条检索，采用阈值判断和LRU淘汰机制改进条目更新的方式，编码时采用自适应变码长方式。经测试，相比于传统LZW编码数据压缩算法，改进的算法对不同码长的数据的适应性更好，并且压缩比提高了约8%。

关键词：数据压缩，LZW，字典

1.引文
　　数据压缩一般分为两大类，无损数据压缩和有损数据压缩[1]。无损数据压缩指在解码后可以无失真的恢复出原始数据，不会丢失信息；有损数据压缩允许在解码后的数据与原始数据存在一定的误差。下面将主要研究无损数据压缩。
　　无损数据压缩技术的发展从最初的单纯的熵编码，发展到今天，出现了很多新的压缩方法[2]。现在比较常见的数据压缩方法有：
1.1 Huffman编码
　　Huffman编码是1952年由D.A Huffman在《论最小冗余度代码的构造》论文中提出，Huffman编码由于完全按照字符出现的概率构造编码，但存在没有错误保护功能和需要缓存区较大等局限性，效率不高。
1.2 算数编码
　　算数编码压缩也是一种基于统计模型的压缩方案，由Elias提出，在80年代发展起来的一种熵编码方法。和Huffman编码不同的是，算数编码不用单个信源符号去映射一个码字，而是将整条输入序列映射成为[0,1）区间内的一个小区间，该序列的概率就等于区间的长度；实际的编码输出是从上述小区间内选择一个代表性的二进制小数，这就实现高效编码的目的。不足的是实现较为复杂。
1.3 LZ编码
　　LZ编码是字典编码的英文简称，是一种基于字典方法的数据压缩技术。是1970年代末由两位以色列科学家Jacoh Ziv和Abraham Lempel提出，现在由 LZ编码衍生出来的算法很多，比较著名的有LZ77、LZ78、LZS、LZW等，LZ字典编码与基于统计的数据压缩技术不同，前者既不使用变长码，，也不使用统计模型，使有的是字符串，利用字典将需要的字符串进行编码形成一个标识，字典保存这些字符串及其标识。字典保存的字符串既可以是静态的，也可以是动态的（自适应的）。静态字典是固定的，添加字符串是允许的，但删除是不允许的；而动态字典中的字符串是先前输入流中出现过的，当读取新的字符串时，允许字符串的添加或删除。字典编码以压缩效果好和实现方法简单的优势，得到人们的一致认可。
　　但是，LZW压缩算法也存在着一些不足之处：
　　（1）在LZW算法中，字典的初始化需要按照ASCLL码表，消耗256个左右的字典词条数，而实现字典的寻址，至少需要9位的地址位去表示相应的词条位置，需要消耗大量的码字。这样的初始化过程中浪费了大量的字典容量，直接导致输出码长的浪费，严重降低最终的压缩比。
　　（2）传统的LZW算法在执行过程中，字典的生成和查找是基于顺序插入和检索模式，当需要处理的数据量较大时，会导致生成的字典项较多，严重降低查找效率；同时，通过顺序检索模式浪费了大量的算法执行时间，无法充分利用数据之间的局部相关性，降低算法的执行效率。
　　（3）传统的LZW压缩算法采用8位数据输入，固定长度编码输出，随着字典内容的不断增多，输出编码的位数不断增加，固定的输出编码长度造成资源的浪费，系统的压缩率下降。
　　本文对LZW算法进行相应改进，实现了高效数据压缩，提高了压缩性能。
2.改进的LZW方法
2.1对于字典初始化的方式，由于在语音识别中使用的更多的是16进制的数据，因此，对于字典的初始化，只需要将16进制数进行字典的初始化，不需要将所有的ASCLL字符全部初始化。
2.2LZW压缩算法的执行速度依赖于字典查找的速度。在LZW压缩算法中，若直接检索字典，编码的速度很低，同时时间复杂度较高，为。因此，选择一种效率较高的字典存储和遍历索引的方式是提高LZW编码效率的主要途径。为了提高字典的存储和索引效率，引入散列表（Hash Table）来存储字典，只需通过关键字就可以确定结点的存储位置，这样能有效提高字符串表的检索效率。2.3为了提高编码的效率，采用可变长度的编码方法。在系统中，使用的可变编码位数从8位开始，当编码长度超过了8位的表示范围，则自动增加到9位编码，依次递增编码位数。但增加编码位数使得算法性能和执行效率都受到影响，因此，设定编码长度的最大范围为12位，当编码超出12位（4096）表示范围，需要重新开始字典的生成和编码。
2.4当词条数目过多导致字典容量饱和时，需要重新生成字典，clear操作会严重影响压缩编码的压缩比和执行效率，因此，为了解决传统的LZW编码压缩效率低的问题，现作出以下改进：
　　当字典中串表填满之后，不立即输出clear信号，删除字典表，而是继续输入一定长度的数据流，使用现有的字典表表对其进行压缩编码，同时计算出这时被压缩的数据流的压缩比，如果所得到的压缩比较低，满足系统要求即（其中为当前计算的压缩比，为系统给定的一个阀值），则继续先前的操作；如果所得到的压缩比时，表示现在的字典表无法满足当前数据压缩的要求，则进行删除和重建字典表的操作。这样可以有效抑制那些突发的数据对整体压缩性能的影响，使得系统不会由于一些数据毛刺的影响导致多次删除和重建字典表，提高了LZW压缩算法的压缩比和执行效率。
　　改进的LZW编码算法的软件流程图如下图1所示：

图1 改进的LZW算法实现流程图
　　可以通过流程图看出，改进的LZW编码方式主要在添加新词条字符串时，需要判断码长是否满足要求，同时当系统码长达到最大，即12位码长之后，是否输出clear信号需要通过判断一段数据流的压缩比后决定。
3.算法的压缩比性能仿真
　　在对算法性能测试时使用系统中需要存储的数据，分别使用改进的LZW算法和传统LZW算法在不同输出码长情况下进行数据压缩，得到部分节点的输出数据，再将这些点的数据通过MATLAB以线图形式输出，得到对于改进的LZW压缩算法的性能通过与传统LZW编码方法分别通过8位码长和12位码长输出的压缩比性能比较数据图如图2所示，其中压缩比的定义为：
    式(1) 

图2 LZW算法压缩比性能比较仿真图

4. 结论
　　在图2中可以看出，改进型LZW算法的压缩比小于传统的LZW算法，实测结果表明，对于传统的LZW压缩算法，在选择输出码长为12位时，在文件较大时，压缩性能优于8位输出的LZW算法，但是压缩数据较小时，压缩性能较差；传统的LZW算法在 压缩过程中，压缩比在更新字典起初有明显上升，而在改进型LZW算法中，在字典更新过程中压缩比明显改善，提高了约8%。
　　

参考文献:
.Signal Processing:Image Communication .2000.16(4).367-372.

本文链接：http://www.qk112.com/lwfw/jsjlw/zhinengkeji/231764.html