基于DFA结构的高速并行正则表达式匹配算法

• 作者: 兰巨龙 李玉峰 李鲲鹏
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 正则表达式 确定有限自动机 访问概率 前端部分 后端部分 匹配速度
• 年，卷（期）: 2013,（5）
• 所属期刊栏目: 软件与数据库技术
• 页码范围: 1050-1053
• 页数: 4页
• 分类号: TP393
• 字数: 4538字
• 语种: 中文

摘要

针对正则表达式匹配速度低的问题,提出一种基于DFA结构的并行匹配算法.正则表达式匹配过程中,DFA的一部分状态访问次数多而另一部分状态访问次数少.因此,建立数学模型,应用马尔科夫链求解各个状态的访问概率,从而将DFA的状态分成前端和后端两个部分.通过多个前端部分共用一个后端部分的方法实现多个数据流的并行处理,达到了提高匹配速度的目的.算法分析与实验表明在多消耗60％-80％的存储空间时,能够提高4.2-4.6倍的匹配速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	兰巨龙		217	1088	16.0	22.0
2	李玉峰		38	226	9.0	13.0
3	李鲲鹏		3	14	3.0	3.0