基于多模式匹配的数据压缩算法研究

来源 :广东工业大学 | 被引量 : 3次 | 上传用户:neo1997
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,日常需要处理和传输的数据越来越多,数据压缩也变得越来越重要,而其中文本是数据的一个重要组成部分,因此对文本数据的压缩研究就成为了压缩领域研究的一个重点。基于字典的压缩算法是文本压缩的一种典型的算法,对其展开研究对文本数据的压缩有着十分重要的意义。本文在对基于字典的压缩算法分析的基础上,选择LZSS算法展开了研究,主要工作如下:首先,为了提高文件的压缩率,对文本文件的无损压缩进行了研究,回顾了经典的无损压缩算法,并阐述了主要压缩方法的原理和特点。实现了三种基于字典的经典压缩算法并在此基础上进行了分析。LZSS算法是LZ77算法的改进,压缩率虽然不高,但因其算法简单、解压速度快,在实际应用中得到了广泛的认可。因此选择了LZSS算法进行研究,目的是在保持高解压速度的基础上进一步提高其压缩率。其次,在LZSS的基础上,本文进一步利用目前流行的多模式匹配算法——Wu-Manber算法,改进了字符串匹配的过程,提出了一种新的算法——WM_LZS S算法。算法的基本思想是利用文本的最近相关性,针对LZSS算法在压缩过程中存在查找回溯的问题,采用多级匹配、Hash散列和跳跃查找的思想,使用多模式匹配技术在更大范围内进行查找。一次针对多个模式进行匹配,避免了不必要的匹配,加速了匹配的过程,有利于查找到更长的匹配信息,获得更高的压缩率。本文详细介绍了基于多模式匹配的压缩算法的核心过程。即利用每一次匹配的结果,动态建立shift表和hash表,得到模式库。然后,从文件中读取固定大小的数据块,进行多模式匹配预处理,针对模式库中的所有的模式进行查找,得到匹配数据(其中包括匹配位置和匹配长度等)。利用得到的匹配数据输出编码并完善树结构。最后,选取了通用的文本压缩测试文件作为测试数据,从文件的类型、文件的大小、最小模式大小的选择等方面对压缩率进行了充分的测试,并与相关的压缩算法进行了横向比较。实验证明,改进后算法的压缩率有了较明显的提高,同时该算法还具有解压快速、算法简单的特点,特别适合在一次压缩多次解压的情况下使用。
其他文献
随着计算机网络技术的发展,互联网逐渐呈现出一种高带宽、高延迟的特性。传统的TCP拥塞控制算法已经不能适应现有的网络,带宽利用率低下。因此,设计出一个适应高带宽延迟网络
在非结构化P2P网络中,节点由于受到内部能力差异、搭便车行为和高扰动(High Churn)特性的影响,负载度呈现出严重的失衡,对网络的健壮性和可用性形成了严重的影响,同时也造成
无论在虚拟的大型3D游戏、影视作品中,还是在海洋勘探等领域,大规模海洋仿真有着非常重要的应用。目前的海洋仿真研究中大多聚焦在海面建模层面,或者只实现某一个海洋光学表
不平衡数据在实际应用中广泛存在,如何从不平衡数据中学习并获得分类器成为了当前机器学习研究领域的一个热点。该方面的研究已经取得了一定的成果,并在入侵检测、信用卡交易
按需式距离矢量路由协议AODV是一种经典的按需路由协议,已经得到了广泛的应用。在AODV的实现中,网络节点根据首次接收到的RREQ报文建立反向路由及前向路由,对于重复接收的RRE
随着“互联网+”时代的到来,移动互联网迎来了新的发展时机,智能手机作为移动互联网的主要入口之一发展迅速,其设备性能与普及度都有很大的提升。Android系统作为最受欢迎的
无线传感器网络是由大量具有感知、数据收集、数据处理和无线通信能力的小体积、低成本的传感器节点构成的无线自组织网络,能够对大范围区域进行有效监测,并对监测数据进行处
随着软件行业的繁荣发展,软件系统的规模和复杂度急剧增长,对软件进行优化和维护越来越困难。软件缺陷预测通过分析软件特征,利用机器学习技术构建预测模型,在软件测试前定位
老的影视资料由于胶片老化、脱落以及反复播放、转存、复制的过程中受到刮伤等原因,播放时在画面中出现了如斑点、闪烁、划痕、抖动、褪色等问题。另外,当前节目制作过程中由
带约束路由算法问题一直是通信领域的热点问题。然而,多数特殊约束路由问题为NP-完全问题,除非NP=P,否则无法给出多项式时间算法。对于这些问题,已经出现各种伪多项式算法,但这些