基于FPGA改进电路的高性能正则表达式匹配算法

来源：计算机应用杂志2016年第4期北京时间：

作者：卓艳男, 刘强, 姜磊, 戴琼

单位：1. 东北石油大学 电子科学学院, 黑龙江 大庆 163318;2. 中国科学院 信息工程研究所, 北京 100093

摘要：针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。

关键词：正则表达式,现场可编程门阵列,模式匹配,确定性有穷状态自动机

基金资助：国家自然科学基金资助项目(51574087)。