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

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2370-2374.

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

贺炜,郭云飞,莫涵,扈红超

国家数字交换系统工程技术研究中心，郑州 450002

收稿日期:2013-02-20 修回日期:2013-03-12 发布日期:2013-09-11 出版日期:2013-08-01
通讯作者: 贺炜
作者简介:
贺炜(1988-)，男，山西吕梁人，硕士研究生，主要研究方向：网络安全中的特征匹配;
郭云飞(1963-)，男，河南郑州人，教授，博士生导师，主要研究方向：三网融合;
莫涵(1988-)，女，河南郑州人，硕士研究生，主要研究方向：可重构网络、组播传输;
扈红超(1983-)，男，河南郑州人，研究员，博士，主要研究方向：网络协议分析。
基金资助:
国家科技支撑计划项目;国家863计划项目

Multi-character DFA-based high speed regular expression matching algorithm

HE Wei,GUO Yunfei,MO Han,HU Hongchao

China National Digital Switching System Engineering and Technological R&D Center, Zhengzhou Henan 450002, China

Received:2013-02-20 Revised:2013-03-12 Online:2013-09-11 Published:2013-08-01
Contact: HE Wei

摘要/Abstract

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

关键词: 正则表达式, 高速, 多字符, 精确定位, 矩阵压缩

Abstract: Traditional Deterministic Finite Automata (DFA) based regular expression matching can only process one character per cycle, which is the speed bottleneck. A new algorithm named Multi-Character DFA (MC-DFA) was proposed for high throughput matching and precise positioning. It combined the one character transition in traditional DFA together to handle multi-character processing per cycle. A new transition matrix compress algorithm was also proposed to reduce the redundancy introduced by MC-DFA. The result demonstrates that MC-DFA can improve the throughput efficiently while requiring acceptable memory. For a set of 300 regexes, 8C-DFA obtains a throughput of 7.88Gb/s, memory usage less than 6MB and 19.24s preprocessing time, better than traditional methods.

Key words: regular expression, high throughput, multi-character, precise positioning, matrix compress

中图分类号:

TP393

贺炜郭云飞莫涵扈红超. 基于多字符DFA的高速正则表达式匹配算法[J]. 计算机应用, 2013, 33(08): 2370-2374.

HE Wei GUO Yunfei MO Han HU Hongchao. Multi-character DFA-based high speed regular expression matching algorithm[J]. Journal of Computer Applications, 2013, 33(08): 2370-2374.

[1]	王一帆, 林绍福, 李云江. 基于区块链和零知识证明的高速公路自由流收费方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3741-3750.
[2]	高醇, 王梦灵. 基于特征融合图注意网络的高速公路交通流预测[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3114-3120.
[3]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[4]	席皓哲, 王瑞峰. 基于天线分组的高铁大规模多输入多输出自适应波束赋形方案[J]. 计算机应用, 2019, 39(3): 839-844.
[5]	王思秀, 张蕾, 任艳, 冯长征. 基于自相关增量的载波参数解耦合技术[J]. 计算机应用, 2019, 39(11): 3339-3342.
[6]	常征, 吕勇. 基于正则表达式的海量数据清洗系统[J]. 计算机应用, 2019, 39(10): 2942-2947.
[7]	江治林, 葛利嘉, 邢峰英, 杨勤. 二维空码索引调制算法[J]. 计算机应用, 2018, 38(5): 1458-1462.
[8]	夏浩男, 戴胜华. 基于着色Petri网的无线闭塞中心安全加密[J]. 计算机应用, 2018, 38(12): 3476-3480.
[9]	麦涛涛, 潘晓中, 王亚奇, 苏阳. 基于预定义类的紧凑型正则表达式匹配算法[J]. 计算机应用, 2017, 37(2): 397-401.
[10]	廖勇, 胡异. 高速移动下U型槽的时变信道建模[J]. 计算机应用, 2017, 37(10): 2735-2741.
[11]	俞艺涵, 付钰, 吴晓平. 基于改进正则表达式规则分组的内网行为审计方案[J]. 计算机应用, 2016, 36(8): 2241-2245.
[12]	卓艳男, 刘强, 姜磊, 戴琼. 基于FPGA改进电路的高性能正则表达式匹配算法[J]. 计算机应用, 2016, 36(4): 927-930.
[13]	蒲松, 吕红霞. 基于改进数据包络分析的高速列车开行方案的动态评价[J]. 计算机应用, 2015, 35(5): 1479-1482.
[14]	李凯何松华欧建平. Virtex-5 GTP和Virtex-6 GTX间匹配通信研究及应用[J]. 计算机应用, 2014, 34(2): 325-328.
[15]	周逊曹亚楠张庆伟任智漆自名. 新的太赫兹超高速无线网络媒体访问控制协议[J]. 计算机应用, 2013, 33(11): 3019-3023.