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

Efficient regular expression matching algorithm based on Bloom filter

作　　者：李鲲鹏[1] 兰巨龙[1] 李印海[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机应用研究》2012年第3期950-954,共5页Application Research of Computers

基　　金：国家"863"计划资助项目(2009AA01A346)

摘　　要：针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法。该算法将正则表达式中的每个确定字符串组成DFA的一个状态,添加比特向量完成匹配过程,并且在一次状态转移中根据确定字符串的匹配结果达到处理多个字符的目的。实验分析表明该算法有效降低了DFA状态的膨胀,提高了匹配速率。Regular expression matching technology based on DFA requires prohibitively large amounts of memory and process only one character per transition. So this paper presented an efficient regular expression matching algorithm based on Bloom filter. Literal characters of regular expression were regards as a state of DFA, and introduced bit vector to realize the matching process. Then it could process variable characters per transition based on the result of literal characters matching. The result of simulation shows the algorithm not only reduces the required memory of DFA, but also increases the matching speed.

关 键 词：正则表达式 确定有限自动机 布鲁姆过滤器 比特向量 确定字符串 匹配概率 匹配速率 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]