最近由于课程设计需要做解压缩算法

特此来考察字典编码

1 导论

许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。 字典编码(dictionary encoding)技术（以下简称DE）就是属于这一类，这种技术属于无损压缩技术。

• DE根据的是
  
数据本身包含有重复代码

  这个特性 例如文本文件和光栅图像就具有这种特性

1.1 分类

种类很多，归纳起来大致有两类

1.1.1 查找正在压缩的字符序列是否在历史输入数据中出现过

用已经出现过的字符串替代重复部分，输出仅仅是指向之前出现过的字符串的“指针”

• 这里的“字典”指 用以前处理过的数据来表示编码过程中遇到的重复部分 这类编码的所有算法都是以
  
abraham lempel

  和
  
jakob ziv

  在1977年研究发表的称为
  
lz77

  算法为基础

1.1.2 从输入的数据中创建一个“短语字典(dictionary of the phrases)”

这种短语不一定是像“好好学习天天向上”和“你个糟老头子坏得很我信你个鬼”这类具有具体含义的短语，它可以是任意字符的组合 编码数据过程中当遇到已经在字典中出现的“短语”时，编码器就输出这个字典中的短语的“索引号”，而不是短语本身。

j.ziv

和

a.lempel

在1978年首次发表了这种编码方法的文章 在他们的研究基础上，

terry a.weltch

在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为

LZW(lempel-ziv walch)

压缩编码，首先在高速硬盘控制器上应用了这种算法

2 LZ77算法

2.1 常见术语

• 输入数据流(input stream) 要被压缩的字符序列
• 字符(character) 输入数据流中的基本单元。
• 编码位置(coding position) 输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符
• 前向缓冲存储器(Lookahead buffer) 存放从编码位置到输入数据流结束的字符序列的存储器。
• 窗口(window) 包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数
• 指针(pointer) 指向窗口中的匹配串且含长度的指针

核心是查找从前向缓冲存储器开始的最长的匹配串

2.2 执行步骤

1.把编码位置设置到输入数据流的起始位 2.查找窗口中最长的匹配串 3.以“(Pointer, Length) Characters”的格式输出 其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。 4.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移

(Length+1)

个字符，然后返回到步骤2

[例]

• “步骤” 编码步骤
• “位置” 编码位置，输入数据流中的第1个字符为编码位置1
• “匹配串” 窗口中找到的最长的匹配串
• “字符” 匹配后在前向缓冲存储器中的第1个字符
• “输出” 以“(Back_chars, Chars_length) Explicit_character”格式输出
  • (Back_chars, Chars_length) 指向匹配串的指针 告诉译码器
    
    在这个窗口中向后退
    
Back_chars

    个字符然后拷贝
    
Chars_length

    个字符到输出
    
  • Explicit_character 真实字符 例如，表
    
编码过程

    的输出
    
(5,2) C

    告诉译码器回退5个字符，然后拷贝2个字符“AB”

但wikipedia认为，粗体字理解成

从编码位置开始往回数Back_chars个字符，从该字符开始数起的字符串与接下来的Chars_length个字符完全相同


3 LZ78算法

3.1 术语和符号

• 字符流(Charstream) 要被编码的数据序列
• 字符(Character) 字符流中的基本数据单元
• 前缀(Prefix) 在一个字符之前的字符序列 -缀-符串(String) 前缀＋字符
• 码字(Code word) 码字流中的基本数据单元，代表字典中的一串字符
• 码字流(Codestream) 码字和字符组成的序列，编码器的输出
• 字典(Dictionary) 缀-符串表。按照字典中的索引号对每条缀-符串(String)指定一个码字(Code word)
• 当前前缀(Current prefix) 在编码算法中使用，指当前正在处理的前缀，用符号P表示。
• 当前字符(Current character) 在编码算法中使用，指当前前缀之后的字符，用符号C表示。
• 当前码字(Current code word) 在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串

3.2 编码算法

不断从字符流中提取新的缀-符串(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)，然后添加到字典中

具体算法

步骤1

在开始时，字典和当前前缀P都是空的

步骤2

当前字符C:=字符流中的下一个字符

步骤3

P+C 是否在字典中 (1) “是” 用C扩展P，让P := P+C (2) “否”     ① 输出与当前前缀P相对应的码字和当前字符C     ② 把字符串P+C 添加到字典中     ③ 令P:=空值 (3) 字符流中是否还有字符需要编码     ① “是” 返回到步骤2     ② “否” 若当前前缀P非空，输出相应于当前前缀P的码字，然后结束编码

3.3 译码算法

在译码开始时译码字典为空，它将在译码过程中从码字流中形成 每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在字典中的缀-符串，然后把当前码字的缀-符串string W 和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到字典中。在译码结束之后，重构的字典与编码时生成的字典完全相同

具体算法

步骤1

开始时字典空

步骤2

当前码字W :=码字流中的下一个码字

步骤3

当前字符C := 紧随码字之后的字符。

步骤4

把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C

步骤5

把string.W+C添加到字典中

步骤6

判断码字流中是否还有码字要译    (1) “是” 返回到步骤2    (2) “否” 结束

例

●“步骤” 编码步骤 ●“位置” 在输入数据中的当前位置 ●“字典” 添加到字典中的缀-符串，缀-符串的索引等于“步骤”序号 ●“输出” 以(当前码字W, 当前字符C)简化为(W, C)的形式输出

与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似

4 LZW算法

使用的术语与LZ78的类似，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)

4.1 编码原理

• LZW只输出代表字典中的缀-符串(String)的码字(code word) 意味着在开始时字典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)
• 由于所有可能出现的单个字符都事先包含在字典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在字典中搜索的第1个缀-符串有两个字符

4.2 编码算法

LZW编码是围绕称为

字典的转换表

来完成的 这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号

这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串 扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示 Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)

LZW编码器就是通过管理这个字典完成输入/输出的转换

• 输入是字符流(Charstream) 可以是8位ASCII字符组成的字符串
• 输出是用n位(例如12位)表示的码字流(Codestream) 码字代表单个字符或多个字符组成的字符串。

LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm) 在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在字典中出现的最长的前缀(Prefix) 用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C 这个新的缀-符串(String)是否要加到字典中，还要看字典中是否存有和它相同的缀-符串String

• 如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符
• 否则就把这个缀-符串(String)写到字典中生成一个新的前缀(Prefix)，并给一个代码

算法的执行

步骤1

开始时的字典包含所有可能的根(Root)，而当前前缀P是空的

步骤2

当前字符(C) :=字符流中的下一个字符

步骤3

判断缀-符串P+C是否在字典中 (1) “是” ：P := P+C (2) “否” ① 把代表当前前缀P的码字输出到码字流; ② 把缀-符串P+C添加到字典; ③ 令P := C

步骤4

码字流中是否还有码字要译 (1) “是” 回到步骤2 (2) “否” ① 把代表当前前缀P的码字输出到码字流 ② 结束

LZW编码算法可用伪码表示 开始时假设编码字典包含若干个已经定义的单个码字

4.3 译码算法

• 当前码字(Current code word) 当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串
• 先前码字(Previous code word) 先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串

算法开始时，译码字典与编码字典相同，包含所有可能的前缀根(roots) 在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)

之后输出当前缀-符串string.cW

，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到字典中。

执行步骤

步骤1：在开始译码时字典包含所有可能的前缀根(Root)。   步骤2：cW :=码字流中的第一个码字。   步骤3：输出当前缀-符串string.cW到码字流。   步骤4： 先前码字pW := 当前码字cW。   步骤5： 当前码字cW := 码字流中的下一个码字。   步骤6： 判断先前缀-符串string.pW是否在字典中    (1) 如果“是”，则：     ① 把先前缀-符串string.pW输出到字符流。     ② 当前前缀P :=

先前缀-符串string.pW

。     ③ 当前字符C :=当前前缀-符串string.cW的第一个字符。     ④ 把缀-符串P+C添加到字典。    (2) 如果“否”，则：     ① 当前前缀P :=

先前缀-符串string.pW

。     ② 当前字符C :=当前缀-符串string.cW的第一个字符。     ③ 输出缀-符串P+C到字符流，然后把它添加到字典中。   步骤7： 判断码字流中是否还有码字要译    (1) 如果“是”，就返回到步骤4。    (2) 如果“否”, 结束。

例

• “字典” 添加到字典中的缀-符串，它的索引在括号中

  每个译码步骤译码器读一个码字，输出相应的缀-符串，并把它添加到字典中 例如，在步骤4中，先前码字(2)存储在先前码字(pW)中，当前码字(cW)是(4)，当前缀-符串string.cW是输出(“A B”)，
  
  先前缀-符串string.pW
  
  (“B”)
  
  是用当前缀-符串string.cW
  
  (“A”)的第一个字符，其结果(“B A”) 添加到字典中，它的索引号是(6)

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作 对LZW算法进一步的改进是增加可变的码字长度，以及在字典中删除老的缀-符串 在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法