基于Bloom filter的高效正则表达式匹配算法

• 作者: 兰巨龙 李印海 李鲲鹏
• 来源期刊: 计算机应用研究
• 关键词: 正则表达式 确定有限自动机 布鲁姆过滤器 比特向量 确定字符串 匹配概率 匹配速率
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 软件技术研究
• 页码范围: 950-954
• 分类号: TP393.08
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2012.03.042

摘要

针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法.该算法将正则表达式中的每个确定字符串组成DFA的一个状态,添加比特向量完成匹配过程,并且在一次状态转移中根据确定字符串的匹配结果达到处理多个字符的目的.实验分析表明该算法有效降低了DFA状态的膨胀,提高了匹配速率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	兰巨龙		217	1088	16.0	22.0
2	李印海		12	113	6.0	10.0
3	李鲲鹏		3	14	3.0	3.0