无重叠条件模式匹配的在线求解算法

• 作者: 武优西 王博 高雪冬
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 模式匹配 间隙约束 无重叠条件 在线算法 网树
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 人工智能与数据挖掘
• 页码范围: 2239-2246
• 页数: 8页
• 分类号: TP391
• 字数: 6371字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2019.12.020

摘要

无重叠条件模式匹配是众多间隙约束的模式匹配算法中的一种,尽管当前证明了无重叠条件模式匹配是一个多项式时间复杂度问题,并提出了有效的求解算法,但是当前求解算法采用离线计算方式,具有空间复杂度较高的缺点.为了解决该问题,设计了一种在线求解算法,该算法一边读入序列串,一边在流网树中寻找符合约束条件的树根-树叶路径,以快速剪枝无用节点,从而加快了匹配速度.与离线算法的空间复杂度相比,在线算法的空间复杂度为O(m×maxlen×W),这里m,maxlen和W分别表示模式串长度、模式最大长度约束和最大间隙约束.实验结果不仅验证了算法的完备性,与现有算法相比,在内存占用上均有较大性能的提升.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	武优西	河北工业大学人工智能与数据科学学院	28	466	10.0	21.0
2	高雪冬	河北工业大学人工智能与数据科学学院	16	52	4.0	6.0
3	王博	河北工业大学人工智能与数据科学学院	3	0	0.0	0.0