lzw编码分析.pdfVIP

LZW 编码分析 导航 U LZW 编码分析U 1 U 缘起：U 1 U 名词规范：U 1 U 本文完成的主要工作U 1 U LZW编码原理U 2 U LZW解码原理U 3 U 问题及改进：U 4 U 算法实现及分析U 6 U 关于作业以外的延拓：U 10 U 参考文献：U 11 缘起： LZW 是一种无损数据压缩算法，是对1978 年发表的 LZ78 的改进。LZW 应用于Unix 系统的标准工具、GIF 图片格式以及TIFF 格式等。同时LZW 压缩算法对于较大规模的英 文文本的压缩具有良好的效果，一般可以压缩到原来大小的一半。然而LZW 的专利曾一度 限制了其使用范围，不过，LZW 专利于2003 年过期。对事物的好奇心驱使我深入学习LZW 压缩和解压缩算法。 本文绝大部分的陈述来自于Dobb 博士的论文以及技术博客、论坛以及维基百科。 名词规范： {( )} 码书 编解码时供查询、插入的字符串和整数索引的集合 STRING, INDEX 文本 需要进行编码的数据结构 编码序列 编码后的整数序列 ( ) 码字 表示字符串及其索引值的一种数据结构 STRING, INDEX 本文完成的主要工作 当码书很大时，查询和编码的效率将有所下降。查询的效率可以很直观的理解，编码效 1 / 11 leengsmile@126.com BUPT 率的下降是指编码的结果是整数序列，其中将会出现较大的整数，如果不进行后续处理，需 要较多的比特才能对其进行编码。本文将结合TIF 格式中的压缩原理，对Dobb 博士所提及 的LZW 算法进行适当的改进，即，当码书容量达到一个容限值时，比如4096 = 210(13bit) ， 清空码书，并在编码序列中插入清除标志CLEAR，为原始数据字长(255 = 28)加1，并插入 结束标志END，其大小为清除标志CLEAR 加1，然后重新构造码书。 LZW 编码原理 LZW 压缩编码如下所示 1. STRING = get input character 2. WHILE there are still input characters DO 3. CHARACTER = get input character 4. IF STRING+CHARACTER is in the string table then 5. STRING = STRING+character 6. ELSE 7. output the code for STRING 8. add STRING+CHARACTER to the string table 9. IF table size reaches up to the predetermined MAX_SIZE 10. renew table and append CLEAN and END label to the output 11. END of IF 12. STRING = CHARACTER 13. END of IF 14.END of WHILE 15.output the code for STRING 其中9~11 行根据TIF 格式压缩原理而添加的步骤，图1 是其编码示例，由于输入文本 很短，不会导致码书容量达到上限值，因而不会运行9~11 行所示代码。 2 / 11