信息论基础第14次课_词典编码解题.ppt

信息论基础 —信息论与编码 词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。 Dictionary coders 第一类词典编码的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。 第一类词典编码 从输入的数据中创建一个“短语词典(dictionary of the phrases )”，这种短语不要求有具体的含义。编码时，当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中该“短语”的索引号。这种编码概念如图所示。 第二类词典编码 LZ77(Abraham Lempel and Jacob Ziv in 1977) 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现的位置和长度。 使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，这是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率； 随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。 LZ77算法 算法中用到的几个术语 1.输入数据流(input stream)：要被压缩的字符序列。 2.字符(character)：输入数据流中的基本单元。 3.编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 4.前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 5.窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。 6.指针(pointer)：指向窗口中的匹配串且含长度的指针。 LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。 1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。 2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。 3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。 LZ77编码的基本流程 Step1: 将编码位置设置到输入数据流的开始位置。 Step2:查找窗口中最长的匹配串。 Step3:以“(pointer,length)characters”的格式输出，其中指针pointer为窗口中匹配字符串相对窗口边界的偏移，length表示匹配字符的长度，characters是前向缓冲器中的不匹配的第一个字符。 Step4:如果前向缓冲器不空，则将编码位置和窗口向前移(length+1)个字符，然后返回到步骤Step2。 LZ77编码的具体步骤 〖例〗待编码的数据流如表1，编码过程如表2。 位置 字符 1 2 3 4 5 6 7 8 9 A A B C B B A B C 步骤 位置 匹配串 字符 输出 表1 待编码数据流　 表2 编码过程 “(5,2) C”告诉译码器回退5个字符，然后拷贝2个字符“AB” 1 2 3 4 5 1 2 4 5 7 － A － B AB A B B C C (0,0) A (1,1) B (0,0) C (2,1) B (5,2) C LZ77编码举例 A A B C B B A B C A 步骤 位置 匹配串 输出 1 1 －－ 0, 0, A 2 2 A 1, 1, B 3 4 －－ 0, 0, C 4 5 B 2, 1, B 5 7 ABC 5, 3, A LZ77译码举例 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 LZSS(Lempel–Ziv–Storer–Szymanski)算法的思想是如果匹配串的长度比指针本身的长度长就输出指针(匹配串长度大于等于MIN_LENGTH)，否则就输出真实字符。另