LZ编码

1965年苏联数学家Kolmogolov提出利用信源序列的结构特性来编码。而两位以色列研究者J.Ziv和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。

Ziv和Lempel于1977年提出了LZ77算法[Ziv & Lempel (1977)]。1984年，二人又提出了改进算法，后被命名为LZ78[Ziv & Lempel (1978)]。1984年，T.A.Welch提出了LZ78算法的一个变种，即LZW算法[ Welch (1984)]。1990年后，T.C.Bell等人又陆续提出了许多LZ系列算法的变体或改进版本[ Bell 等(1990)]。

LZ系列算法用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。

以LZ78算法为例。

设信源符号集A={a1，a2，…，aK}共K个符号，设输入信源符号序列为u=(u1，u2，…，uL)编码是将此序列分成不同的段。分段的规范为：尽可能取最少个相连的信源符号，并保证各段都不相同。

开始时，先取一个符号作为第一段，然后继续分段。若出现与前面相同的符号时，就再取紧跟后面的一个符号一起组成一个段，使之与前面的段不同。这些分段构成字典。当字典达到一定大小后，再分段时就应查看有否与字典中的短语相同，若有重复就添加符号，以便与字典中短语不同，直至信源序列结束。

编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M（u）个。若编码为二元码，段号所需码长n=「log M（u）「（注：代表上取整符号），每个符号需要的码长为「log K「。单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相同短语的段号。

例如，设U={a1，a2，a3，a4}，信源序列为a1，a3，a2，a3，a2，a4，a3，a2，a1，a4，a3，a2，a1，共13位，字典如表所示：

表1编码字典

段号

短语

编码

1

a1

00000

2

a3

00010

3

a2

00001

4

a3a2

01001

5

a4

00011

6

a3a2a1

10000

7

a4a3

10110

8

a2a1

01100

表2符号编码表

a1

a2

a3

a4

00

01

10

11

表1中，8个短语使用3bit可以表示段号。每个信源符号使用2bit表示，因此，一个短语使用5bit。

LZ编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，只要传输字典的大小，无需传输字典本身。当编码的信源序列增长时，编码效率会提高，平均码长会逼近信源熵。