LZ算法：词典编码的革命性创新

LZ算法-词典编码课件 LZ算法是一种高效的压缩技术，它的提出标志着数据压缩领域的重大突破。 Jacob Ziv 和 Abraham Lempel 两人在1977年和1978年分别发表了两篇论文《顺序数据压缩的一个通用算法》和《通过可变比率编码的独立序列的压缩》，提出了LZ77和LZ78两种压缩技术。这些技术的提出，标志着字典式编码的诞生，并且这种编码方法的压缩效果和速度都大大超过了哈夫曼编码。 字典式编码的思路是基于对信息中单个字符出现频率的统计，但是这种思路在数据压缩领域一直占据着统治地位。直到70年代末期，这种情形在某种程度上显得有些可笑，但是事情就是这样，一旦某项技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来。 LZ算法的提出，打破了Huffman编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今，几乎我们日常使用的所有通用压缩工具，象WinZip，RAR……甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。 词典编码的思路相当简单，我们日常生活中就经常在使用这种压缩思想。我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。 我们之所以可以顺利使用这种压缩方式而不产生语义上的误解，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正是基于这一思路设计实现的。 最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章进行压缩，我们手中已经有一本《现代汉语词典》。那么，我们扫描要压缩的文章，并对其中的句子进行分词操作，对每一个独立的词语，我们在《现代汉语词典》查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有找到，我们就输出一个新词。这就是静态字典模型的基本算法了。 在实际应用中，LZ算法有很多种变形和改进，例如LZW算法、LZSS算法等，但是它们的基本思路都是基于字典式编码的。LZ算法的出现，不仅改变了数据压缩领域的发展方向，也为我们提供了高效的压缩工具和算法。