Page 5 - 《软件学报》2021年第11期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(11):3331−3350 [doi: 10.13328/j.cnki.jos.006054] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
无重叠条件严格模式匹配的高效求解算法

2,4
武优西 1,2,3 , 刘 茜 1,2,3 , 闫文杰 1,2,3 , 郭 磊 , 吴信东 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 种相似的求解策略,分别
是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最
右双亲方式.实验结果验证了该算法的性能,特别是在序列模式挖掘中,应用该方法的挖掘算法可以降低挖掘时间.
关键词: 模式匹配;序列模式挖掘;无重叠条件;网树;回溯策略
中图法分类号: TP301

中文引用格式: 武优西,刘茜,闫文杰,郭磊,吴信东.无重叠条件严格模式匹配的高效求解算法.软件学报,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.htm

Efficient Algorithm for Solving Strict Pattern Matching Under Nonoverlapping Condition
2,4
WU You-Xi 1,2,3 , LIU Xi 1,2,3 , YAN Wen-Jie 1,2,3 , GUO Lei , 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 Reliability and Intelligence of Electrical Equipment, Hebei University of Technology, Tianjin 300401, China)
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 of Hebei Province (CXZZSS2019023)
收稿时间: 2019-06-10; 修改时间: 2019-12-25; 采用时间: 2020-04-12