第4章无损数据压缩 囗国四囗区国囗四四 图407第二类词典法编码概念 J.Ziv和A. Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础上 Terry A. Welch在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为 Lzw( Lempel- Ziv Walch)压缩编码,首先在高速硬盘控制器上应用了这种算法 4.4.2LZ77算法 为了更好地说明LZ7算法的原理,首先介绍算法中用到的几个术语: (1)输入数据流( Input stream):要被压缩的字符序列。 (2)字符( character):输入数据流中的基本单元。 (3)编码位置( coding position):输入数据流中当前要编码的字符位置,指前向缓冲 存储器中的开始字符。 (4)前向缓冲存储器( Lookahead buffer):存放从编码位置到输入数据流结束的字符序 列的存储器 (5)窗口( window):指包含W个字符的窗口,字符是从编码位置开始向后数也就是最后 处理的字符数 (6)指针( pointer):指向窗口中的匹配串且含长度的指针 LZ7编码算法的核心是査找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执 行步骤如下 (1)把编码位置设置到输入数据流的开始位置。 (2)查找窗口中最长的匹配串 (3)以“( Pointer, Length) Characters”的格式输出,其中 Pointer是指向窗口中匹 配串的指针, Length表示匹配字符的长度, Characters是前向缓冲存储器中的不 匹配的第1个字符。 (4)如果前向缓冲存储器不是空的,则把编码位置和窗口向前移( Length+1)个字符, 然后返回到步骤2。 [例4.匀]待编码的数据流如表4-09所示,编码过程如表4-10所示。现作如下说明: “步骤”栏表示编码步骤。 ②)“位置”栏表示编码位置,输入数据流中的第1个字符为编码位置1 (3)“匹配串”栏表示窗口中找到的最长的匹配串。 (4)“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符 (5)“输出”栏以“( Back chars, Chars length) Explicit character”格式输出 其中,( Back chars, Chars length)是指向匹配串的指针,告诉译码器“在这个 窗口中向后退 Back chars个字符然后拷贝 Chars length个字符到输出” Explicit character是真实字符。例如,表4-10中的输出“(5,2)C”告诉译码器 回退5个字符,然后拷贝2个字符“AB第4章 无损数据压缩 9 图4-07 第二类词典法编码概念 J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础上， Terry A.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为 LZW(Lempel-Ziv Walch)压缩编码，首先在高速硬盘控制器上应用了这种算法。 4.4.2 LZ77算法 为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语： (1) 输入数据流(input stream)：要被压缩的字符序列。 (2) 字符(character)：输入数据流中的基本单元。 (3) 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲 存储器中的开始字符。 (4) 前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序 列的存储器。 (5) 窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后 处理的字符数。 (6) 指针(pointer)：指向窗口中的匹配串且含长度的指针。 LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执 行步骤如下： (1) 把编码位置设置到输入数据流的开始位置。 (2) 查找窗口中最长的匹配串。 (3) 以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹 配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不 匹配的第1个字符。 (4) 如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符， 然后返回到步骤2。 [例4.4] 待编码的数据流如表4-09所示，编码过程如表4-10所示。现作如下说明： (1) “步骤”栏表示编码步骤。 (2) “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。 (3) “匹配串”栏表示窗口中找到的最长的匹配串。 (4) “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。 (5) “输出”栏以“(Back_chars, Chars_length) Explicit_character”格式输出。 其中，(Back_chars, Chars_length)是指向匹配串的指针，告诉译码器“在这个 窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”， Explicit_character是真实字符。例如，表4-10中的输出“(5,2) C”告诉译码器 回退5个字符，然后拷贝2个字符“AB