LZ-78编码算法：原理与应用

LZ-78编码算法源自对LZ-77编码算法的重要改进，即取消窗口，将已编码的字符串全都存在字典内，还将标识改为二元标识的形式（k，x），其中，k是指向字典的指针（即段号数），x是待编码字符，匹配串长度l隐含在字典中。

LZ-78的编码算法是一种分段编码算法。设信源符号集A：{a₀，a₁，…，a_r-1}，共r个符号，输入信源符号序列为

x₀x₁x₂…x_n，x_i∈A

编码就是将此序列分成不同的m段。分段原则如下：

1）先取第一个符号作为第一段，然后再继续分段。

2）若出现与前面相同符号时，就再添加紧跟后面的一个符号一起组成一个段，以使与前面的段不同。

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

将不同的段看成短语，可得所对应的短语字典表。若编成二元码，段号用二进制数表示，则段号所需码长为

l=log m

其中，m是段号数。LZ-78的编码原则如下：

1）对字符段X编码，若字符段X仅由某一个信源符号组成，则它必为新出现的段，字典内不会有和它匹配的段，此时指针k=0，表示是首次出现，字典内没有与之匹配的段，故将其编码为（0，x），其中，x为字符段X中这个待编码信源符号的编码的码字。用二进制表示时，。

2）若字符段X至少由两个或两个以上信源符号组成时，记X=x₁x₂…x_rx₀（x_i∈A），则编码器首先在字典表内搜索与X的去掉最后一个符号x₀后的符号串x₁x₂…x_r相匹配的短语的位置顺序号，其值就是指针k，然后将最后一个信源符号x₀的编码码字x₀作为标识的第二项x的值，即得X的码字（k，x）。(www.xing528.com)

下面仍用举例说明LZ-78编码的编码算法。

【例4.24】

信源符号集A：{a，b，c，d}，信源序列为aacdbbaaadcacbaaadccacbbbaadcbacba，对其进行LZ-78编码。

解 将信源符号a、b、c、d编码，其二元码字为a→00，b→01，c→10，d→11。

其LZ-78编码的过程见表4.17。按编码原则，第1段X=a，由一个信源符号组成，必为首次出现，字典表内无匹配串，编码为（0，a），并将a存入字典表中；第2段X=ac，由两个信源符号组成，去掉最后一个符号c，仅余a，字典表内刚存入的第1项恰与a匹配，故指针k=1，则ac编码为（1，c）。按编码原则，可以逐步给其余段编码，并在给每一新的段编码后，将其存入字典表内。

表4.17 例4.24的LZ-78编码过程

此例共分14段，段号需用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）

可见，LZ-78编码方法简单、快捷，码符号序列的译码也很直接，一边译码一边又建成字典表，所以字典表无须传输，能无误地恢复成原信源符号序列。这会使LZ-78的译码器比LZ-77的译码器复杂。LZ-77只使用有限字节的存储器作为一个动态字典使用，而LZ-78算法要把已编码的段全部存储，再作为字典使用，这使字典太大，搜索时间也会太长。因此现在的LZ-78码中，字典的数据结构采用多进制树结构：以空串作树根，以单字符的段作为根的子节点，再将其他段的字符添加成二阶子节点，……这样简化了字典的管理及加快搜索。

要注意的是，LZ-78算法不一定比LZ-77算法好，两者各有所长。因此在1989年以后，又有综合两者优点的LZFG码出现，它有A1、A2、B1、B2、C1和C2等多种变形码，分别在搜索速度和压缩率大小上各有所长。后来又有追求压缩速度的LZRW1码，它比UNIX的压缩算法LZC（即下小节介绍的LZW算法的变形）的压缩效果差约为10%，但压缩速度快了4倍，适用于需要快速压缩的实时传播的领域。