LZW_压缩算法.pdfVIP

26 福 建 电 脑 2004年第 1期 LZW 压 缩 算 法 董雪丰 严 闪 (福建师范大学，福建 福州350007) 【摘 要】 本文主要介绍LZw编码思路以及编码解码的全过程。 【关键词】 词典式编码 解码 串表 码字流 1984年 ，美国T．A．Welch以LZw算法为名提 出1_Z78算法 CodeStream +一 CW lorPrefix 的实用修正形式，很快被用作几种流行程序的基础，包括：Unix 2．1LZW 的解码算 法 压缩程序和一些计算机归档系统 。LZw算法正是 以LZ78为基 (1) 将发端传送的LZw压缩代码作为译码的依据。LZw 础 ，对数据进行压缩编码 ，尽可能获得最大的压缩 比，这和压缩 编码器的输出代码 由压缩代码及单个字符所组成的串表构成。 技术属于无损压缩。 初始化时，串表中包含所有可能的单个字符 ，其余的代码值按顺 LZw和 LZ78的主要不同之处：LZw 只对短语进行编码 ，输 序分配给新的字符串。 出码中没有显示字符 ，这就有可能通过初始化短语表来包含输 (2) 从输入的码字流 (CodeStrema )读第一个码字 (Code 入字符表中的所有字符。一个新的短语是在一个 已译码的短语 Word)，把其对应的字符C输出，并把当前的码字当作 旧码 (Old 后附加下一个短语的第一个字符来构成。 Code)保存起来 ，以便后面使用。 l、LZw 编码的物理过程 Step：读入下一个字符码字 cw(fi：没有码字 CW表示输入 LZw 的编码能有效地利用字符出现的频率冗余度，字符重复 已穷尽，则结束)； 性和高使用率模式冗余度。IZW编码只需扫描一次数据，无需有关 If：CW 已存于表中，则sofrCW 一 输出，OldCode对应的 输入数据统计量的先验信息而运算时问正比于消息的长度。 字符串0S— Prefix，该前缀与S的最后一个字符 c(从右往左) 2、LZW 的编码思路 Prefix．C __+ 串表 ，CW __+OldCode：gotoStep LZw 的编码是 围绕一张转换表完成的，这张转换表称之为 Else：CW不在串表中(尚未定义)：则码字 OldCode对应的 “串表”(StringTable)。即放人串表的每一个字符串(亦称每一个 字符串0S— Prefix，该前缀与 0S的最后一个字符 C(从右往 表项)都给一个代码(CodeWord)，串表实际上是把8位ASCII字 左)Prefix．C一 串表 ，Prefix．C 一 输 出，CW — OldCode； 符集进行扩充 ，即可用来表示文本或图像 中出现的字符 串(可变 gotoStep。 长度字符)。这些字符串也可理解为是 ASCII字符集中新增加的 (3) LZw解码算法的伪码表示： 字符，扩充后的ASCII字符集可用 9位、10位、11位、12位甚至 Table… +__allnsingle—character，j=I，2… ．．．．n 更多位来表示。例如若每个字符串给 12个位，12位可以有 4096 J+_。n+1 个不同的12位代码，这就是说，转换表有4096个表项 ，其中256 CW +__readthefirstCodeinCodeStream 个表项用来存放 已定义的字符 (ASCII)，剩下 3840个表项用来 Output— TableC【W] 存放前缀 (Prex．字符串)。 O