正则表达式匹配算法研究

《正则表达式匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTER‟SDISSERTATION论文题目正则表达式匹配算法研究作者姓名陈航宇学科专业软件工程指导教师王璿副教授2016年05月中图分类号：TP312学校代码：10216UDC：621.3密级：公开工学硕士学位论文正则表达式匹配算法研究硕士研究生：陈航宇导师：王璿副教授申请学位：工学硕士学科专业：软件工程所在单位：信息科学与工程学院答辩日期：2016年5月授予学位单位：燕山大学ADissertationinSoftwareEngineeringRESEARCHONREGULAREXPRESSIONMATCHINGALGORITHMByC

2、henHangyuSupervisor:ProfessorWangXuanYanshanUniversityMay,2016燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《正则表达式匹配算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字：日期：年月日燕山大学硕士学位论文使用授权书《正则表达式匹配算法研究》系本人在燕山大学攻读硕士学位

3、期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分内容。保密□，在年解密后适用本授权书。本学位论文属于不保密□。(请在以上相应方框内打“√”)作者签名：日期：年月日导师签名：日期：年月日摘要摘要正则表达式匹配是从文本中找出与给定正则表达式匹配的所有字符序列的起始和结束位置，该操作在文本编辑、

4、生物信息学、模式识别等领域有着重要的应用。通过分析发现现存方法需要对文本建立后缀树索引，而本文后缀树索引空间大，建树过程复杂且查找正则表达式的前缀、后缀位置信息时需要遍历整个后缀树效率较低。为了提高匹配效率，本文从以下几个方面对正则表达式匹配问题进行了深入研究：首先，提出了基于数组索引的访问策略，该策略先查询正则表达式中一定出现的字符序列的位置，然后根据这些位置进行对正则表达式左右匹配，最后找出能够与此正则表达式匹配的所有位置，从而避免遍历整个后缀树，并提出了基于上述策略的正则表达式匹配算法-Match算法。其次，针对在正则表达式的匹配阶段存在的冗余计算

5、问题，提出了新的匹配方法，即依照出现次数最少的字符序列位置进行左右匹配；根据左右匹配的不同限制以及以前方法的过滤思想提出了两种过滤策略，即左右匹配的过滤策略和基于消极因子的过滤策略，进一步减少了候选结果和验证时间，从而提高算法的执行效率。最后，在不同特征数据集上，通过比较同一正则表达式的匹配时间，将Match算法与当前最好的正则表达式匹配算法进行比较，实验结果验证了本文所提算法的高效性。关键词：正则表达式；后缀树；Match算法；过滤策略I燕山大学工学硕士学位论文AbstractRegularexpressionmatchingistofindthest

6、artingpositionandtheendingpositionofthecharactersequencematchingthegivenregularexpressionfromthetext,theoperationhasimportantapplicationsintextediting,bioinformatics,patternrecognition,etc.Throughanalyzingtheexistingmethods,theresultsfindthattheexistingmethodsneedtobuildasuffixtr

7、eeindex.Andthesuffixtreeindexspaceisbig,establishingprocessiscomplexandlocatingtheinformationofregularexpressionprefixandsuffixneedstotraversetheentiresuffixtree，whichhaslowefficiency.Inordertoimprovetheefficiency,thisarticlestudiesthematchingquestionofregularexpressionfromthefol

8、lowingseveralaspects:Firstly,puttingacce