软件学报

作者：武优西，刘茜，闫文杰，郭磊，吴信东

单位：武优西，河北工业大学 人工智能与数据科学学院, 天津 300401;省部共建电工装备可靠性与智能化国家重点实验室(河北工业大学), 天津 300401;河北省大数据计算重点实验室, 天津 30040111,刘茜，河北工业大学 人工智能与数据科学学院, 天津 300401;省部共建电工装备可靠性与智能化国家重点实验室(河北工业大学), 天津 300401;河北省大数据计算重点实验室, 天津 30040102,闫文杰，河北工业大学 人工智能与数据科学学院, 天津 300401;省部共建电工装备可靠性与智能化国家重点实验室(河北工业大学), 天津 300401;河北省大数据计算重点实验室, 天津 30040103,郭磊，省部共建电工装备可靠性与智能化国家重点实验室(河北工业大学), 天津 300401;河北工业大学 电气学院, 天津 30040104,吴信东，教育部大数据知识工程重点实验室(合肥工业大学), 合肥 230009;明略科学院 明略科技集团, 北京 10008405

关键词：模式匹配;序列模式挖掘;无重叠条件;网树;回溯策略

基金：国家重点研发计划（2016YFB1000901）；国家自然科学基金（61976240，61702157，917446209）；河北省创新能力培养资助项目（CXZZSS2019023）

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法，与同类挖掘方法相比，该方法更容易发现有价值的频繁模式，其核心问题是计算给定模式在序列中的支持度或出现数，进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现，然后剪枝无用结点的方式计算模式的支持度，其计算时间复杂度为O （m×m×n×W），其中，m，n和W分别为模式长度、序列长度及最大间隙.为了进一步提高无重叠条件模式匹配计算速度，从而有效地降低无重叠条件序列模式挖掘时间，提出了一种高效的算法，该算法将模式匹配问题转换为一棵网树，然后从网树的最小树根结点出发，采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现，在网树上剪枝该出现后，无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备性，并将该算法的时间复杂度降低为O （m×n×W）.在此基础上，继续指明该问题还存在另外3种相似的求解策略，分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式.实验结果验证了该算法的性能，特别是在序列模式挖掘中，应用该方法的挖掘算法可以降低挖掘时间.

来源：2021年第11期

《软件学报》期刊编辑部

查看软件学报杂志2021年第11期