SEA  >> Vol. 3 No. 3 (June 2014)

    改进的LZ77数据压缩算法
    Modified Algorithms of the LZ77 Data Compression

  • 全文下载: PDF(479KB) HTML    PP.50-56   DOI: 10.12677/SEA.2014.33007  
  • 下载量: 2,121  浏览量: 5,700   国家自然科学基金支持

作者:  

黄健骏,姜正禄:中山大学,广州

关键词:
无损压缩字典编码LZ77压缩算法散列表Lossless Compression Codeword Encoding LZ77 Compression Algorithm Hash Table

摘要:

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

Every day much information is transmitted in such forms as images, sounds and texts. These data of images and sounds are particularly large and need an efficient compression method. The LZ77 algorithm is one of the most effective compression algorithms. In this paper, two new algorithms are given in order to improve the performance of the original LZ77 algorithm. One is to check whether it can get the longest match before matching, and the other is to save the longest common prefix of the adjacent strings in the list to improve the efficiency. It is proved that the two new algorithms achieve the expectation after a comparative analysis with other versions of the LZ compression algorithms.

文章引用:
黄健骏, 姜正禄. 改进的LZ77数据压缩算法[J]. 软件工程与应用, 2014, 3(3): 50-56. http://dx.doi.org/10.12677/SEA.2014.33007

参考文献

[1] Ziv, J. and Lempel, A. (1977) A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, 23, 337-343.
[2] Ziv, J. and Lempel, A. (1978) Compression of Individual Sequences via Variable-Rate Coding. IEEE Transactions on Information Theory, 24, 530-536.
[3] Storer, J. and Szymanski, T. (1982) Data compression via textual substitution. Journal of the Association for Computing Machinery, 11, 928-951.
[4] Welch, T.A. (1984) A Technique for High-Performance Data Compression. Computer, 6, 8-19.
[5] Williams, R.N. (1991) An extremely fast Ziv-Lempel data compression algorithm. Data Compression Conference 1991 (DCC’91), 8-11 April 1991, Snowbird, 362-371.
[6] Bender, P.E. (1991) New asymptotic bounds and improvements on the Lempel-Ziv data compression algorithm. IEEE Transactions on Information Theory, 5, 721-729.
[7] Ziv, J. and Wyner, A.D. (1994) The sliding-window Lempel-Ziv algorithm is asymptotically optimal. Proceedings of the IEEE, 6, 872-877.
[8] Kosaraju, R.S. and Manzini, G. (1997) Some entropic bounds for Lempel-Ziv algorithms. Proceedings of DCC, 3, 446.