基于参数设定的正则表达式匹配算法

• 作者: 周金治 康春香 邓悄
• 来源期刊: 江苏大学学报（自然科学版）
• 学科: 工学
• 关键词: 正则表达式 确定有限自动机 互斥性 多模式匹配 歧义匹配
• 年，卷（期）: 2016,（2）
• 页码范围: 194-200
• 页数: 7页
• 分类号: TP301
• 字数: 4773字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-7775.2016.02.012

摘要

为了解决现有正则表达式匹配算法在时间复杂度与空间复杂之间的平衡问题，提出一种通过参数动态设定的确定有限自动机（dynamic parameters DFA，DPDFA）的正则表达式匹配算法。首先对现有典型正则表达式匹配算法进行性能分析，指出它们在内存占用、规则匹配时间、可扩展性方面存在的不足。然后给出 DPDFA 算法的设计思想：先设定组合后状态数上限，分离组合表达式之间的互斥性，从而降低内存占用；再设定状态数增长率参数，将表达式进行切片，隔离状态数膨胀片段，降低它们之间的歧义匹配，从而节约匹配时间。试验结果表明，DPDFA 算法在时间复杂度方面优于 D2 FA 约23％，在空间复杂度方面优于 mDFA 约43％，在拓展性方面优于 XFA 近260％，整体匹配效率方面也优于其他算法。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周金治	西南科技大学信息工程学院	48	194	8.0	10.0
5	康春香	西南科技大学信息工程学院	2	9	1.0	2.0
9	邓悄	西南科技大学信息工程学院	2	4	1.0	2.0