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

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (15): 43-47.

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

沈璐1，2，纪允1，纪冬宝3，李萍4

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

出版日期:2015-08-01 发布日期:2015-08-14

Pattern matching with variable length wildcards

SHEN Lu1，2, JI Yun1, JI Dongbao3, LI Ping4

1.School of Computer and Information, Hefei University of Technology, Hefei 230009, China
2.Department of Electrical Engineering, Wuhu Institute of Technology, Wuhu, Anhui 241006, China
3.Anhui Modern TV Technology Co., Ltd, Hefei 230088, China
4.Department of Information and Art, Anhui Vocational and Technical College of Forestry, Hefei 230031, China

Online:2015-08-01 Published:2015-08-14

摘要/Abstract

摘要： 针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时，需要的时间是多项式级别，而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI（pAttern mAtching with wIldcards）算法，计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为[O(n+m+α)]和[O(m+B)]，其中[n]和[m]分别表示文本和模式的长度，[α]是所有子模式在文本中出现的数目，[B]是模式中通配符间距下限的总和。通过真实数据和人工数据的实验结果表明，AAI算法与同类算法相比具备显著的优势。

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

Abstract: 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（pAttern mAtching with wIldcards） 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.

Key words: pattern matching, wildcards, dynamic programming, Aho-Corasick automaton

沈璐1，2，纪允1，纪冬宝3，李萍4. 带可变长度通配符的模式匹配算法[J]. 计算机工程与应用, 2015, 51(15): 43-47.

SHEN Lu1，2, JI Yun1, JI Dongbao3, LI Ping4. Pattern matching with variable length wildcards[J]. Computer Engineering and Applications, 2015, 51(15): 43-47.

[1]	周睿慜，李辉. 改进动态规划算法的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(21): 20-24.
[2]	孙云浩，李逢雨，李冠宇，韩冰，邢维康. 面向RDF图的多模式匹配方法[J]. 计算机工程与应用, 2020, 56(13): 84-92.
[3]	王红，祝寒，林海舟. 航空安全事故因果关系抽取方法的研究[J]. 计算机工程与应用, 2020, 56(11): 265-270.
[4]	谭章禄，王兆刚，胡翰. 时间序列趋势相似性度量方法研究[J]. 计算机工程与应用, 2020, 56(10): 94-99.
[5]	黄思猛1，程良伦2，王涛2. 基于双数组trie树的多模式复杂事件检测方法[J]. 计算机工程与应用, 2019, 55(4): 91-95.
[6]	陈俊杰，同淑荣，聂亚菲，张静文. 考虑胜任力水平的研发项目群人力资源调度[J]. 计算机工程与应用, 2019, 55(3): 209-218.
[7]	连玮. 采用树表示的全局最优形状匹配算法[J]. 计算机工程与应用, 2019, 55(1): 217-225.
[8]	张雨，崔耀东，梁泽华. 多尺寸圆木二维下料问题研究[J]. 计算机工程与应用, 2018, 54(19): 266-270.
[9]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[10]	夏念，嵩天. 短规则有效的快速多模式匹配算法[J]. 计算机工程与应用, 2017, 53(7): 1-8.
[11]	王歧1，2，3，卢毓海1，3，刘洋1，3，刘燕兵1，3，谭建龙1，3，孙波4. 支持模式串动态更新的多模式匹配Karp-Rabin算法[J]. 计算机工程与应用, 2017, 53(4): 39-44.
[12]	范洪博，史舒鹏，张晶. 改进的AAC多模式实时匹配算法[J]. 计算机工程与应用, 2017, 53(3): 68-73.
[13]	李莉1，江育娥1，林劼1，江秉华2. 基于KMP算法的改进算法KMPP[J]. 计算机工程与应用, 2016, 52(8): 33-37.
[14]	张玉叶1，王颖颖1，王春歆2，彭海军1. 分析参数相关和时序特征的飞行动作识别方法[J]. 计算机工程与应用, 2016, 52(5): 246-249.
[15]	孙培双，韩其睿. 彩色图像最优拼接线的改进算法研究[J]. 计算机工程与应用, 2016, 52(21): 218-221.