第4章无损数据压缩 表4-09待编码的数据流 位置12|3456789 字符|AA| BCBBALBIC 表4-10编码过程 步骡位置|匹配串字符|输出 A|(0,0)A C(0,0)C B(2,1)B 57ABc[65,2)d 4.4.3LZSS算法 LZ7通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有 冗余信息。冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种 字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题,它 的思想是如果匹配串的长度比指针本身的长度长就输出指针,否则就输出真实字符。由于输 出的压缩数据流中包含有指针和字符本身,为了区分它们就需要有额外的标志位,即ID位 LZSS编码算法的具体执行步骤如下: (1)把编码位置置于输入数据流的开始位置。 (2)在前向缓冲存储器中查找与窗口中最长的匹配串 ① Pointer:=匹配串指针。 2 Length:=匹配串长度 (3)判断匹配串长度 Length是否大于等于最小匹配串长度 Length≥ MIN LENGTH), 如果“是”:输出指针,然后把编码位置向前移动 Length个字符。 如果“否”:输出前向缓冲存储器中的第1个字符,然后把编码位置向前移动一个 (4)如果前向缓冲存储器不是空的,就返回到步骤2 [例4.5]编码字符串如表4-11所示,编码过程如表4-12所示。现说明如下 (1)“步骤”栏表示编码步骤。 (2)“位置”栏表示编码位置,输入数据流中的第1个字符为编码位置1 (3)“匹配”栏表示窗口中找到的最长的匹配串。 (4)“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符 (5)“输出”栏的输出为 ①如果匹配串本身的长度 Length≥ MIN LENGTH,输出指向匹配串的指针,格式 为( Back chars, Chars length)。该指针告诉译码器“在这个窗口中向后退 Back chars个字符然后拷贝 Chars length个字符到输出” ②如果匹配串本身的长度 Length≤ MIN LENGTH,则输出真实的匹配串。 表4-11输入数据流 12|34567 AABIBICBIB 表4-12编码过程 MIN LENGTH=2) 步骤位置匹配串输出第4章 无损数据压缩 10 表4-09待编码的数据流 位置 1 2 3 4 5 6 7 8 9 字符 A A B C B B A B C 表4-10 编码过程 步骤 位置 匹配串 字符 输出 1 1 -- A (0,0) A 2 2 A B (1,1) B 3 4 -- C (0,0) C 4 5 B B (2,1) B 5 7 A B C (5,2) C 4.4.3 LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有 冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种 字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它 的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输 出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。 LZSS编码算法的具体执行步骤如下： (1) 把编码位置置于输入数据流的开始位置。 (2) 在前向缓冲存储器中查找与窗口中最长的匹配串 ① Pointer ：=匹配串指针。 ② Length ：=匹配串长度。 (3) 判断匹配串长度Length是否大于等于最小匹配串长度(Length  MIN_LENGTH) ， 如果“是”：输出指针，然后把编码位置向前移动Length个字符。 如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个 字符。 (4) 如果前向缓冲存储器不是空的，就返回到步骤2。 [例4.5] 编码字符串如表4-11所示，编码过程如表4-12所示。现说明如下： (1) “步骤”栏表示编码步骤。 (2) “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。 (3) “匹配”栏表示窗口中找到的最长的匹配串。 (4) “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。 (5) “输出”栏的输出为： ① 如果匹配串本身的长度Length  MIN_LENGTH，输出指向匹配串的指针，格式 为(Back_chars, Chars_length)。该指针告诉译码器“在这个窗口中向后退 Back_chars个字符然后拷贝Chars_length个字符到输出”。 ② 如果匹配串本身的长度Length  MIN_LENGTH，则输出真实的匹配串。 表4-11 输入数据流 位置 1 2 3 4 5 6 7 8 9 10 11 字符 A A B B C B B A A B C 表4-12 编码过程(MIN_LENGTH = 2) 步骤 位置 匹配串 输出 1 1 -- A 2 2 A A