求解PMWOC问题的位并行算法

• 作者: 叶明全 张浩
• 来源期刊: 计算机应用研究
• 关键词: 模式匹配 通配符 One-Off条件
• 年，卷（期）: 2015,（10）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2973-2977
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2015.10.022

摘要

带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值.给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即One-Off条件.提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描.通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	叶明全	皖南医学院计算机教研室	86	416	11.0	17.0
2	张浩	皖南医学院计算机教研室	15	46	3.0	6.0