裹茎u澎斟_鼹
一个改进的基于字典压缩L zw算法的研究
朱亮
(苏州工业职业技术学院信息工程系江苏苏州215000)
[擒要]首先介绍数据压缩技术的发展历史和概貌，接着介绍基于字典压缩的压缩算法，着重阐述L zw算法原理和传统编码过程。然后针对该算法进行几方面的改进，实现零搜索、动态编码，实现数据的压缩和解压缩功能，最后通过具体的压缩比较来说明改进L zw算法的特点。
[关键词]数据压缩Lzw字典压缩零搜索动态编码
中图分类号：TP3文献标识码：^文章编号：1671—7597(2008)0910014一01
一、基于字典压缩算法
(一)基于字典压缩算法的一般原理
字典压缩算法是利用许多数据类型都含有重复的代码序列这一特性。在文本文件中其代码字代表字符，而
在光栅图像中代码字代表象素。在编码时将有霞复的内容一次性地记录在一个数据串表中，这个表就仿佛是字典，当译码是利用指针号或索引号就可以到原输入数据流中相应的内容，L z的几种算法都属于基于字典的压缩算法。
(二)基于字典压缩算法的分类
1．L Z77、L Z SS算法
L Z77、L zss算法的思想是：在数据压缩过程中。寻当前等待进行压缩处理的数据串中是否在已经处理过的数据串中出现过，如果确实曾经出现过，则利用指向该已经进行处理数据串的指针代替当前等待进行压缩的数据串。
2．L Z78、L Z W算法
L Z W算法
(1)编码算法
L z w编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀的字符序列，并且为每个表项分配一个码字。L zw编码器使用了一种很实用的分析算法，称为贪婪分析算法。在贪婪分析算法中，
每一次分析都要串行地检查来自字符流的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀。用已知的前缀加上下一个输入字符c也就是当前字符作为该前缀的扩展字符，形成新的扩展字符串缀一符串：Pr ef i x．c。这个新的缀一符串是否要加到词典中，还要看词典中是否存有和它相同的缀一符串St r i ng。如果有，那么这个缀一符串就变成前缀(Pr ef i x)，继续输入新的字符，否则就把这个缀一符串写到词典中生成一个新的前缀(Pr ef i x)，并给一个代码。
(2)译码算法
L z w译码算法中还用到另外两个术语：①当前码字：指当前正在处理的码字，用cw表示，用st r i n g．cw表示当前缀一符串；②先前码字：指先于当前码字的码字，用p w表示。用st r i ng．pW表示先前缀一符串。L Z w译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(r oot s)。L zw算法在译码过程中会记住先前码字(p w)。从码字流中读当前码字(c町之后输出当前缀一符串st r i n g．cw，然后把用st r i ng．cw的第一个字符扩展的先前缀一符串s t r i ng．pw添加到词典中。：
二、改进的U州算法
(一)实现零搜索
如何才能使根据字头码和字尾码建立的索引值不重复，其办法是以其本身的值合成内存地址，依靠指针
进行定位，从而不再需要查过程。在32位操作系统下，其寻址能力可达4G B，再加上硬件设施大大提高，物理内存空间一般达到了128惦，技术上虚拟内存町达4G B，使得上述方法成为可能。
(二)动态编码
使用动态编码长度进一步提高了算法效率。这种方法允许压缩代码长度的更改，即利用不固定长度的代码存储压缩数据。L zw算法一般从9位开始编码，这时存储代码也是9位，直到编码增加到10位时，存储代码才增加到10位。传统的Lzw算法是直接存储最人编码位的，这样做导致非编码数据也要存储这样大的位，浪费了完全没有用处的几个高位。考虑到字典编码是按位逐渐增大的，于是应用动态编码既能保证字典编码的完整，又能起到对非编码数据的优化作用。但应用动态编码在存储代码时需要增加一个位处理过程。这需要采用动态编码长度存储，编码是从9位开始的，因此数据存储也是从9位开始。
三、编码潦程圈
由上面几个例子可以看出本压缩算法对一些常用的文件格式如：记事本。W0r d，PPT，图片以及一些虑用程序等都能进行准确的压缩与解压缩，并具都比原来的L zw算法压缩率要高。同时也发现，对于文本类文件，压缩速度比较快，而且压缩比比较高，对于图片来讲，该压缩算法效果不是很好。
参考文献：
[1]李小平，
2000．5第一版．
[2]吴乐南，
[3]洪小达，
1999．6第一版．
‘数据压缩及传输编码软件速查手册》．科学出版社
‘数据压缩》．电子工业出版社．2000．6第一版．
‘多媒体计算机与数据压缩技术》．中国国际广播出版社
[4]王咏刚，‘笨笨数据压缩教程》．m．context f ree．net．
[5】汪远征，刘瑞新，‘中文V i sual B asi c6．0与可视化编程》。上海科学技术出版社．，1999．11
[6]c．E．s ha nno n，‘通信的数学理论》(^l Ia t hem t i ca l The or y of
C o咖uni cat i on)．
字符串长度压缩[7]D．A．H uff㈣。《最小冗余度代码的构造法》(A M et hod f o r t h e
C ons t r uct i on o f M i ni m um R edundancy C o de s)．

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。