最近由于课程设计需要做解压缩算法
特此来考察字典编码
许多场合,开始时不知道要编码数据的统计特性,也不一定允许你事先知道它们的统计特性。因此,人们提出了许许多多的数据压缩方法,企图用来对这些数据进行压缩编码,在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。 字典编码(dictionary encoding)技术(以下简称DE)就是属于这一类,这种技术属于无损压缩技术。
数据本身包含有重复代码
这个特性
例如文本文件和光栅图像就具有这种特性种类很多,归纳起来大致有两类
用已经出现过的字符串替代重复部分,输出仅仅是指向之前出现过的字符串的“指针”
abraham lempel
和jakob ziv
在1977年研究发表的称为lz77
算法为基础这种短语不一定是像“好好学习天天向上”和“你个糟老头子坏得很我信你个鬼”这类具有具体含义的短语,它可以是任意字符的组合
编码数据过程中当遇到已经在字典中出现的“短语”时,编码器就输出这个字典中的短语的“索引号”,而不是短语本身。
j.ziv
和a.lempel
在1978年首次发表了这种编码方法的文章
在他们的研究基础上,terry a.weltch
在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为LZW(lempel-ziv walch)
压缩编码,首先在高速硬盘控制器上应用了这种算法
核心是查找从前向缓冲存储器开始的最长的匹配串
1.把编码位置设置到输入数据流的起始位
2.查找窗口中最长的匹配串
3.以“(Pointer, Length) Characters”的格式输出
其中Pointer是指向窗口中匹配串的指针,Length表示匹配字符的长度,Characters是前向缓冲存储器中的不匹配的第1个字符。
4.如果前向缓冲存储器不是空的,则把编码位置和窗口向前移(Length+1)
个字符,然后返回到步骤2
待编码的数据流
编码过程
Back_chars
个字符然后拷贝Chars_length
个字符到输出 编码过程
的输出(5,2) C
告诉译码器回退5个字符,然后拷贝2个字符“AB”但wikipedia认为,粗体字理解成
从编码位置开始往回数Back_chars个字符,从该字符开始数起的字符串与接下来的Chars_length个字符完全相同
原文
不断从字符流中提取新的缀-符串(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),然后添加到字典中
在开始时,字典和当前前缀P都是空的
当前字符C:=字符流中的下一个字符
P+C 是否在字典中 (1) “是” 用C扩展P,让P := P+C (2) “否” ① 输出与当前前缀P相对应的码字和当前字符C ② 把字符串P+C 添加到字典中 ③ 令P:=空值 (3) 字符流中是否还有字符需要编码 ① “是” 返回到步骤2 ② “否” 若当前前缀P非空,输出相应于当前前缀P的码字,然后结束编码
在译码开始时译码字典是空的,它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时,码字就参考已经在字典中的缀-符串,然后把当前码字的缀-符串string.W 和字符C输出到字符流(Charstream),而把当前缀-符串(string.W+C)添加到字典中。在译码结束之后,重构的字典与编码时生成的字典完全相同。LZ78译码的具体算法如下: 步骤1: 在开始时字典是空的。 步骤2: 当前码字W :=码字流中的下一个码字。 步骤3: 当前字符C := 紧随码字之后的字符。 步骤4: 把当前码字的缀-符串(string.W)输出到字符流(Charstream),然后输出字符C。 步骤5: 把string.W+C添加到字典中。 步骤6: 判断码字流中是否还有码字要译 (1) 如果“是”,就返回到步骤2。 (2) 如果“否”,则结束。
[例4.6] 编码字符串如表4-13所示,编码过程如表4-14所示。现说明如下: ●“步骤”栏表示编码步骤。 ●“位置”栏表示在输入数据中的当前位置。 ●“字典”栏表示添加到字典中的缀-符串,缀-符串的索引等于“步骤”序号。 ●“输出”栏以(当前码字W, 当前字符C)简化为(W, C)的形式输出。 表4-13 编码字符串
位置
1
2
3
4
5
6
7
8
9
字符
A
B
B
C
B
C
A
B
A
表4-14 编码过程
步骤
位置
字典
输出
1
1
A
(0,A)
2
2
B
(0,B)
3
3
B C
(2,C)
4
5
B C A
(3,A)
5
8
B A
(2,A)
与LZ77相比,LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目,而压缩率与LZ77类似。
LZW算法
在LZW算法中使用的术语与LZ78使用的相同,仅增加了一个术语—前缀根(Root),它是由单个字符串组成的缀-符串(String)。在编码原理上,LZW与LZ78相比有如下差别:①LZW只输出代表字典中的缀-符串(String)的码字(code word)。这就意味在开始时字典不能是空的,它必须包含可能在字符流出现中的所有单个字符,即前缀根(Root)。②由于所有可能出现的单个字符都事先包含在字典中,每个编码步骤开始时都使用一字符前缀(one-character prefix),因此在字典中搜索的第1个缀-符串有两个字符。 现将LZW编码算法和译码算法介绍如下。
1. 编码算法 LZW编码是围绕称为字典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列,并且为每个表项分配一个码字(Code word),或者叫做序号,如表4-15所示。这张转换表实际上是把8位ASCII字符集进行扩充,增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位,12位可以有4096个不同的12位代码,这就是说,转换表有4096个表项,其中256个表项用来存放已定义的字符,剩下3840个表项用来存放前缀(Prefix)。 表4-15 字典
码字(Code word)
前缀(Prefix)
1
…
…
193
A
194
B
…
…
255
…
…
1305
abcdefxyF01234
…
…
LZW编码器(软件编码器或硬件编码器)就是通过管理这个字典完成输入与输出之间的转换。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),并给一个代码。 LZW编码算法的具体执行步骤如下: 步骤1: 开始时的字典包含所有可能的根(Root),而当前前缀P是空的; 步骤2: 当前字符(C) :=字符流中的下一个字符; 步骤3: 判断缀-符串P+C是否在字典中 (1) 如果“是”:P := P+C // (用C扩展P); (2) 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 把缀-符串P+C添加到字典; ③ 令P := C //(现在的P仅包含一个字符C); 步骤4: 判断码字流中是否还有码字要译 (1) 如果“是”,就返回到步骤2; (2) 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 结束。 LZW编码算法可用伪码表示。开始时假设编码字典包含若干个已经定义的单个码字。例如,256个字符的码字,用伪码可以表示成:
Dictionary[j] ← all n single-character, j=1, 2, …,n j ← n+1 Prefix ← read first Character in Charstream while((C ← next Character)!=NULL) Begin If Prefix.C is in Dictionary Prefix ← Prefix.C else Codestream ← cW for Prefix Dictionary[j] ← Prefix.C j ← n+1 Prefix ← C end Codestream ← cW for Prefix
2. 译码算法 LZW译码算法中还用到另外两个术语:①当前码字(Current code word):指当前正在处理的码字,用cW表示,用string.cW表示当前缀-符串;②先前码字(Previous code word):指先于当前码字的码字,用pW表示,用string.pW表示先前缀-符串。 LZW译码算法开始时,译码字典与编码字典相同,它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW),从码字流中读当前码字(cW)之后输出当前缀-符串string.cW,然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到字典中。 LZW译码算法的具体执行步骤如下: 步骤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) 如果“否”, 结束。 LZW译码算法可用伪码表示如下:
Dictionary[j] ← all n single-character, j=1, 2, …,n j ← n+1 cW ← first code from Codestream Charstream ← Dictionary[cW] pW ← cW While((cW ← next Code word)!=NULL) Begin If cW is in Dictionary Charstream ← Dictionary[cW] Prefix ← Dictionary[pW] cW ← first Character of Dictionary[cW] Dictionary[j] ← Prefix.cW j ← n+1 pW ← cW else Prefix ← Dictionary[pW] cW ← first Character of Prefix Charstream ← Prefix.cW Dictionary[j] ← Prefix.C pW ← cW j ← n+1 end [例4.7] 编码字符串如表4-16所示,编码过程如表4-17所示。现说明如下: ●“步骤”栏表示编码步骤; ●“位置”栏表示在输入数据中的当前位置; ●“字典”栏表示添加到字典中的缀-符串,它的索引在括号中; ●“输出”栏表示码字输出。
表4-16 被编码的字符串
位置
1
2
3
4
5
6
7
8
9
字符
A
B
B
A
B
A
B
A
C
表4-17 LZW的编码过程
步骤
位置
字典
输出
(1)
A
(2)
B
(3)
C
1
1
(4)
A B
(1)
2
2
(5)
B B
(2)
3
3
(6)
B A
(2)
4
4
(7)
A B A
(4)
5
6
(8)
A B A C
(7)
6
--
--
--
(3)
表4-18解释了译码过程。每个译码步骤译码器读一个码字,输出相应的缀-符串,并把它添加到字典中。例如,在步骤4中,先前码字(2)存储在先前码字(pW)中,当前码字(cW)是(4),当前缀-符串string.cW是输出(“A B”),先前缀-符串string.pW ("B")是用当前缀-符串string.cW ("A")的第一个字符,其结果("B A") 添加到字典中,它的索引号是(6)
表4-18 LZW的译码过程
步骤
代码
字典
输出
(1)
A
(2)
B
(3)
C
1
(1)
--
--
A
2
(2)
(4)
A B
B
3
(2)
(5)
B B
B
4
(4)
(6)
B A
A B
5
(7)
(7)
A B A
A B A
6
(3)
(8)
A B A C
C
LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度,以及在字典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。 LZW算法取得了专利,专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司),除了商业软件生产公司之外,可以免费使用LZW算法。