面向网络流的自适应正则表达式分组匹配算法

针对当前的多正则表达式匹配算法占用较大的系统资源,且吞吐量较低的问题,在分析典型的正则表达式匹配算法的基础上,提出了一种自适应的多正则表达式分组匹配算法.该算法通过对正则表达式进行高效分组,将相互之间存在交叠且容易引起状态数指数增长的表达式相互隔离；将每个分组构造为一个确定性有限自动机(DFA),按匹配概率大小建立伸展树进行调度.仿真结果表明,该算法不仅大大节省了存储空间,而且吞吐量提高了大约3倍.

An Adaptive Matching Algorithm for Regular Expression Grouping in Network Traffic

In view of current multiple regular expressions matching algorithms consume too large system resource,but provide low throughput,a new regular expression matching algorithm for network context is proposed through analyzing typical regular expression matching algorithms.The algorithm separates expressions that have interaction and could cause exponential increase in the number of states,and assigns them into different groups.Then a DFA is constructed for each group,and these DFAs are placed on the splay tree to schedule by their matching probabilities.Simulation results show that the proposed algorithm not only could save more memory space,but also could provide about three times higher throughput.