基于多字符dfa的高速正则表达式匹配算法

？基于确定性有限自动机(dfa)的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈。为提升处理速率，提出一种单周期处理多字符的匹配算法mc-dfa，该算法基于dfa实现，支持匹配位置的精确定位。mc-dfa将传统dfa中的单字符跳转合并为多字符跳转，实现了单周期处理多个输入字符。通过状态转移矩阵二阶压缩算法，mc-dfa分别对矩阵行内以及行间冗余进行消除，减少了内存使用。300条规则下，单周期处理8字符时，mc-dfa吞吐率能够达到7.88gb/s，内存占用小于6mb，预处理时间为19.24s。实验结果表明，mc-dfa能够有效提升系统吞吐率，并且保证内存占用在可接受范围之内，性能优于现有正则表达式匹配算法。