文献类型：期刊文章

作　　者：武优西[1,2] 吴信东[3,2] 江贺[4,2] 闵帆[5,2]

机构地区：[1]河北工业大学计算机科学与软件学院,天津300130 [2]佛蒙特大学计算机系 [3]合肥工业大学计算机科学与信息工程学院,合肥230009 [4]大连理工大学软件学院,辽宁大连116621 [5]漳州师范学院粒计算重点实验室,福建漳州363000

出　　处：《计算机学报》

基　　金：国家自然科学基金(60828005)资助~~

年　　份：2011

卷　　号：34

期　　号：8

起止页码：1452-1462

语　　种：中文

收录情况：BDHX、BDHX2008、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI(收录号：20113714332528)、INSPEC、JST、MR、SCOPUS、ZGKJHX、核心刊

摘　　要：具有间隙约束和一次性条件的最大模式匹配(Maximum Pattern Matching with Gaps and One-Off Condition,MPMGOOC)是一种具有通配符长度约束的模式匹配问题,其任务是寻找彼此互不相关的最多出现.文中基于一种新的非线性数据结构——网树,提出了一种解决MPMGOOC问题的启发式算法.与树结构不同之处在于,除根结点外,网树中任何结点可以多于1个双亲结点.文中给出了网树的定义及其相关的概念和性质.基于这些概念和性质,提出了一种选择较优出现(Selecting Better Occurrence,SBO)的启发式算法.该算法在搜索一个出现的循环中,采用了贪婪搜索双亲策略(Strategy of Greedy-Search Parent,SGSP)和最右双亲策略(Strategy of RightMostParent,SRMP)寻找相同叶子的两个出现并选择其中较好的出现作为SBO算法的结果.SGSP策略的核心思想是每一步都寻找当前结点的一个近似最优双亲(Approximately Optimimal Parent,AOP);SRMP策略的核心思想是每一步都寻找当前结点的最右双亲结点.实验结果表明,在多数情况下SBO算法可以获得更好的解且解的质量较其它算法有显著的提高.文中不但提供了一个解决MPMGOOC问题的启发式算法,更重要的是对于求解其它复杂问题具有一定的参考价值.

关 键 词：模式匹配  通配符 一次性条件  网树  启发式算法

分 类 号：TP301]