2常用数据压缩技术.ppt

* 注意能量的概念 * 注意西格码的计算。 * KL变换的程序设计 要求：给出源代码、执行程序、测试结果和说明文档。 输入数据流 ? 编码过程(MIN_LENGTH = 2) 步骤 位置 匹配串 输出 1 1 -- A 2 2 A A 3 3 -- B 4 4 B B 5 5 -- C 6 6 B B (3,2) 7 8 A A B (7,3) 8 11 C C ? 位置 1 2 3 4 5 6 7 8 9 10 11 字符 A A B B C B B A A B C LZ78算法 几个术语 字符流(Charstream)：要被编码的数据序列，即输入的数据流 字符(Character)：字符流中的基本数据单元 前缀(Prefix)：在一个字符之前的字符序列 缀?符串(String)：前缀＋字符 码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符 码字流(Codestream)：码字和字符组成的序列，是编码器的输出 LZ78算法 词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀?符串(String)指定一个码字(Code word) 当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。 当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。 当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀?符串。 LZ78算法 LZ78的编码思想是不断地从字符流中提取新的缀?符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。 LZ78算法 LZ78 编码的具体算法如下: 步骤1： 在开始时，词典和当前前缀 P 都是空的。 步骤2： 当前字符 C := 字符流中的下一个字符。 步骤3： 判断 P+C 是否在词典中： (1) 如果“是”：用C扩展P，让 P := P+C ； (2) 如果“否”： ① 输出与当前前缀 P 相对应的码字和当前字符 C； ② 把字符串 P+C 添加到词典中。 ③ 令 P :=空值。 (3) 判断字符流中是否还有字符需要编码 ① 如果“是”：返回到步骤2。 ② 如果“否”：若当前前缀 P 不是空的，输出相应于当前前缀 P 的码字， 然后结束编码。 编码字符串 位置 1 2 3 4 5 6 7 8 9 字符 A B B C B C A B A ? 编码过程 步骤 位置 词典 输出 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) 1 D=‘’ P=‘’ C=‘A’ P+C=‘A’ N: output (0,A) D1=‘A’ P=‘’ 2 C=‘B’ P=‘’ P+C=‘B’ N: output (0,B) D2=‘B’ P=‘’ 3 C=‘B’ P=‘’ P+C=‘B’ Y: P=P+C=‘B’ 4 C=‘C’ P=‘B’ P+C=‘BC’ N: output (2,C) D3=‘BC’ P=‘’ 5 C=‘B’ P=‘’ P+C=‘B’ Y: P=P+C=‘B’ 6 C=‘C’ P=‘B’ P+C=‘BC’ Y: P=P+C=‘BC’ 7 C=‘A’ P=‘BC’ P+C=‘BCA’ N: output (3,A) D4=‘BCA’ P=‘’ 8 C=‘B’ P=‘’ P+C=‘B’ Y: P=P+C=‘B’ LZW算法 LZW与LZ78 的差别 LZW只输出代表词典中的缀?符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root) ； 由于所有可能出现的单个字符都事先包含在词典中，每个编码