基于DFA结构的高速并行正则表达式匹配算法  

Parallel Architecture for High Throughput DFA-based Regular Expression Matching Algorithm

作　　者：李鲲鹏[1] 兰巨龙[1] 李玉峰[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《小型微型计算机系统》2013年第5期1050-1053,共4页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2012CB315901)资助

摘　　要：针对正则表达式匹配速度低的问题,提出一种基于DFA结构的并行匹配算法.正则表达式匹配过程中,DFA的一部分状态访问次数多而另一部分状态访问次数少.因此,建立数学模型,应用马尔科夫链求解各个状态的访问概率,从而将DFA的状态分成前端和后端两个部分.通过多个前端部分共用一个后端部分的方法实现多个数据流的并行处理,达到了提高匹配速度的目的.算法分析与实验表明在多消耗60%-80%的存储空间时,能够提高4.2-4.6倍的匹配速度.Regular expression matching technology has a problem of low throughput, so a parallel architecture based on DFA was pres- ented. From the fact that some states of DFA are visited frequently but others rarely in the process of regular expression matching, a mathematical model and Markov chain were introduced to calculate the access probability of each state. So the DFA was partitioned into head DFA and tail DFA, and variable head DFA share a tail DFA in order to process multi-flows simultaneity. The result of simulation shows the algorithm can achieve 4.2-4.6 times matching speed in a condition of extra 60%-80% times memory.

关 键 词：正则表达式 确定有限自动机 访问概率 前端部分 后端部分 匹配速度 

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