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

摘要

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