学位论文 > 优秀研究生学位论文题录展示

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

作　者: 魏星
导　师: 吴伟民
学　校: 广东工业大学
专　业: 计算机应用技术
关键词: 无损数据压缩 LZSS算法 多模式匹配 WM多模式匹配 预处理
分类号: TP391.1
类　型: 硕士论文
年　份: 2011年
下　载: 44次
引　用: 1次
阅　读: 论文下载
 

内容摘要


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

全文目录


摘要  4-5
ABSTRACT  5-12
第一章 绪论  12-18
  1.1 数据压缩技术  12-15
  1.2 课题的定位  15
  1.3 完成的主要工作  15-16
  1.4 论文的组织  16-18
第二章 数据压缩算法  18-35
  2.1 数据压缩理论  19-21
    2.1.1 信息和熵  19-20
    2.1.2 冗余度  20-21
    2.1.3 压缩性能评价  21
  2.2 无损数据压缩  21-30
    2.2.1 Huffman算法  22
    2.2.2 LZ77系列算法  22-27
    2.2.3 LZ78系列算法  27-30
  2.3 压缩算法的选择  30-33
    2.3.1 Huffman算法与LZ系列算法的比较  30-31
    2.3.2 LZ78系列算法的比较  31
    2.3.3 LZ77系列算法的比较  31-32
    2.3.4 LZ78系列与LZ77系列算法的比较  32-33
  2.4 LZ编码压缩性能的理论分析  33-34
  2.5 本章小结  34-35
第三章 基于多模式匹配的压缩算法设计  35-47
  3.1 LZSS算法的优缺点  35-36
  3.2 多模式匹配算法  36-38
    3.2.1 模式匹配  36
    3.2.2 WM多模式匹配算法  36-38
  3.3 WM_LZSS算法  38-45
    3.3.1 实现难点及关键技术  39-44
    3.3.2 算法的具体步骤  44-45
  3.4 算法的进一步优化  45-46
  3.5 本章小结  46-47
第四章 基于多模式匹配的压缩算法的实现及测试  47-65
  4.1 算法类的设计  47
  4.2 适用范围  47
  4.3 测试结果及分析  47-62
    4.3.1 文件类型测试  48-52
    4.3.2 文件长度测试  52-54
    4.3.3 模式库中最小模式的大小测试  54-55
    4.3.4 相关压缩算法比较测试  55-61
    4.3.5 测试结果总结  61-62
  4.4 软件使用说明  62-64
    4.4.1 运行界面  62-63
    4.4.2 文件的打开和保存  63-64
    4.4.3 结果信息显示  64
  4.5 本章小结  64-65
结论  65-66
参考文献  66-70
攻读学位期间发表的论文  70-72
致谢  72

相似论文

  1. 舌图像中瘀斑瘀点检测技术研究,TP391.41
  2. Cu2+/Co2+催化漂白桉木浆工艺与机理研究,TS745
  3. 离子液体预处理纤维素及再生纤维素水解研究,TQ352.1
  4. 玉米秸秆和牛粪混合厌氧发酵工艺优化研究,S216.4
  5. 红外图像目标识别及跟踪技术研究,TP391.41
  6. 基于粗糙集的城市区域交通绿时控制系统研究,TP18
  7. 化学与生物成因施氏矿物的矿物学特征及其对水中As（Ⅲ）吸附去除效果的研究,X703
  8. O3高级氧化技术处理黄连素制药废水研究,X787
  9. 缺氧预处理MSCs移植对心肌梗死区SDF-1/CXCR4轴表达变化的实验研究,R542.22
  10. 内质网应激预处理提高肾组织对缺血再灌注损伤耐受性的作用及机制,R692.5
  11. 丁苯酞预处理对大鼠脑缺血再灌注损伤的神经保护作用,R743.33
  12. 经H2O2预处理的骨髓间充质干细胞移植对急性心梗后心室重构影响的实验研究,R542.22
  13. 基于车牌识别技术的智能交通系统的设计与实现,TP391.41
  14. 基于小波分析的掌纹图像识别研究,TP391.41
  15. 基于高斯过程的在线建模问题研究,TP181
  16. 五效蒸发法预处理环氧丙烷废水研究,X78
  17. 基于投影寻踪回归的网络异常检测机制研究,TP393.08
  18. 基于web的通信原理教学信息管理与评估系统的设计与实现,TP311.52
  19. 基于数字图像处理的手势识别,TP391.41
  20. 基于数据挖掘聚类技术的我国高校分类研究,TP311.13
  21. 基于SVM的车牌字符识别算法研究与实现,TP391.41

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理（信息加工） > 文字信息处理
© 2012 www.xueweilunwen.com