%0 Journal Article
%T 基于多字符dfa的高速正则表达式匹配算法
%A 贺炜
%A 郭云飞
%A 莫涵
%A 扈红超
%J 计算机应用
%D 2013
%X ？基于确定性有限自动机(dfa)的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈。为提升处理速率，提出一种单周期处理多字符的匹配算法mc-dfa，该算法基于dfa实现，支持匹配位置的精确定位。mc-dfa将传统dfa中的单字符跳转合并为多字符跳转，实现了单周期处理多个输入字符。通过状态转移矩阵二阶压缩算法，mc-dfa分别对矩阵行内以及行间冗余进行消除，减少了内存使用。300条规则下，单周期处理8字符时，mc-dfa吞吐率能够达到7.88gb/s，内存占用小于6mb，预处理时间为19.24s。实验结果表明，mc-dfa能够有效提升系统吞吐率，并且保证内存占用在可接受范围之内，性能优于现有正则表达式匹配算法。
%K 正则表达式
%K 高速
%K 多字符
%K 精确定位
%K 矩阵压缩
%U http://www.joca.cn/CN/abstract/abstract16627.shtml