第4章无损数据压缩 6|BB(3,2) AAB(7,3) 在相同的计算机环境下,LZSS算法比LZ7可获得比较高的压缩比,而译码同样简单。这 也就是为什么这种算法成为开发新算法的基础,许多后来开发的文档压缩程序都使用了LZSS 的思想。例如, PKZip,ARJ, LHArc和Z00等等,其差别仅仅是指针的长短和窗口的大小等有 所不同。 LZSS同样可以和熵编码联合使用,例如AJ就与赫夫曼编码联用,而PKZi则与 Shannon-Fano联用,它的后续版本也采用赫夫曼编码 4.4.4LZ78算法 在介绍LZ78算法之前,首先说明在算法中用到的几个术语和符号: (1)字符流( Charstream):要被编码的数据序列。 (2)字符( Character):字符流中的基本数据单元。 (3)前缀( Prefix):在一个字符之前的字符序列。 (4)缀-符串( String):前缀+字符 (5)码字( Code word):码字流中的基本数据单元,代表词典中的一串字符 (6)码字流( Codestream):码字和字符组成的序列,是编码器的输出。 (7)词典( Dictionary):缀-符串表。按照词典中的索引号对每条缀-符串( String)指 定一个码字( Code word) (8)当前前缀( Current prefix):在编码算法中使用,指当前正在处理的前缀,用符号 P表示。 (9)当前字符( urrent character):在编码算法中使用,指当前前缀之后的字符,用 符号C表示。 (10)当前码字( Current code word):在译码算法中使用,指当前处理的码字,用W表 示当前码字, String.W表示当前码字的缀-符串。 编码算法 LZ78的编码思想是不断地从字符流中提取新的缀-符串( String),通俗地理解为新“词 条”,然后用“代号”也就是码字( Code word)表示这个“词条”。这样一来,对字符流的 编码就变成了用码字( Code word)去替换字符流( Charstream),生成码字流( Codestream), 从而达到压缩数据的目的。 在编码开始时词典是空的,不包含任何缀-符串( string)。在这种情况下编码器就输出 个表示空字符串的特殊码字(例如“0”)和字符流中( Charstream)的第一个字符C,并把这 个字符C添加到词典中作为一个由一个字符组成的缀-符串( string)。在编码过程中,如果出 现类似的情况,也照此办理。在词典中已经包含某些缀-符串( String)之后,如果“当前前 缀P+当前字符C”已经在词典中,就用字符C来扩展这个前缀,这样的扩展操作一直重复到 获得一个在词典中没有的缀-符串( String)为止。此时就输出表示当前前缀P的码字(Cod word)和字符C,并把P+C添加到词典中作为前缀( Prefix),然后开始处理字符流( Charstream) 中的下一个前缀 LZ78编码器的输出是码字-字符(w,C)对,每次输出一对到码字流中,与码字W相对应的 缀-符串( String)用字符C进行扩展生成新的缀-符串( String),然后添加到词典中。LZ78 码的具体算法如下 步骤1:在开始时,词典和当前前缀P都是空的 步骤2:当前字符C:=字符流中的下一个字符 步骤3:判断PC是否在词典中 (1)如果“是”:用C扩展P,让P:=P+C第4章 无损数据压缩 11 3 3 -- B 4 4 B B 5 5 -- C 6 6 B B (3,2) 7 8 A A B (7,3) 8 11 C C 在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这 也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS 的思想。例如，PKZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有 所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与赫夫曼编码联用，而PKZip则与 Shannon-Fano联用，它的后续版本也采用赫夫曼编码。 4.4.4 LZ78算法 在介绍LZ78算法之前，首先说明在算法中用到的几个术语和符号： (1) 字符流(Charstream)：要被编码的数据序列。 (2) 字符(Character)：字符流中的基本数据单元。 (3) 前缀(Prefix)： 在一个字符之前的字符序列。 (4) 缀-符串(String)：前缀＋字符。 (5) 码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。 (6) 码字流(Codestream)： 码字和字符组成的序列，是编码器的输出。 (7) 词典(Dictionary)： 缀-符串表。按照词典中的索引号对每条缀-符串(String)指 定一个码字(Code word)。 (8) 当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号 P表示。 (9) 当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用 符号C表示。 (10)当前码字(Current code word)： 在译码算法中使用，指当前处理的码字，用W表 示当前码字，String.W表示当前码字的缀-符串。 1. 编码算法 LZ78的编码思想是不断地从字符流中提取新的缀-符串(String)，通俗地理解为新“词 条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的 编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)， 从而达到压缩数据的目的。 在编码开始时词典是空的，不包含任何缀-符串(string)。在这种情况下编码器就输出 一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C，并把这 个字符C添加到词典中作为一个由一个字符组成的缀-符串(string)。在编码过程中，如果出 现类似的情况，也照此办理。在词典中已经包含某些缀-符串(String)之后，如果“当前前 缀P +当前字符C”已经在词典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到 获得一个在词典中没有的缀-符串(String)为止。此时就输出表示当前前缀P的码字(Code word)和字符C，并把P+C添加到词典中作为前缀(Prefix)，然后开始处理字符流(Charstream) 中的下一个前缀。 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的 缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编 码的具体算法如下： 步骤1： 在开始时，词典和当前前缀P都是空的。 步骤2： 当前字符C ：=字符流中的下一个字符。 步骤3： 判断P+C是否在词典中： (1) 如果“是”：用C扩展P，让P ：= P+C ；