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

摘要：

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

关键词： Pattern matching Wildcards Suffix tree

作者: 侯宝剑 谢飞 胡学钢 刘应玲 王海平

作者单位: 合肥工业大学计算机与信息学院 合肥230009 合肥工业大学计算机与信息学院 合肥230009;合肥师范学院计算机科学与技术系 合肥230601 合肥工业大学计算机与信息学院 合肥230009;中国科学技术大学物理学院 合肥230026

会议类型: 国内会议

会议名称: 第十二届中国Rough集与软计算学术会议、第六届中国Web智能学术研讨会及第六届中国粒计算学术研讨会联合学术会议

会议地点: 合肥

会议语种:中文

页码: 93-93

在线出版日期: 2012-10-13（万方平台首次上网日期，不代表论文的发表时间）