基于后缀数组的近似字符串匹配

《基于后缀数组的近似字符串匹配》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、I摘要字符串匹配问题是计算机科学研究中最基础的问题之一。早期的研究多集中于精确字符串匹配领域，就精确字符串匹配提出了许多单模式和多模式匹配算法。然而在信息检索、模式识别和计算生物学等一些实际应用中有时候更需要查找的是近似匹配字符串。因此研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。本文首先介绍了近似字符串匹配算法的研究现状和近似字符串的相关理论和主要研究方法—动态规划、自动机、位并行、过滤等技术。结合后缀数组这一索引结构，本文提出了基于后缀数组的近似字符串匹配算法，即IS_DP算法。算法使用后缀数组加快在动态规

2、划矩阵上的迭代速度，从而达到O(kn)的时间复杂度和空间复杂度。用后缀数组构造算法可以预先排序文本串后缀，求解后缀数组中相邻后缀的最长公共前缀，从而可以在O(1)时间内计算出任意两个后缀串的最长共有前缀长度。本文算法是对原有的基于动态规划的近似字符串匹配算法的改进，通过加速矩阵对角线上扩展的方式降低了构造动态规划矩阵的时间消耗，进而在O(kn)时间内查找出文本中所有的近似匹配字符串，与一些在后缀树上查找近似字符串匹配的算法相比较，本文算法采用后缀数组结构可以节省约5n的存储空间。关键词：动态规划后缀数组编辑距离近似字符串匹

3、配最长公共前缀数组IIIAbstractStringmatchingisoneofthebasicproblemsincomputerscience.Alotofresearcheswerefocusingonexactstringmatchinginearlytime,andmanyalgorithmsofsingleandmultiplestringmatchinghavebeenproposed.However,inapplicationssuchasinformationretrieval,patternrecog

4、nitionandcomputationalbiology,approximatestringmatchingmakesmoresense.Sothereissomuchtheoreticalvalueandpracticalmeaningtoresearchanddesignefficientapproximatestringmatchingalgorithms.Inthebeginning,thispaperintroducestheresearchstatusandbasictheoriesofapproximate

5、stringmatching,andthenpresentsthemainapproacheswhichincludedynamicprogramming,automata,bit-parallelismandfiltering.ThenwecomeupwithourapproximatestringmatchingoversuffixarrayalgorithmwhichisshortforIS_DPalgorithm.IS_DPalgorithmusessuffixarrayforacceleratingthecomp

6、utationalongthedynamicprogrammingtableandreachesrunningtimeinO(kn).SuffixarrayareusedforpreprocessingthesequencesallowinganO(1)runningtimecomputationofthelongestcommonextensionbetweensubstrings.Comparedwiththeclassicapproximatestringmatchingalgorithmwhichisbasedon

7、dynamicprogramming,ouralgorithmshowsprettygoodtimecomplexitywhichisO(kn);besides,comparedwithsomeapproximatestringmatchingalgorithmswhicharebasedonsuffixtree,IS_DPalgorithmdoesimprovetheactualspaceusage.Keywords:dynamicprogrammingsuffixarrayeditdistanceapproximate

8、stringmatchinglongestcommonprefix目录第一章绪论................................................................................................................