|
|
1.
基于多字符DFA的高速正则表达式匹配算法
贺炜 郭云飞 莫涵 扈红超
计算机应用
2013, 33 (08):
2370-2374.
基于确定性有限自动机(DFA)的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈。为提升处理速率，提出一种单周期处理多字符的匹配算法MC-DFA，该算法基于DFA实现，支持匹配位置的精确定位。MC-DFA将传统DFA中的单字符跳转合并为多字符跳转，实现了单周期处理多个输入字符。通过状态转移矩阵二阶压缩算法，MC-DFA分别对矩阵行内以及行间冗余进行消除，减少了内存使用。300条规则下，单周期处理8字符时，MC-DFA吞吐率能够达到7.88Gb/s，内存占用小于6MB，预处理时间为19.24s。实验结果表明，MC-DFA能够有效提升系统吞吐率，并且保证内存占用在可接受范围之内，性能优于现有正则表达式匹配算法。
相关文章 |
多维度评价
|
|
