信息论基础第14次课_词典编码

1、信息论基础信息论基础 信息论与编码n词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。n实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。Dictionary codersn第一类词典编码的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。第一类词典编码n从输入的数据中创建一个“短语词典(dict

2、ionary of the phrases )”，这种短语不要求有具体的含义。编码时，当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中该“短语”的索引号。这种编码概念如图所示。第二类词典编码nLZ77(Abraham Lempel and Jacob Ziv in 1977) 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现的位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，这是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程

3、滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。LZ77算法算法中用到的几个术语n1.输入数据流(input stream)：要被压缩的字符序列。n2.字符(character)：输入数据流中的基本单元。n3.编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。n4.前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。n5.窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。n

4、6.指针(pointer)：指向窗口中的匹配串且含长度的指针。 LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。 1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。LZ

5、77编码的基本流程Step1: 将编码位置设置到输入数据流的开始位置。Step2:查找窗口中最长的匹配串。Step3:以“(pointer,length)characters”的格式输出，其中指针pointer为窗口中匹配字符串相对窗口边界的偏移，length表示匹配字符的长度，characters是前向缓冲器中的不匹配的第一个字符。Step4:如果前向缓冲器不空，则将编码位置和窗口向前移(length+1)个字符，然后返回到步骤Step2。LZ77编码的具体步骤n例待编码的数据流如表1，编码过程如表2。表表1 待编码数据流待编码数据流表表2 编码过程编码过程“(5,2) C”告诉译码器回退告

6、诉译码器回退5个字符，个字符，然后拷贝然后拷贝2个字符个字符“AB” 1234512457ABABABBCC(0,0) A(1,1) B(0,0) C(2,1) B(5,2) CLZ77编码举例LZ77译码举例nLZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。nLZSS(LempelZivStorerSzymanski)算法的思想是如果匹配串的长度比指针本身的长度长就输出指针(匹配串长度大于等于MIN_LENGTH)，否则就输出真实字符。另外要

7、输出额外的1bit标志位以区分是指针还是字符。LZSS算法1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。2、输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。LZSS编码的基本流程Step1：把编码位置置于输入数据流的开始位置。Step2：在前向缓冲器中查找与窗口中最

8、长的匹配串。Pointer :=匹配串指针Length :=匹配串长度Step3：判断匹配串长度Length是否大于等于最小匹配串长度(lengthMIN_LENGTH)如果“是”，输出指针，然后将编码位置向前移动Length个字符；如果“否”，输出前向缓冲器中的一个字符，然后将编码位置向前移动一个字符。Step4：如果前向缓冲器不空，就返回到步骤Step2。LZ77编码的执行步骤n例输入数据流如表3，编码过程如表4。表表3 输入数据流输入数据流表表4 编码过程编码过程(MIN_LENGTH=2)“(7,3)”告诉译码器回退告诉译码器回退7个字符，指个字符，指向连续的向连续的3个字符个字符“A

9、AB” 11A22AA33B44BB55C66BB(3,2)78AAB(7,3)811CCLZSS编码举例n在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, GZip, RAR, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。nLZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。LZSS算法应用nLZ78的编码思想是不断地从字符流

10、中提取新的缀-符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。LZ78算法n在编码开始时词典是空的，不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中的第一个字符C，并把这个字符C添加到词典中作为一个由一个字符组成的缀-符串。在词典中已经包含某些缀-符串之后，如果“当前前缀P +当前字符C”已经在词典中，就用字符C来扩

11、展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的缀-符串为止。此时就输出表示当前前缀P的码字和字符C，并把P+C添加到词典中作为前缀，然后开始下一个字符。LZ78算法nCharstream 要被编码的数据序列nCharacter 字符流中的基本数据单元nPrefix 前缀，在一个字符之前的字符序列nString 缀-符串，前缀+字符nCode word 码字，代表词典中的一串字符nCodestream 码字流，码字和字符组成的序列，即编码器输出nDictionary 词典，缀-符串表nCurrent prefix 当前正在处理的前缀，用P表示nCurrent character 当前

12、前缀之后的字符，用C表示nCurrent code word 当前正在处理的码字，用W表示，stream.W表示当前码字的缀-符串LZ78算法中用到的几个术语Step 1: 开始时，词典和当前前缀都是空的。Step 2: 当前字符C:=字符流中的下一个字符。Step 3: 判断P+C是否在词典中：(1) “是”:则 P:=P+C;(2) “否”:输出与当前P相对应的码字和当前字符C； 把字符串P+C添加到词典中； 令P:=空值。(3)判断字符流中是否还有字符需要编码： “是”，返回到步骤Step 2； “否”，若当前前缀P不空，输出相应于当前前缀P的码字，然后结束编码。LZ78编码的基本步骤表

13、表5 输入数据流输入数据流表表6 6 编码过程编码过程11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)LZ78编码举例nLZ78译码算法的思想：在译码开始时译码词典是空的，它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在词典中的缀-符串，然后把当前码字的缀-符串string.W 和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到词典中。在译码结束之后，重构的词典与编码时生成的词典完全相同。LZ78译码算法Step 1： 在开始时词典是空的。Step 2： 当前码字W

14、 :=码字流中的下一个码Step 3： 当前字符C := 紧随码字之后的字符Step 4： 把当前码字的缀-符串(string.W)输出到字 符流(Charstream)，然后输出字符C。Step 5： 把string.W+C添加到词典中。Step 6： 判断码字流中是否还有码字要译(1) 如果“是”，就返回到Step 2 。(2) 如果“否”，则结束。LZ78译码的具体步骤码字流：码字流：译码过程：译码过程：(0,A) (0,B) (2,C) (3,A) (2,A)1(0, A)AA2(0, B)BB3(2, C)BCBC4(3, A)BCABCA5(2, A)BABALZ78译码举例n在L

15、Z78基础上，Terry A.Weltch在1984年发表了改进这种编码算法的文章，称为LZW(Lempel-Ziv Waltch)压缩编码，首先在高速硬盘控制器上应用了这种算法。n在 LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语：前缀根(Root)，它是由单个字符串组成的缀-符串(String)。LZW算法nLZW编码的特点：LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流中出现的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。LZW编码是围绕称为词典的转换表来完成的。LZW

16、算法nLZW编码是围绕词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如表8所示。nLZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流 (Code stream)，码字代表单个字符或多个字符组成的字符串(String)。LZW编码算法表表8 8 词典词典 ASCII前缀根前缀根(Root)PrefixLZW算法nLZW编码器使用了一

17、种称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀加上下一个输入字符C也就是当前字符(Current character) ，形成新的缀-符串(String)：Prefix.C。当词典中存在有和它相同的缀-符串，这个缀-符串就变成前缀，继续输入新的字符，否则就把这个缀-符串写到词典中生成一个新的前缀，并给一个代码。LZW算法nStep 1：将词典初始化为包含所有可能的单字符(Root) ，当前前缀P初始化为空。nS

18、tep 2：当前字符(C):=字符流中的下一个字符；nStep 3：判断缀-符串P+C是否在词典中 (1) 如果“是”，则 P:= P+C /(用C扩展P)；(2) 如果“否”，则 把代表当前前缀P的码字输出到码字流； 把缀-符串P+C添加到词典; 令P:= C /(现在的P仅包含一个字符C)；nStep 4：判断码字流中是否还有码字要译(1) 如果“是”，则返回到Step 2；(2) 如果“否” 把代表当前前缀P的码字输出到码字流； 结束。 LZW算法的具体步骤输入数据流输入数据流：编码过程：编码过程：114A1225B2336B2447A4568A7693(最后字符C)BBAB AB AC

19、LZW算法举例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译码算法nStep 1：开始时词典包含所

20、有可能的前缀根(Root)。nStep 2：cW :=码字流中的第一个码字。nStep 3：输出当前缀-符串string.cW到码字流。nStep 4：先前码字pW := 当前码字cW。nStep 5：当前码字cW := 码字流中的下一个码字。nStep 6：判断先前缀-符串string.pW是否在词典中？ (1) 如果“是”，则： 把先前缀-符串string.pW输出到字符流。 当前前缀P:=先前缀-符串string.pW。LZW译码算法的具体步骤 当前字符C :=当前前缀-符串string.cW的第一个字符。 把缀-符串P+C添加到词典。(2) 如果“否”，则： 当前前缀P :=先前缀-符

21、串string.pW。 当前字符C :=当前缀-符串string.cW的第一个字符。 输出缀-符串P+C到字符流，然后把它添加到词典中。Step 7：判断码字流中是否还有码字要译码？(1) 如果“是”，就返回到步骤4。(2) 如果“否”, 结束。 LZW译码算法的具体步骤译码过程：译码过程：字典122473ABBAB?4: A?5: B?6: B?7: AB?4: AB5: BB6: BAAB?=?ABA7: ABA8: ABA?C8: ABACLZW译码举例LZW DecodingWord_abz0Index329798122SEND256STOP257itWordtttyy_bbity_biit_bin258Index259260261262263265266267268itt264Dictionary105Received1161161213298260262iInputtty_btty_258bit258i266_bi110n257STOP256SENDDictionaryj all n single-character，j1， 2，n jn+1 Prefix read first Character in Charstream while(C next Character)!=NULL) Begin If