带可变长度通配符的模式匹配算法  

Pattern matching with variable length wildcards

作　　者：沈璐[1,2] 纪允[1] 纪冬宝 李萍[4] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]芜湖职业技术学院电气系,安徽芜湖241006 [3]安徽现代电视技术有限公司,合肥230088 [4]安徽林业职业技术学院信息与艺术系,合肥230031

出　　处：《计算机工程与应用》2015年第15期43-47,55,共6页Computer Engineering and Applications

基　　金：安徽省高等学校省级一般教学研究项目(No.20101264)

摘　　要：针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时,需要的时间是多项式级别,而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI(pAttern mAtching with wIldcards)算法,计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为O(n+m+α)和O(m+B),其中n和m分别表示文本和模式的长度,α是所有子模式在文本中出现的数目,B是模式中通配符间距下限的总和。通过真实数据和人工数据的实验结果表明,AAI算法与同类算法相比具备显著的优势。Current works on computing the number of all matches of pattern with variable length wildcards in text need polynomial time, and have been greatly influenced by the length of the text, pattern, and wildcards interval. This paper proposes an algorithm AAI（p Attern m Atching with w Ildcards）based on Aho-corasick automaton which adopts dynamic programming and effective pruning strategies. Let n and m be the length of P and T, respectively. The algorithm AAI need time O（n ＋ m ＋ α） and space O（m ＋ B）, where α is the total number of occurrences of the subpatterns in P within S, B is the sum of the lower bonds of the wildcards. Experimental results from different aspects validate that AAI is more stable and effective than other peers on both artificial and real-world data.

关 键 词：模式匹配 通配符 动态规划 Aho-Corasick自动机 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]