多模型下的近似字符串匹配算法研究

《多模型下的近似字符串匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、D200877550分类号__________学号______________学校代码__________10487密级______________博士学位论文多模型下的近似字符串匹配算法研究学位申请人：赵华学科专业：计算机应用技术指导教师：卢正鼎教授路松峰副教授答辩日期：2013年1月22日ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinEngineeringApproximateStringMatchingUnderDifferentMod

2、elsPh.D.Candidate:ZHAOHuaMajor:ComputerApplicationTechnologySupervisor:Prof.LUZhengding,AssociateProf.LUSongfengHuazhongUniversityofScienceandTechnologyWuhan,Hubei430074,P.R.ChinaJanuary,2013独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的

3、个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本论文属于不保密□。（请在以上方框内打―√‖）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学博士学位论文摘要近似字符串匹配是模

4、式匹配研究领域中的一个重要问题。近年来，随着各学科的迅速发展，在许多不同背景下对于近似串匹配问题的研究逐渐受到人们的关注。特别是在计算生物学等新兴学科中，有许多近似串匹配的新模型被陆续提出。一方面，这些模型在各学科中均有非常重要的应用；另一方面，由于这些模型被提出的时间大多不长，因此对它们的研究并不充分。因此，对不同模型下的近似串匹配问题进行研究就成为了在模式匹配和诸多相关领域中的研究重点和难点。针对这一现状，研究的主要内容就是三种近年被提出的模型下的近似串匹配问题。这三种模型分别是：属性匹配模型，交换匹配模型以及块匹配模型。针对属性匹配，提出了一种新的索引结构CIDS-PIP（

5、compressedindexeddatastructureforpropertyindexingproblem）及相应的匹配算法。在该算法中采用了压缩后缀数组作为核心的索引结构。为了进一步降低索引的空间开销，针对不同的属性规模，提出了两种解决方案。针对这两种方案设计了不同的辅助索引结构，以同时满足较高的查询效率和较低的空间开销。与现有的支持属性匹配的索引相比，CIDS-PIP的空间开销更低。针对交换匹配，提出了一种新的离线匹配算法，并证明了更精确的模式交换版本的个数上限。该交换匹配离线算法是建立在已有的全文索引的基础上，而非设计全新的索引数据结构。在该算法中，采用后缀数组或压缩

6、后缀数组作为索引结构。当模式长度较小时，该算法可以达到良好的时间效率，并明显优于现有的属性匹配在线算法。此外，还解决了近似交换匹配问题。实验证明，相对于已有的在线交换匹配算法，该算法的时间效率大幅提高。块模式匹配模型是JulioN.等人在2011年提出的一种匹配模型，现在在此基础上进行的研究并不多见。针对在线和离线两种情况下的块模式匹配问题进行了研究，并且分别给出了新的算法。相对于现有的在线匹配算法，新的在线算法需要更低的空间开销，而时间开销并没有增加。相对于现有的离线匹配算法，新的离线算法的I华中科技大学博士学位论文时间效率更高。与此同时，还指出了在Julio等人论文中的一处不

7、正确的表述，并对其算法的时间复杂度进行了修正。此外，对块模式匹配问题的两个衍生问题：融合块模式匹配问题和突变块模式匹配问题进行了研究并提出了新的算法。关键词：模式匹配，近似串匹配，属性匹配，交换匹配，块模式匹配，压缩后缀数组II华中科技大学博士学位论文AbstractApproximatestringmatchingisanimportantissueintheresearchareasofpatternmatching.Withtherapiddevelopmentofvari