转载

聊聊字典编码

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

特此来考察字典编码

1 导论

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

  • DE根据的是数据本身包含有重复代码这个特性
    例如文本文件和光栅图像就具有这种特性

1.1 分类

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

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

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

  • 这里的“字典”指 用以前处理过的数据来表示编码过程中遇到的重复部分
    这类编码的所有算法都是以abraham lempeljakob ziv在1977年研究发表的称为lz77算法为基础

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

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

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

步骤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算法

正文到此结束
本文目录