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

信息论基础 —信息论与编码 Dictionary coders 词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。 第一类词典编码 第一类词典编码的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。 第二类词典编码 从输入的数据中创建一个“短语词典(dictionary of the phrases )”，这种短语不要求有具体的含义。编码时，当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中该“短语”的索引号。这种编码概念如图所示。 LZ77算法 LZ77(Abraham Lempel and Jacob Ziv in 1977) 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现的位置和长度。 算法中用到的几个术语 1.输入数据流(input stream)：要被压缩的字符序列。 2.字符(character)：输入数据流中的基本单元。 3.编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 4.前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 5.窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。 6.指针(pointer)：指向窗口中的匹配串且含长度的指针。 LZ77编码的基本流程 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。 LZ77译码举例 LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 LZSS(Lempel–Ziv–Storer–Szymanski)算法的思想是如果匹配串的长度比指针本身的长度长就输出指针(匹配串长度大于等于MIN_LENGTH)，否则就输出真实字符。另外要输出额外的1bit标志位以区分是指针还是字符。 LZSS编码的基本流程 1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。 2、输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。 3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。 LZ77编码的执行步骤 Step1：把编码位置置于输入数据流的开始位置。 Step2：在前向缓冲器中查找与窗口中最长的匹配串。 ①Pointer :=匹配串指针 ②Length :=匹配串长度 Step3：判断匹配串长度Length是否大于等于最小匹配串长度(length≥MIN_LENGTH) 如果“是”，输出指针，然后将编码位置向前移动Leng