枝上又闻啼

由于下午有体育课，导致晚上的信息论基础课每次都是昏昏欲睡，今天跑去还是先用了半节课来休养生息，然后开始写上次的作业。

突然看到一个LZ编码的题目让我困惑了好久，书上不到一页的文字，我硬是反反复复看了好几遍，还是没有明白。终于在下课后得到了很好的解释。

在这里首先要感谢凯哥同学，居然能通过书上为数不多的几段文字正确得出LZ编码（之后我们戏称楼主编码）的具体过程。因为在此之前关于字段这个细节问题老师说错了。

一下文字来自百度百科，由馅饼同学花了一晚上了时间与2009年11月9日晚完成。

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 编码字典

表2 符号编码表

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

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