无重叠条件严格模式匹配的高效求解算法-武优西，刘茜，闫文杰，郭磊，吴信东 - 副本.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(11):3331−3350 [doi: 10.13 328/j.cnki.jos.006054] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
无重叠条件严格模式匹配的高效求解算法
∗
武优西
1,2, 3
,
刘
茜
1,2,3
,
闫文杰
1,2, 3
,
郭
磊
2,4
,
吴信东
5,6
1
(河北工业大学 人工智能与数据科学学院,天津 300401)
2
(省部共建电工装备可靠性与智能化国家重点实验室(河北工业大学),天津 300401)
3
(河北省大数据计算重点实验室,天津 300401)
4
(河北工业大学 电气学院,天津 300401)
5
(教育部大数据知识工程重点实验室(合肥工业大学),合肥 230009)
6
(明略科学院 明略科技集团,北京 100084)
通讯作者: 武优西, E-mail: wuc567@163.com
摘 要: 无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现
有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性.而计算模式
支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现,然后剪枝无用结点的方式计算模式的
支持度,其计算时间复杂度为 O(m×m×n×W),其中,m,n 和 W 分别为模式长度、序列长度及最大间隙.为了进一步提高
无重叠条件模式匹配计算速度,从而有效地降低无重叠条件序列模式挖掘时间,提出了一种高效的算法,该算法将模
式匹配问题转换为一棵网树,然后从网树的最小树根结点出发,采用回溯策略迭代搜索最左孩子方式计算无重叠最
小出现,在网树上剪枝该出现后,无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备
性,并将该算法的时间复杂度降低为 O(m×n×W).在此基础上,继续指明该问题还存在另外 3 种相似的求解策略,分别
是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最
右双亲方式.实验结果验证了该算法的性能,特别是在序列模式挖掘中,应用该方法的挖掘算法可以降低挖掘时间.
关键词: 模式匹配;序列模式挖掘;无重叠条件;网树;回溯策略
中图法分类号: TP3
01
中文引用格式: 武优西,刘茜,闫文杰,郭磊,吴信东.无重叠条件严格模式匹配的高效求解算法. 软件学报,2021,32(11):
3331−3350. http ://www.jos.org.cn/1000-9825/6054.htm
英文引用格式: Wu YX, Liu X, Yan WJ, Guo L, Wu XD. Efficient algorithm for solving strict pattern matching under
nonoverlapping condition. Ruan Jian Xue Bao/Journal of Software, 2021,32(11):3331−3350 (in Chinese). http://www.jos.org.cn/
1000-9825/6054.ht m
Efficient Algorithm for Solving Strict Pattern Matchi ng Under Nonoverlapp ing Condi tion
WU You-Xi
1,2,3
, LIU Xi
1,2,3
, YAN Wen-Jie
1,2,3
, GUO Lei
2,4
, WU Xin-Dong
5,6
1
(School of Artificial Intelligence, Hebei University of Technology, Tianjin 300401, China)
2
(Hebei Key Laboratory of Big Data Computing, Tianjin 300401, China)
3
(State Key Laboratory of Reliabilit y and Int elligence of Electrical Equipment, Hebei University of Technology, Tianjin 300401 , Chi na)
4
(School of Electrical Engineering, Hebei University of Technology, Tianjin 300401, China)
∗ 基金项目: 国家重点研发计划(2016YFB1000901); 国家自然科学基金(61976240, 61702157, 917446209); 河北省创新能力培养
资助项目(CXZZSS2019023)
Foundation item: National Key Research and Development Program of China (2016YFB1000901); National Natural Science
Foundation of China (61976240, 61702157, 917446209) ; Graduate Student Innovation Program o f Hebei Provin ce (CXZZSS2019023)
收稿时间: 2019-06-10; 修改时间: 2 019-12-25; 采用时间: 2020-04-12
3332
Journal of Software 软件学报 Vol.32, No.11, November 2021
5
(Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology), Ministry of Education, Hefei 230009,
China)
6
(Mininglamp Academy of Sciences, Mininglamp Technology, Beijing 100084, Chin a)
Abstra ct : Nonoverlapping conditional sequence pattern mining is a meth od of gap constrained sequence pattern mining. Compared with
similar mining methods, this method is easier to find valuable frequent patterns. The core of the probl em is to calculate th e support (or the
number of occurrences) of a pattern in the sequence, and then determine whether the pattern is frequent. The essence of calculating the
support is the pattern matching under nonoverlapp ing condition. The current studies employ the iterative search to find a nonoverlapping
occurrence, and then prune the useless nodes to calculate the support of the pattern. The computational time complexity of these
algorithms is O(m×m×n×W), where m, n, and W are the pattern length, sequence length, and maximum gap, respectively. In order to
improve the calculation speed of pattern matching under nonoverlapping condition, and effectively reduce sequence pattern mining time,
this study proposes an efficient and effective algorithm, which converts the pattern matching problem into a NetTree, then starts from the
minroot node of th e NetTree, and adopts the backtracking strat egy to iteratively search th e leftmost child to calculate the nonoverlapping
minimum occurrence. After pruning the occurrence on the NetTree, the problem can be solved without further searching and pruning
invalid nodes. This study proves the completeness of the algorithm and reduces the time complexity to O(m×n×W). On this basis, the
study continues to indicate that there are other three similar solving strategies for this problem, iteratively finds the leftmost parent path
from the leftmost leaf, th e rightmost child p ath from th e right most root, and th e right most parent p ath fro m the ri ghtmost le af. Extensively
experimental results verify the efficiency of the proposed algorithm in this study, especially, the mining algorithm adopting this method
can reduce the mining time.
Key words: pattern matching; sequence pattern mining ; nonov erlapping condition; NetTree; b acktracking s trategy
模式匹配作为计算机科学的基本问题之一,包括大数据挖掘
[1]
在内的诸多研究都建立在模式匹配的基础
上,如序列模式挖掘
[2,3]
、时间序列分析与预测
[4]
、生物序列数据分析
[5]
、网络入侵检测
[6]
、正负序列分析
[7,8]
以及大空间数据库中的字符串搜索
[9,10]
.近年来,具有间隙约束的模式匹配逐渐引起研究者们的广泛关注,如
Manbe r 等人
[11]
最先研究了具有间隙约束的模式匹配问题,但其模式中只有一个可变间隙,具有一定的局限性.
随着研究的深入,更多学者将注意力转向具有多个可变间隙约束模式匹配问题(或称间隙约束模式匹配问
题)
[12]
.具有多个可变间隙的模式匹配在诸多领域具有广泛的应用,例如,在计算生物学中,Navarro 和 Raffinot
[13]
采用此种模式匹配提出了更为优化的搜索方法用来寻找特殊蛋白质位点,Drory 等人
[14]
实现了 RNA 序列的
motif 结构检测;在文本匹配方面,Cole 等人
[15]
在可变间隙近似模式匹配下有效地判断模式串是否在指定的文本
或字典中.特别需要指出的是,具有间隙约束模式匹配在序列模式挖掘领域具有重要应用
[16,17]
.传统序列模式挖
掘研究只关注模式在序列中是否存在,而不关注模式在序列中出现的次数. 这导致序列串“AC”与序列串
“ACACACAC”的作用相同,因此,传统序列模式挖掘方式会在诸如 DNA 序列等长序列挖掘中丢失诸多重要信
息.为了弥补传统序列模式挖掘的不足,可重复序列模式挖掘孕育而生
[18]
,这种挖掘方法更加关注模式在序列中
出现的次数
[19,20]
.为了避免匹配的序列间隔过大,间隙约束序列模式挖掘孕育而生,其核心工作之一是计算模式
在序列中的出现次数,即支持度,实质上就是间隙约束模式匹配问题
[21]
.在间隙约束序列模式挖掘和模式匹配问
题中,模式串可以写作 P=p
1
[min
1
,ma x
1
]p
2
…[min
j−1
,max
j−1
]p
j
…[min
m−1
,max
m−1
]p
m
的形式
[22]
,其中,min
j−1
和 max
j−1
分别指 p
j−1
和 p
j
之间通配符的最小和最大个数
[23]
.间隙约束作为一种新型的通配符,比传统通配符“? ”和“*” 更具
灵活性与适用性,这是因为其允许在 p
j−1
和 p
j
之间通配的字符数量是一个范围值,而非一个确定值.
无重叠条件的模式匹配作为间隙约束模式匹配的一种方法,最早是在文献[24]中提出,其是指允许序列中
的任意位置的字符重复使用,但不允许同一字符在相同位置多次使用.Wu 等人
[25]
严格形式化地给出了无重叠
条件模式匹配的定义,并理论证明了该问题的复杂度为 P.之后,文献[26]研究了无重叠条件序列模式挖掘,并有
效地解决了间隙约束序列模式挖掘难以兼顾 Apriori 性质和挖掘完备性的问题
[5,20]
.下面举例说明无重叠条件
模式匹配问题.
例 1:给定序列串 S=s
1
s
2
s
3
s
4
s
5
s
6
s
7
s
8
=ag gcaaga,模式串 P=p
1
[mi n
1
,max
1
]p
2
[min
2
,max
2
]p
3
=a[0,1]g[0,1 ]a.
子模式 a[0,1]g 指在 a 与 g 之间可以没有间隙或者有一个通配符“? ”, 也就是说,a 与 g 之间可以通配 0~1 个
字符.由图 1 可知:例 1 中满足间隙约束的出现共有 3 个,分别是〈1,3,5〉,〈5,7,8〉,〈6,7,8〉.出现〈5,7,8〉和〈6,7 , 8〉均在相
of 20
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论