基于后缀数组的滑动窗口匹配压缩改进算法研究

《基于后缀数组的滑动窗口匹配压缩改进算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学号M200972498学校代码10487密级硕士学位论文基于后缀数组的滑动窗口匹配压缩改进算法研究学位申请人：王坚学科专业：计算机应用技术指导教师：路松峰副教授答辩日期：2012年1月15AThesisSubmittedinFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringTheImprovingAlgorithmofSlidingWindowBaseonSuffixArrayCandidate:JianWangMajor:ComputerApplicationTechnol

2、ogySupervisor:AssociateProf.LuSongfengHuazhongUniversityofScienceandTechnologyWuhan,Hubei430074,P.R.ChinaJAN,2012独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授

3、权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在_____年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打―√‖）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学硕士学位论文摘要LZ77算法，又被称为―滑动窗口压缩‖，它依赖两个滑动窗口来进行压缩，一个窗口包含已输入数据流，称为字典窗口D

4、W(dictionarywindow)；另一个窗口包含待压缩编码的字符串，即待编码窗口CW(codewindow)。LZ77通过查找在DW中与CW相同的字符数据并将匹配成功的数据编码成三元组写入压缩文件，从而实现数据压缩功能。后缀数组(SuffixArray，简称SA)作为一种常用的文本索引机制，由于其结构简单及空间效率较好的特点，现已经结合到LZ算法中。但这种结合方法，每次都需重建SA，时间复杂度较高，效率不高。首先分析字符串匹配等算法并进行对比，在对已提出各种LZ77改进算法的研究分析的基础上，进一步对后缀数组与最长公共前缀((LongestComm

5、onPrefix,简称LCP)等相关理论进行研究分析，阐述三种后缀数组的构建算法并对比。然后分析现有结合算法的思想及其不足，通过对SA的特点分析，提出完全后缀这一新术语，利用LCP数组把SA分为完全后缀(CompleteSuffixArray，简称CSA)和非完全后缀(UncompletedSuffixArray，简称UCSA)，由于窗口滑动后UCSA保持了原有的偏序关系，且占SA比例高，采用二分插入法把CSA插入到UCSA中构建新的SA，可以更高效地重建SA。从而在保证压缩效率不降低的同时，提高整个算法的压缩效率。最后通过实验，对多种不同大小的文件进行

6、测试，对比现有结合算法和改进算法的效率，表明改进算法的实践优越性。同时实验中的最长公共字符串平均长度和完全后缀数组的平均大小，也表明了改进算法的优越性。关键词：伦佩尔-谢夫压缩算法，滑动窗口，后缀数组，最长匹配公共前缀I华中科技大学硕士学位论文ABSTRACTTheLZ77,called―compressionviaslidingwindows‖,itcompressesdatabytwoslidingwindows.Theoneisnamedasdictionarywindow,whichcontainstheinputdataalready;theo

7、theroneisnamedascodewindow,whichcontainsthestringwillbecompressedandcoded.ThroughtosearchthestringofCWappearedinDWandcompressandcodethecorrespondingcurrentdata,LZ77executescompression.Asacommontext-indexmechanism,suffixarray(SA)hasbeencombinedintoLZ77duetoitssimplicityandlowermem

8、oryrequired.Buttheircombinationisinadequ