基于统计概率的信源编码类:这类码要求信源是平稳的,且已知统计概率,如:Shannon码、Fano码、Huffman码和算术码等。工程上,一些信源的统计特性难以得到,或不存在。基于数据串特性的信源编码类:这种不依赖于概率统计特性的编码方法,称为通用编码。1977—1978年,以色列学者J.Ziv和A.Lempel提出一种通用编码,称为LZ码,也称为字典码。典型的字典码包括:LZ-77码,LZ-78码,LZW码,以及改进或变形的多种字典码。举例说明字典码的思想:

(1)A和B两人约定用相同的字典(例如辞海)互相通信。

(2)A将信文中每个单词用二元标识符(k,l)代替,当逐个单词被替代后,就将标识符序列发给B。其中,k为单词在字典中的页数;l为单词在此页的位置次序。

(3)B收到标识符序列后按标识符恢复单词。

如果标识符号数据量少于单词符号数据量,就实现了文本压缩。

LZ-77编码

LZ-77编码算法的主要思想:把已输入的数据流存储起来,作为字典使用。编码器为输入数据流开设一个滑动窗口,其长可达几千字节,将输入数据存在窗内(用实线表示)做字典使用,窗口外是待编码数据,长只有几十字节(用虚线表示),如图7.10所示。

图7.10　LZ-77编码算法的主要思想

LZ-77编码用三元标识(k,l,x)给数据编码,其中k为滑动窗(字典)内从尾部自右向左搜索的字符位数,称为移位数;l为滑动窗内可以与滑动窗外有相同符号的字符串的长度,称为匹配字符串(匹配串)长度;x为窗外已找到的匹配串后的首字符。

LZ-77编码器:滑动窗口初始化状态为空。若窗内没有与待编码字符x匹配的字符时,编码为(0,0,x)。以图7.10为例说明编码过程:待编码缓存器中首符号为“1”,在字典“2.71828”中搜索“1”,移位数k=4,匹配串“1828”,串长为l=4,匹配串后的首字符为。当用数据编码后,表示编码后的字符串为“18284”,字典更新是将已编码的5位数据字符串“18284”送入滑动窗口,字典更新为“2.7182818284”;同时用后续5位数据“04523”送入待编码缓存器中,待编码缓存器更新为“5904523”。

【例7.15】用LZ-77编码对自然对数的底e进行编码。

解:自然对数的底e为

仅对e的前若干位进行编码。LZ-77编码的过程如表7.7所示。结果为:(0,0,2),(0,0,.),(0,0,7),(0,0,1),(0,0,8),(5,1,8),(4,4,4),(0,0,5),(0,0,9),(0,0,0),(4,2,2),…

表7.7　LZ-77编码的过程

【例7.16】对编码结果:(0,0,2),(0,0,.),(0,0,7),(0,0,1),(0,0,8),(5,1,8),(4,4,4),(0,0,5),(0,0,9),(0,0,0),(4,2,2),…进行译码。

解:译码过程如表7.8所示。译码结果为e=2.7182818284590452…。

表7.8　LZ-77译码过程

续表

LZ-78编码

LZ-78编码是对LZ-77编码算法的重要改进,即取消窗口,已编码的字符串全都存在字典内,标识改为二元标识的形式(k,x),其中,k为指向字典的指针(即段号数),x为待编码字符,匹配串长度l隐含在字典中。(0,x)为字符x首次出现,表示的字符串为“x”;(k,x),k＞0为字符x前是第k号字符段,表示的字符串为“第k号字符段+x”。

LZ-78的编码算法是一种分段编码算法。设信源符号集A:{a1,a2,…,ar}共r个符号,设输入信源符号序列为:x0x1x2…xn,xi∈A,编码就是将此序列分成不同的m段。分段原则是:

(1)先取第一个符号作为第一段,然后再继续分段;(www.daowen.com)

(2)若出现有与前面相同符号时,就再添加紧跟后面的一个符号一起组成一个段,以使与前面的段不同;

(3)尽可能取最少个连着的信源符号,并保证各段都不相同。直至信源符号序列结束。

将不同的段看成短语,得对应的短语字典表。若编成二元码,段号用二进数表示,段号所需码长为l=logm,其中m为段号数。

LZ-78的编码原则:

(1)对字符段X编码,若字符段X仅由某一个信源符号组成,则编码为(0,x)。

(2)若字符段X至少由两个或两个以上信源符号组成时,记X=x1x2…xr,(xi∈A),则先在字典表内搜索与符号串x1x2…xr相匹配的短语的位置顺序号,其值就是指针k,将最后一个信源符号x0作为标识的第二项x,即得X的码字(k,x)。

【例7.17】信源符号集A:{a,b,c,d},信源序列为aacdbbaaadcacbaaadccacbbbaadcbacba,对其进行LZ-78编码。

解:信源符号a,b,c,d二元编码,a→00,b→01,c→10,d→11。其LZ-78编码的过程如表7.9所示。

第1段X=a,单符号,字典表内无匹配串,编码为(0,a),并将a存入字典表中;第2段X=ac,两符号,去掉最后符号c,仅余a,与字典表内的刚存入的a匹配,故指针k=1,则ac编码为(1,c)。按编码原则,逐步给其余段编码。此例共15段,段号用4位二进数,最后编码为(0000,00),(0001,10),(0000,11),(0000,01),(0100,00),(0001,00),(0011,10),(0010,01),(0110,00),(0111,10),(1000,01),(0101,00),(0111,01),(1000,00)。

表7.9　LZ-78编码的过程

LZW编码

1984年,T.A.Welch(韦尔奇)开发了LZW编码。是LZ系列码中应用最广、变形最多的LZ算法。标识改为一元标识的形式k,即指向字典的指针,(区别于LZ-77,LZ-78)。

LZW编码算法:先建立初始字典,再分解输入流为短语词条,这个短语若不在初始字典内,就将其存入字典,这些新词条和初始字典共同构成编码器的字典。初始字典可以由信源符号集构成,每个符号是一个词条。更一般的,是ASCII码(256项)存入初始字典。

LZW码的编码原理:

(1)先建立初始化字典。

(2)然后将待编码的输入数据流分解成短语词条。

编码器要逐个输入字符,并累积串联成一个字符串,即短语I。若I是已有的词条,则输入下一字符x,形成新词条Ix。当I在字典内,Ix不在字典内时,编码器首先输出指向字典内词条I的指针(即I的相应码字);再将Ix作为新词条存入字典,并为其确定顺序号;然后把x赋值给I,当作新词条的首字符。

(3)重复上述过程,直到输入流都处理完为止。

【例7.18】信源符号集A:{a,b,c,d},信源序列为aacdbbaaadcacbaaadccacbbbaadcbacba,对其进行LZW编码。

解:信源符号a,b,c,d二元编码,a→00,b→01,c→10,d→11。其LZW编码的过程如表7.10所示。先建初始化字典,将a,b,c,d预置为字典的前4项。信源序列为:aacdbbaaadcacbaaadccacbbbaadcbacba,按编码原则,将首字符a预置为I,即I=a,

搜索后知I在字典内,继续输入第二项a,即有Ix=aa,搜索后知Ix不在字典内。则输出字典词条I=a的指针(输出码字1),把Ix=aa作为新词条(编码5)存入字典,再将x赋值给I(此时I=a),作新词条的首字符,重复上述做法,得到编码表。

LZW码字:1,1,3,4,2,2,5,1,4,3,6,10,5,13,14,3,9,16,13,10,20,1,EOF。

表7.10　编码表

LZW码解码:输入第1个码字(即第1个指针),并从字典中取回一个词条I,并将I输出,同时将Ix存入解码字典中。(x未知,是下一次从字典中读取的词条的首个字符)再输入下一个指针,又从字典中取回词条J,将其输出,并把J的首字符赋予上一步存入字典的词条Ix的x,(此时,Ix已完全确定)重复上述过程,则自动重建了译码表,并将译码输出。