摘要：

分析现有方法处理状态爆炸的局限性，将条件函数和位图结构引入自动机，提出一种位图移位有限自动机(Bs-FA)，并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况，仅需引入较小位图空间，就能使整个自动机内存空间明显减少。在实际规则集上评估，并与现有方法进行比较，说明该自动机的应用价值。

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

Abstract:

The limitation of existing method is analysed, Bitmap shift 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.

Key words: Deterministic Finite Automaton(DFA), deep packet inspection, regular expression

中图分类号: 

• TP311