张永棠

（广东东软学院计算机科学与技术系，广东佛山528225）



一种改进的LZ77无损数据压缩算法设计

张永棠

（广东东软学院计算机科学与技术系，广东佛山528225）

摘要：研究了LZ77无损数据压缩算法的原理，在对LZ77各种改进算法进行深入分析的基础上，结合TUNEDBM单模式匹配算法，提出了一种新的改进的LZ77无损数据压缩算法。实验结果表明，改进的LZ77压缩率比原LZ77稍有降低，但在压缩时间有很明显的优势，尤其当文件较小时，这种优势体现得更加明显。

关键词：通信编码；无损压缩；LZ77；算法设计；TUNEDBM

随着大数据和云计算的应用，给互联网数据的存储和传输带来了更大的挑战。应用数据压缩技术解决这一难题是重要手段。为了达到最好的压缩效果，无损压缩法（也叫熵编码）是一种最常用的压缩编码方法。目前无损压缩主要有两大分支，一种是基于字符概率统计的，如Huffma等；一种是基于字典的，如LZ系列［1］。

现在的字典压缩算法大都可以追溯到由ZIV和LEMPEL［1-2］提出的LZ77和LZ78算法。日常使用的通用压缩工具有WinZip，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR等，此外，许多网络设备中内置的压缩程序都可以归结为这些算法及其变种。虽然现有的LZ78其压缩思想有较大变化，它采用了保存先前所遇到的字符串的字典方法来取代传统的滑动窗口。由于字典中的表项很少，弥补初期的低效，逐渐显出自己的优势。但是LZ78算法实现起来较为复杂，而且需要额外的内存开销，这对资源有限且处理能力不足的平台数据压缩并不适合，比如单片机。对LZ77进行改进，可使其能实现嵌入式平台的数据压缩。……