摘要
本文在研究著名的ＬＺ７７压缩算法的基础上，讨论了对这一算法的种种改进。新的算法同样适用于任何类型的数据文件，而且无论是压缩速度还是压缩效率均好于ＬＺ７７算法。我们的算法所用到的工作缓冲区是一个循环缓冲区，不再包括一个输入符号超前缓冲区；结果，匹配过程是边接收输入边进行，无需等待一组输入数据填满超前缓冲区才开始，同时，最大匹配长度也不再受超前缓冲区大小的限制，而且，避免了大量的平移工作缓冲区的操作。另外，还涉及一些其他方面的改进，主要包括改等长压缩码为变长码和引入匹配位置滑动表技术等。本文详细讨论了各种改进及其对算法性能的影响。
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1996年第5期329-340,共12页
Journal of Computer Research and Development
关键词
数据压缩
LZ77压缩算法
计算机
算法
Data compression, LZ77 algorithm, LZ78 algorithm, circular buffer,matching position list.
