一种改进的LZW图像压缩技术的研究与实现
摘要：针对原始的lzw算法在进行数据压缩的时候给不同的代码字分配固定长度整数，并在查询字典时耗时随字符串长度增加，成几何增长的不足等情况，提出了一种改进的lzw压缩算法，改进的算法采用了给不同的代码字段分配变长长度整数的方法。测试结果显示，在深较小的图片压缩中，压缩率总体小于50%。比原始的lzw算法有明显的改进。结果表明，nic算法适用于低深的非自然图或有大量块的图片中。
关键词：图像压缩；定长编码；压缩率
abstract: during the time of data compression for the original lzw algorithm assigned to a different code word fixed-length integer, and time-consuming with increasing length of the string in the query dictionary, as the lack of geometric growth, an improved the lzw compression algorithm, the improved algorithm uses a variable length integer assigned to a different code field. the test results show a smaller color depth image compression, the compression ratio is less than 50% overall. the results show that the nic algorithm is suitable for low color depth of unnatural map or a large number of color images.keywords: image com
pression; fixed-length encoding; compression ratio
中图分类号：tp301.6字符串长度与大小文献标识码： a文章编号
近年来，图像压缩领域变得越来越为人们所重视，因为图像文件不仅需要占据大量的内容空间，同时随着互联网络技术的发展，在网络上，图像文件也占据了大量的传输带宽，所以在图像进行存储之前，或者在对图像进行网络传输之前，首先要对图像进行压缩。目前的图像压缩算法分为两类：有损压缩和无损压缩，其中lzw是一种流行的无损图像压缩算法。它是一种基于字典的压缩算法，通过对一个字典的应用对数据进行编码，在图像压缩领域，它通过定长编码技术，消除图像像素间冗余，性能良好。
1 lzw算法
lzw压缩算法思想主要是通过用简单的代码来替换复杂的字符串，在压缩的过程中，动态生成串表，通过串表来记录字符串与代码之间的对应关系[1]。压缩开始时，初始化串表使其包括所有的单字（代码从0到255），lzw压缩算法规定清串表代码为256，结束代码为257，由此串表中增加第一个表项时，对应的代码是258。为限制串表的大小，lzw压缩算法规定串表
不能超过4096项，即当代码位数超过12位时，放弃这个串表，重新初始化串表，同时输出一个清位码，并按新的串表继续进行压缩[2][3]。
2 改进后的lzw算法
改进的lzw算法（new image compress：以下简称为nic）首先对偏移量中的数据进行读取，得到原始图像像素的位数，然后对数据块进行rle算法压缩，接着以文件读取方式，逐个字节读取，读取的字节赋值到后缀变量中，前缀变量记录为上一次读取的字节。读取完一个字节后，便对字典数组中前缀变量和后缀变量的值做判断，为空则赋值为当前编码号，段号自动增长；不为空则把值赋给前缀变量。当段号大于4095时，输出清字典代码（257），并清空字典所有数据。如此循环，直到数据处理到最后一个字节，输出前缀变量和后缀变量，最后输出结束符（256），把所有输出保存成nic文件。
以标准码长为12bit的lzw压缩算法为例，该算法编码表可以容纳4096个码字。整个编码表分成5个部分，其中1～256，257～512，513～1024，1025～2048，2049～4096分别为第1部分，第2部分，第3部分，第4部分，第5部分，每一部分输出的代码字长度分别为8bit，9bit，10bit，11bit，12bit。在算法中设置257为变长标示，每出现一次代码字长度的变化便
输出一个变长标示，以提示解码程序代码字长度的变化。在压缩的过程中，根据lzw的编码规则，每次读入一个字节，都要和之前的字典的所有项相比较，发现如果已经在字典中，就继续读下一个字节，如果字典中没有，就输出最后匹配的段号，并把这个新段号加入到字典中。那么，每读一个字节，就要查一遍，会使得编码所需要的时间随文件长度而呈指数增长。在这里，本文提出一个解决方法，从而真正实现零查，称其为反向字典存储列表，即把每个（前缀，后缀）作为二维数组的下标，值为段号。 这样的反向列表虽然有些（前缀，后缀）可能一直没有出现过，使得额外多占用了很多内存。但是只有这样的格式才能做到真正的零查，用这些内存换取节约的时间是非常值得的。

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