一种高效匹配PCRE的扩展自动机  

Efficient Extended Automaton Matching Perl-Compatible Regular Expressions

作　　者：刘鹏[1] 姚远[1] 邰铭[1] 张铮[1] 

机构地区：[1]解放军信息工程大学信息工程学院,郑州450002

出　　处：《计算机工程》2010年第12期39-42,共4页Computer Engineering

基　　金：国家"863"计划基金资助项目(2006AA01Z408)

摘　　要：分析现有方法处理状态爆炸的局限性,将条件函数和位图结构引入自动机,提出一种位图移位有限自动机(Bs-FA),并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况,仅需引入较小位图空间,就能使整个自动机内存空间明显减少。在实际规则集上评估,并与现有方法进行比较,说明该自动机的应用价值。The limitation of existing method is analysed, Bitmap shit~ Finite Automaton（Bs-FA） is proposed by introducing condition function and bitmap structure, and the general method is provided to create Bs-FA from regular expression. In the condition of class of characters which overlaps with prefix, additional less space can reduce the memory storage remarkably. Bs-FA is evaluated on current rule sets and it has an important application value by comparing with recent methods.

关 键 词：确定的有限自动机 深度包检测 正则表达式 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]