武优西,陈 彤,闫文杰,高雪冬

(河北工业大学 人工智能与数据科学学院,天津 300401) (河北省大数据重点实验室,天津 300401)

1 引 言

模式匹配(又称字符串匹配)是计算机科学的基础问题之一[1],其在生物信息学[2]、网络入侵[3]以及数据挖掘[4]等诸多领域具有重要应用,其问题实质是在一个相对长的序列串S上查找相对较短的模式P所有出现的位置及个数,这里序列串S以及模式P必须采用相同的字母表中[5].

近年来,为了满足实际需要,在传统通配符的基础上,研究者们致力于间隙约束的模式匹配,其模式串P可以表示为:P=p1[a1,b1]p2…[aj,bj]pj+1…[am-1,bm-1]pm(1≤j≤m),其中aj和bj分别为pj和pj+1之间通配符之间最小和最大通配符的个数.这种间隙约束的模式在序列模式挖掘中亦有深入探索,如Min等人[6]在间隙约束下探索了序列中字符作用不均等的模式挖掘方法;Wu等人[7]采用网树结构对周期性一般间隙的序列模式挖掘问题进行研究;Ding等人[8]在无重叠条件下探索了间隙约束的序列模式挖掘问题;文献[9]中提出免预设间隔约束的对比序列模式高效挖掘算法,解决了序列数据挖掘问题;Dong等人[10]在挖掘重复模式问题上,提出了e-RNSP算法;Tan等人[11]根据位置的频繁模式检测,提出具有弱通配符间隙算法.在上述研究中,均需采用间隙约束模式匹配技术实现模式支持度的计算,从而判定模式的频繁性,因此这种间隙约束模式匹配是序列模式挖掘的核心与基础[12].

当前研究主要在非负间隙下进行研究,即aj≥0,但一般间隙约束能得到……