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

Pattern Matching with Wildcards Based on Suffix Tree

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构——后缀树,设计了求解模式所有解的完备算法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.