分段处理的1/p概率字符串匹配

摘要：

现有的概率字符串匹配算法通过计算字符串之间的最小失配字符数(编辑距离),可求出字符串之间的相似度.这些算法平等地看待模式串和文本串,虽然可求出二者之间完整的编辑距离,但并不能解决以下问题:即判断是否模式串中至少有1/p的字符顺序地出现在文本串中.基于动态规划字符串匹配算法,提出了一个改进算法.该算法通过将字符串分段,在段内执行改进的概率匹配算法可求出段内的编辑距离,再结合回溯策略可以很好地解决上述问题.该算法的复杂性要低于基本动态规划匹配算法,且在某些情况下效率更高.就问题的一般性而言,该算法可广泛地应用于计算生物学、信息安全和信号处理等诸多领域.

关键词：概率字符串匹配、动态规划、分段策略、回溯策略

所属期刊栏目：35

分类号：TP3;TN9

资助基金：国家自然科学基金60673075;国家高技术研究发展计划8632006AA01Z428

在线出版日期：2008-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：91-95