基于字符串匹配的通用数据压缩算法

AN EFFICIENT UNIVERSAL DATA COMPRESSION ALGORITHM BASED ON STRING MATCHING

本文主要介绍基于字符串匹配的数据压缩算法原理，该算法从多方面对著名的ＬＺ７７算法进行了改进。我们的算法所用到的工作缓冲区是一个循环历史表，摈弃了输入符号超前缓冲区；结果，匹配过程是边接收输入边进行，无需等待一组输入数据填满超前缓冲区才开始，同时，最大匹配长度不再受超前缓冲区大小的限制，而且，不再需要做大量的平移工作缓冲区的操作．另外，还涉及一些其他方面的改进，包括改等长压缩码为变长码和引入匹配位置滑动表技术等。

This paper discusses a univerasl adta compression algorithm based on string matching that can be used to compress various types of data fficiently. Although the main principle is the same as the famous algorithm, LZ77, some important improvements have been taken and the chief drawbacks of LZ77 have been successfully avoided. For example,our algorithm adopts a circular historf list ,lcaving the look-ahead bcffer of LZ77 discarded. As a result, the lengt of matched string can go beyond the size limit of look - ahead buffer, and furthermore, before looking for longest metching,our algorithm does not have to wait for the ac, ceptance Of enough input to fill up the look-ahead buffer but just makes the length of matched string longer with the arrival of more data,that is,even a single input symbol can start the matching process. The other improvements are also discussed.