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

Regular expression matching algorithm based on parameters setting

作　　者：周金治[1,2] 邓悄 康春香[1,2] 

机构地区：[1]西南科技大学信息工程学院,四川绵阳621010 [2]西南科技大学特殊环境机器人技术四川省重点实验室,四川绵阳621010 [3]四川通信科研规划设计有限责任公司,四川成都610041

出　　处：《江苏大学学报（自然科学版）》2016年第2期194-200,共7页Journal of Jiangsu University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60932005);特殊环境机器人技术四川省重点实验室基金资助项目(13ZXTK07)

摘　　要：为了解决现有正则表达式匹配算法在时间复杂度与空间复杂之间的平衡问题,提出一种通过参数动态设定的确定有限自动机(dynamic parameters DFA,DPDFA)的正则表达式匹配算法.首先对现有典型正则表达式匹配算法进行性能分析,指出它们在内存占用、规则匹配时间、可扩展性方面存在的不足.然后给出DPDFA算法的设计思想:先设定组合后状态数上限,分离组合表达式之间的互斥性,从而降低内存占用;再设定状态数增长率参数,将表达式进行切片,隔离状态数膨胀片段,降低它们之间的歧义匹配,从而节约匹配时间.试验结果表明,DPDFA算法在时间复杂度方面优于D2FA约23%,在空间复杂度方面优于m DFA约43%,在拓展性方面优于XFA近260%,整体匹配效率方面也优于其他算法.To well balance time complexity and space complexity in regular expression,a matching algorithm for regular expression of deterministic finite automata was proposed through dynamic parameters DFA（ DPDFA）. The performance of current typical matching algorithm of regular expression was analyzed,and the insufficiencies in CPU memory occupation,matching time and expandability were indicated to give the design concept of DPDFA. The top-limit of state number after combination was set up,and the exclusivity among the combination expressions was separated to reduce the CPU occupation.The growth rate parameter of state number was set up,and the expression was sliced up. The expanding section of state number was isolated to reduce matching ambiguity and matching time. The experimental results show that the DPDFA algorithm is at least 23% overmatching than D2 FA in time complexity with43% overmatching than m DFA in space complexity and 260% overmatching than XFA in expandability.It is briefly more superior to other algorithm in overall matching efficiency.

关 键 词：正则表达式 确定有限自动机 互斥性 多模式匹配 歧义匹配 

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