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

武优西; 王博; 高雪冬

首页> 中文期刊> 《计算机工程与科学》 >无重叠条件模式匹配的在线求解算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机工程与科学》 |2019年第12期|2239-2246|共8页
作者
武优西; 王博; 高雪冬;
展开▼
作者单位

河北工业大学人工智能与数据科学学院天津 300401;

展开▼
原文格式 PDF
正文语种 chi
中图分类信息处理（信息加工）;
关键词
模式匹配; 间隙约束; 无重叠条件; 在线算法; 网树;

相似文献

中文文献
外文文献
专利

1. 无重叠条件严格模式匹配的高效求解算法 [J] . 武优西 ,刘茜 ,闫文杰 . 软件学报 . 2021,第011期
2. 基于模式匹配和静态评估的计算机围棋布局问题求解算法 [J] . YU Lei ,CHEN Han . 数字技术与应用 . 2018,第012期
3. 基于模式匹配和静态评估的计算机围棋布局问题求解算法 [J] . 余磊1 ,陈涵1 . 数字技术与应用 . 2018,第012期
4. 熊去氧胆酸治疗无重叠和有重叠特征原发性胆汁性肝硬化的疗效及生存分析 [J] . 孙颖 ,常彬霞 ,滕光菊 . 传染病信息 . 2013,第005期
5. 金属材料无负载条件下尺寸稳定性的热循环在线检测 [J] . 王秀芳 ,武高辉 ,李晓玲 . 中国有色金属学报 . 2003,第003期
6. 无回溯模式匹配算法的设计与研究 [C] . 马海云 ,张少刚 . 2011年西南三省一市自动化与仪器仪表学术年会 . 2011
7. 无重叠条件模式匹配的在线求解算法研究 [A] . 王博 . 2019

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

摘要

著录项

相似文献

相关主题

期刊订阅