第2章 数据无损压缩.pptVIP

2.4 词典编码 2.4.4 LZ78算法 【例2.7】待编码字符串(字符流)如下表，进行LZ78编码。 位置 1 2 3 4 5 6 7 8 9 字符 A B B C B C A B A 编码位置 当前字符Ch := A。 Pr :=B。 Pr+Ch(即BA)不在词典中，则 (1) 输出(Pr对应的码字,Ch)， 即(2,A)； (2) 把Pr+Ch，即BA添加到词典中； (3) 令Pr := 空值。 结束编码。 步骤 编码位置 词典 输出 1 1 A (0,A) 2 2 B (0,B) 3 3 BC (2,C) 4 5 BCA (3,A) 5 8 BA (2,A) 步骤 词典 步骤 词典 1 A 3 BC 2 B 4 BCA 2.4 词典编码 2.4.4 LZ78算法 【例2.7】待编码字符串(字符流)如下表，进行LZ78编码。 LZ78的编码思想：不断地从字符流中提取新的缀-符串（新“词条”），然后用“代号”也就是码字表示这个“词条”。这样一来，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。 步骤 编码位置 词典 输出 1 1 A (0,A) 2 2 B (0,B) 3 3 BC (2,C) 4 5 BCA (3,A) 5 8 BA (2,A) 位置 1 2 3 4 5 6 7 8 9 字符 A B B C B C A B A 编码过程 2.4 词典编码 2.4.4 LZ78算法 与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串比较的次数，而压缩率与LZ77类似。 LZ78译码算法如下： 【步骤1】 在开始时词典是空的。 【步骤2】 当前码字W ：=码字流中的下一个码字。 【步骤3】 当前字符C ：= 紧随码字之后的字符。 【步骤4】把当前码字的缀-符串(string.W)输出到字符流，然后输出字符C。 【步骤5】 把string.W+C添加到词典中。 【步骤6】判断码字流中是否还有码字要译　(1) 如果“是”，就返回到步骤2。　(2) 如果“否”，则结束。 2.4 词典编码 2.4.5 LZW算法 LZW编码算法是围绕称为词典的转换表来完成的，如下表“LZW词典” 码字 前缀 1 … … 193 A 194 B … … 码字 前缀 255 … … 1305 abcdefxyF01234 … … 上表实际扩充了8位ACSII字符集，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符。 Welch论文中采用12位代码，共4096个表项，256个表项存放已定义字符，3840个表项存放前缀。 2.4 词典编码 2.4.5 LZW算法 在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串。 在编码原理上，LZW与LZ78相比有如下差别： (1) LZW只输出代表词典中的缀-符串的码字(code word)。则词典初始不能为空，它必须包含前缀根。 (2) 由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)。 (3) 重构词典时不需要在码字流中加入额外的符号。 LZW编码器使用了贪婪分析算法(greedy parsing algorithm)，即每一次分析都要串行地检查来自字符流的字符串，从中分解出已经识别的最长的字符串(即已在词典中出现的最长前缀)。 2.4 词典编码 2.4.5 LZW算法 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 LZW编码算法伪代码 2.4 词典编码 2.4.5 LZW算法 LZW算法得到普遍采用，它的速度比LZ77算法快，因为它不需要执行那么多的缀-符串比较操作。 对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串