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

Pattern Matching with Wildcards Based on Suffix Tree

作　　者：侯宝剑[1] 谢飞[1,2] 胡学钢[1] 刘应玲[1,3] 王海平[1] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]合肥师范学院计算机科学与技术系,合肥230601 [3]中国科学技术大学物理学院,合肥230026

出　　处：《计算机科学》2012年第12期177-180,194,共5页Computer Science

基　　金：国家"863"计划课题(2012AA011005);国家博士后科学基金(2012M511403);安徽省自然科学基金(11040606M134);中央高校基本科研基金(2010HGXJ0714)资助

摘　　要：由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构——后缀树,设计了求解模式所有解的完备算法PAST。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的时间性能。Pattern matching with wildcards is a hot research problem that can be used in biological sequence analysis,text indexing,network intrusion detection,and so on.Aiming at the problem that the wildcards have strong limitations in the existing research work,pattern matching with flexible wildcards was studied.The wildcards can appear between any two substrings and can be specified with flexible length constraints.The nonlinear data structure—suffix tree was used to design a completeness algorithm PAST.In the prepare process,an online incremental algorithm was used to build the suffix tree which has priori knowledge of the text.In the search phase,the idea of dynamic programming was used to match the characters of the pattern.Experiments on DNA sequences show that our method has better perfor-mances in time than the related matching algorithm.

关 键 词：模式匹配 通配符 后缀树 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]