关于Lempel－Ziv　77压缩算法及其实现的研究  

RESEARCH ON LEMPEL-ZIV 77 ALGORITHM AND ITS IMPLEMENTATION

作　　者：王忠效[1] 姜丹[1] 

机构地区：[1]中国科学技术大学管理学院,中国科学院管理干部学院

出　　处：《计算机研究与发展》1996年第5期329-340,共12页Journal of Computer Research and Development

摘　　要：本文在研究著名的ＬＺ７７压缩算法的基础上，讨论了对这一算法的种种改进。新的算法同样适用于任何类型的数据文件，而且无论是压缩速度还是压缩效率均好于ＬＺ７７算法。我们的算法所用到的工作缓冲区是一个循环缓冲区，不再包括一个输入符号超前缓冲区；结果，匹配过程是边接收输入边进行，无需等待一组输入数据填满超前缓冲区才开始，同时，最大匹配长度也不再受超前缓冲区大小的限制，而且，避免了大量的平移工作缓冲区的操作。另外，还涉及一些其他方面的改进，主要包括改等长压缩码为变长码和引入匹配位置滑动表技术等。本文详细讨论了各种改进及其对算法性能的影响。Based on the analysis of LZ77 algorithm, this paper discusses its major improvements. A new algorithm adopts a circular history list, leaving the look-aheadbuffer of LZ77 discarded. That makes it possible to let a matched string be as long asthe size of the history list and results in the reduction of code length. Another main improvement is that the new algorithm takes variable-length code instead of LZ77's fixedlength one. Besides, a new data structure called matching position list is introduced,which contributes much to the high efficiency of the encoder. How and why the improvements affect the algorithm's performance are shown in detail.

关 键 词：数据压缩 LZ77压缩算法 计算机 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]