改进的LZ77数据压缩算法

每天都有大量的信息，而这些信息以诸如图像、声音和文本的形式来传递。其中图像和声音的数据量特别地大，需要高效的压缩方法。LZ77算法是有效的压缩算法之一。本文针对LZ77算法提出两种新的算法，来提高压缩算法的性能。算法一在查找匹配前先检验是否可能得到最长匹配，而算法二则是保存链表中相邻字符串的最长公共前缀来提高效率。与其他版本的LZ系列压缩算法进行对比分析后发现，改进后的这个新方案达到预期效果。

现今越来越多的研究者意识到数据压缩的重要性，这主要是因为当今如此大量的数据不仅占据了大量的存储空间，而且占据了大量的传输带宽，使得计算机的数据处理和通信干线信道的带宽都受到了极大的压力。因此，无论从存储角度还是从传输角度，对数据压缩进行研究都有着相当重大的意义。目前有许多较成熟的数据压缩技术， 而LZ77 算法是有效的压缩算法之一。

LZ77 算法是由Jacob Ziv 和Abraham Lempel [1]在1977 年给出的，其设计思想是采用字典查找方法，它是用滑动窗口来构作字典的。

后来， Jacob Ziv 和Abraham Lempel 两人在1978 年提出了另一种LZ 算法[2]， 这种算法被称为LZ78算法。LZ78 取消了LZ77 算法的滑动窗口，从字符流中不断提取新的缀–符串保存到字典中，并在压缩过程中把字符串替换成相应的缀–符串。

1982 年James Storer 和Thomas Szymanski [3]对LZ77 算法进行了改进，后来这个算法被称为LZSS算法。LZSS 算法通过二叉树匹配查找代替LZ77 算法的顺序匹配查找，并通过一个额外的ID 位来区分输出的是指针还是真实字符。在相同的条件下LZSS 算法大大地提高了压缩的时间效率，同时可获得更小的压缩率。

1984 年，Welch 研究出一种高性能数据压缩技术，这是LZ78 算法的一个变种，也就是后来非常有名的LZW 算法[4]。LZW 算法的实现比较简单，同时它改善了LZ78 算法的自适应性，字典一开始保存256 个索引，每一条索引对应一个字符，在压缩时生成新的索引保存到字典中，并输出索引代替相应的字符串。

1991 年Ross Williams 提出的LZRW 算法[5]是LZ77 算法的另一改进，它的主要思想是通过构建散列表来提高算法的效率。使用散列表来进行匹配的压缩速度是极快的，把每一个字符串的开头若干个字节作为散列表的关键码值，通过散列函数找到开头若干个字节与之匹配的字符串的位置，之后再做顺序的匹配。另外，LZRW 算法没有改进LZ77 算法的压缩比。

以上介绍的算法统称LZ 系列算法，这些算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的WinZIP、Gzip 等压缩工具都采用了LZ 算法来进行压缩。其它有关LZ 算法的研究可以参考文献[6]-[8]。

本文主要研究如何提高LZ77 算法的时间效率， 提出了两种新的LZHJ 算法。

这两种新算法都是通过链表法实现的散列表来进行匹配查找，其中LZHJ 算法一在查找匹配前先检验是否可能得到最长匹配， 而LZHJ 算法二则是保存链表中相邻字符串的最长公共前缀来提高效率。通过实验对比新的算法达到预