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

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

Efficient regular expression matching algorithm based on Bloom filter

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.