论文部分内容阅读
近年来,日常需要处理和传输的数据越来越多,数据压缩也变得越来越重要,而其中文本是数据的一个重要组成部分,因此对文本数据的压缩研究就成为了压缩领域研究的一个重点。基于字典的压缩算法是文本压缩的一种典型的算法,对其展开研究对文本数据的压缩有着十分重要的意义。本文在对基于字典的压缩算法分析的基础上,选择LZSS算法展开了研究,主要工作如下:首先,为了提高文件的压缩率,对文本文件的无损压缩进行了研究,回顾了经典的无损压缩算法,并阐述了主要压缩方法的原理和特点。实现了三种基于字典的经典压缩算法并在此基础上进行了分析。LZSS算法是LZ77算法的改进,压缩率虽然不高,但因其算法简单、解压速度快,在实际应用中得到了广泛的认可。因此选择了LZSS算法进行研究,目的是在保持高解压速度的基础上进一步提高其压缩率。其次,在LZSS的基础上,本文进一步利用目前流行的多模式匹配算法——Wu-Manber算法,改进了字符串匹配的过程,提出了一种新的算法——WM_LZS S算法。算法的基本思想是利用文本的最近相关性,针对LZSS算法在压缩过程中存在查找回溯的问题,采用多级匹配、Hash散列和跳跃查找的思想,使用多模式匹配技术在更大范围内进行查找。一次针对多个模式进行匹配,避免了不必要的匹配,加速了匹配的过程,有利于查找到更长的匹配信息,获得更高的压缩率。本文详细介绍了基于多模式匹配的压缩算法的核心过程。即利用每一次匹配的结果,动态建立shift表和hash表,得到模式库。然后,从文件中读取固定大小的数据块,进行多模式匹配预处理,针对模式库中的所有的模式进行查找,得到匹配数据(其中包括匹配位置和匹配长度等)。利用得到的匹配数据输出编码并完善树结构。最后,选取了通用的文本压缩测试文件作为测试数据,从文件的类型、文件的大小、最小模式大小的选择等方面对压缩率进行了充分的测试,并与相关的压缩算法进行了横向比较。实验证明,改进后算法的压缩率有了较明显的提高,同时该算法还具有解压快速、算法简单的特点,特别适合在一次压缩多次解压的情况下使用。