基于后缀数组字符串模式查找算法

《基于后缀数组字符串模式查找算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文M．D．Thesis基于后缀数组的字符串模式查找的算法TheStringPatternSearchingAlgorithmsBasedonSuffixArrays张利香ZhangLiXiangI摘要模式匹配问题是计算机科学的一个基本问题。在早期的模式匹配研究中，多数算法集中于精确模式匹配的研究，如：著名的单模式匹配算法KMP、BM及多模式匹配算法CA、CW、BNDM等。但在实际应用中，近似模式匹配算法在信息过滤及计算生物学等领域显得非常重要。比如人们通常在DNA的片段分析中，只是寻找到与目标模式相似的DNA片段，从而判断

2、它们之间是否有亲缘关系等等。要在海量的信息中快速地找到有意义的模式串，运用一般的方法进行模式查找，所花费的时间让人难以忍受，为了提高模式查找算法的运行效率，这里提出了模式查找的新算法。本文是针对长篇英文小说中的高频词（模式串）查找问题，应用了近似串匹配的过滤的思想，提出了模式查找的算法Epattern_searcherH和Epattern_searcher。本论文的主要工作如下：(1)提出了模式查找的算法。针对近似模式匹配中过滤思想设计模式查找的算法，首先按照一定的过滤原则（某种条件限定）搜索文本串，过滤掉那些不可能发生匹配的的文本

3、段；然后验证剩下的匹配候选位置处是否真的存在成功匹配。由于过滤去了大部分不可能发生匹配的文本串，加速了匹配的查找过程，从而达到提高模式查找算法运行效率的目的。(2)应用后缀数组的数据结构来实现提出的算法。对于字符串处理问题，后缀树是一种很好的数据结构，但后缀树需要占用较大内存空间，而空间问题一直是运用后缀树数据结构来处理超长字符串的一个瓶颈。与后缀树结构相比，后缀数组可节约三分之二以上的空间，因此这里运用后缀数组的数据结构来实现提出的算法。关键词:模式查找；串匹配；后缀数组；英文高频词；过滤；编辑距离IIAbstractPatter

4、n-matchingproblemisafundamentalproblemincomputerscience.Intheearlyyears,mostofpattern-matchingalgorithemsfocusontheexactpattern-matchingalgorithmsstudy,suchas:well-knownsinglepatternmatchingalgorithmsKMPBMandmulti-patternmatchingalgorithmsCACWBNDMso.However,inpractical

5、applications,itisveryimportantthatapproximatepatternmatchingininformationfilteringandcomputationalbiologyandotherfields.Forexample,intheanalysisofDANfragments,peopleusuallysearchsimilarpatternswiththetargetDNAfragment,inordertodeterminewhethertherearegeneticrelationsbe

6、tweenthem.Tosearchameaningfulpatternstringquicklyinthevastamountsofinformation,wemustimprovetheefficiencyofpatternmatchingalgorithms.Therefore,itisnecessarytoimprovepattern-matchingalgorithmsfurtherly.Herefortheproblemofsearchingthehigh-frequencywords(patternstring)inl

7、ongerEnglishnovel,weappliedfilteringideastopresentapproximatestringpatternsearchingalgorithmsEpattern_searcherHandEpattern_searcher.Themainworkofthispaperisasfollows:(1)Proposethealgorithmsofpatternsearching,fortheideaofthefilterdesignpatternsearchingalgorithmsofapprox

8、imatepatternmatching.First,accordingtocertainfilterprinciples(limitedtocertainconditions)tosearchatextstring,filterou