基于后缀树的带有通配符的模式匹配研究

• 作者: 侯宝剑 刘应玲 王海平 胡学钢 谢飞
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 模式匹配 通配符 后缀树
• 年，卷（期）: 2012,（12）
• 所属期刊栏目: 人工智能
• 页码范围: 177-180,194
• 页数: 5页
• 分类号: TP309
• 字数: 5245字
• 语种: 中文

摘要

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究的热点.针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束.采用非线性数据结构——后缀树,设计了求解模式所有解的完备算法PAST.预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合动态规划的思想,逐个匹配模式中字符,最终得到完备解.在基因序列上的实验表明,PAST比其他算法具有更好的时间性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡学钢	合肥工业大学计算机与信息学院	314	3156	27.0	39.0
2	侯宝剑	合肥工业大学计算机与信息学院	1	13	1.0	1.0
3	谢飞	合肥工业大学计算机与信息学院	19	217	8.0	14.0
7	刘应玲	合肥工业大学计算机与信息学院	3	18	2.0	3.0
11	王海平	合肥工业大学计算机与信息学院	9	43	4.0	6.0