顺序检测近似串匹配算法研究

《顺序检测近似串匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、太原理工大学硕士研究生论文顺序检测近似串匹配算法研究摘要近似串匹配是计算机科学的基础问题，在文本检索、生物信息学、信号处理、入侵检测、模式识别、数据挖掘和实体识别等领域具有广泛的应用。近似串匹配的效率决定了这些应用的效率。传统的动态规划方法效率低，自动机方法构造复杂，过滤验证方法以其高效、简明成为使用最广泛的近似串匹配方法。为了进一步提高过滤验证算法的效率，本文提出用于近似串匹配的顺序检测方法，具体内容包括以下方面：1.提出顺序检测计算编辑距离的方法。该方法顺序比对两个字符串的当前位置，通过合理认定不匹配位置的基本操作，得到其编辑距离。该方2法时间复杂度为O(n

2、)，与动态规划法的O(n)相比，具有明显的优势。不匹配位置的基本操作认定，本文提出两种方法:第一种方法是基于基本操作序列顺序验证。该方法先枚举某一编辑距离对应的所有基本操作序列。顺序检测时，按照基本操作序列确定不匹配位置的基本操作，该方法适用于小于等于3的编辑距离的计算。第二种方法是基于局部最优规则(综合考虑当前位置每增加一个基本操作所能处理的字符数和处理后两子字符串的长度差)来确定当前位置的基本操作。按照该方法得到编辑距离的一个上界，可得到大部分符合条件的字符串，也可以为其设置一个上界，对剩余字符串进行过滤。2.以顺序检测方法为核心，在过滤验证的框架下，提出阈

3、值为k的近似串匹配算法。过滤阶段，先进行离线的count过滤，然后基于局部最优I太原理工大学硕士研究生论文规则顺序检测方法估计两个字符串的编辑距离，根据估计值对候选集进行筛选过滤；验证阶段，阈值k小于等于3时，用基本操作序列顺序验证方法验证两字符串的编辑距离，否则，用动态规划法验证其编辑距离。实验结果表明，相比目前高效的MergeFilter算法，本文方法在DBLP、IMDB、WEBCorpus数据集中的时间效率至少提高17%。关键词近似串匹配，编辑距离，顺序检测，基本操作序列，局部最优规则II太原理工大学硕士研究生论文SequentiallyMatchingS

4、imilarityStringAlgorithmResearchABSTRACTApproximatestringmatchingisabasisprobleminthecomputerscience,whichwasbeenappliedwidelyinthefieldoftextretrieval,bioinformatics,signalprocessing,intrusiondetection,patternrecognition,dataminingandentityrecognitionetc.Thematchingefficiencydetermi

5、nestheefficiencyoftheseapplications.Thetraditionaldynamicprogrammingalgorithmisinefficient,andtheautomationalgorithmiscomplex,sothefiltering-verificationalgorithmbecamethemostpopularmethod.Inordertoimprovetheefficiency,weproposedasequentialdetectionmethod.Thecontentsofthispaperareasf

6、ollows.1.Weproposedasequentialdetectionmethodtocomputeeditdistance,whichcomparesthestringsinorder.Whenthelocalpositionismismatch,wechooseareasonableeditbasicoperation.Thisalgorithm’stimecomplexityis2O(n),whilethedynamicprogrammingisO(n).Thekeyistochoosethebasicoperationwhenthelocalpo

7、sitionismismatch.Thispaperproposedtwomethods.Thefirstmethodisbasedonthebasicoperationsequence.First,weenumeratethebasicoperationsequenceofacertaineditdistance.Accordingtothebasicoperationsequence,wechoosethebasicoperationoflocalmismatchpositon.Thisalgorithmapplieswhentheeditdistancei

8、slessthanore