面向网络流的正则表达式匹配改进算法

Improved algorithm of regular expression matching for network flow

提出了基于猜测-分组-检验的面向网络流正则表达式匹配算法。首先对出现概率高的部分特征子块进行搜索并把特征子块进行分组后DFA转换,然后对输出进行猜测匹配。若匹配成功,则使用NFA进行完整验证。实验表明,该方法能够在减少内存使用和资源占用率的同时,具有极高的匹配效率。

On the basis of analyzing the classic regular expression algorithm, this paper proposes a novel network-oriented reg- ular expression matching algorithm based on guess-grouping-inspection. Firstly, the algorithm searches the characteristic sub-blocks with high probability of occurrence, divides these characteristic sub-blocks into groups, and carries out DFA conversion. Then, it performs the guess match algorithm to the output. If the match is successfuL, it will use NFA to carry out complete verification. The experiment results show that this method could not only reduce the memory consumption and resource consumption rate, but al so have high matching efficiency.