一种基于FPGA压缩DFA的高速正则表达式匹配算法
Regular Expression Matching Algorithm of Compressing DFA Based on FPGA作者机构:湖南理工学院计算机学院 中国科学院信息工程研究所
出 版 物:《电子技术(上海)》 (Electronic Technology)
年 卷 期:2014年第41卷第8期
页 面:21-24,14页
学科分类:08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
主 题:正则表达式 模式匹配 游程编码 自动机 现场可编程阵列
摘 要:正则表达式匹配技术在网络应用中面临两方面的制约,一方面,复杂或大规模规则导致DFA存储空间急剧膨胀,现有的内存容量难以支撑;另一方面,传统计算机架构的DFA处理能力有限,很难满足高速网络流的线速处理需求。因此,提出一种基于FPGA使用改进游程编码压缩DFA的高速正则表达式匹配算法。实现了基于改进游程编码的DFA引擎架构、分组存储与多路并行比较器技术。该算法不仅具有游程编码的压缩效果,而且压缩后的DFA实现一次状态转移只需2个时钟周期。