Abstract: In order to analyze and evaluate the existed regular expression matching algorithms, it implements them such as DFA, D2FA, CD2FA, mDFA and XFA, and conducts extensive experiments on short rules to evaluate the performance of these algorithms. Experimental results show that compared with mDFA, XFA achieves 84.9%~89.9% memory reduction; XFA only increases 38.9%~174.6% matching times in comparison with mDFA; when the number of rules increases by 8 times, mDFA increases 64 times memory space, while XFA only increases 16 times memory space and increases 61.3% matching time, which demonstrates that XFA has good scalability in terms of memory requirements and matching efficiency.

Key words: regular expression matching, deterministic finite automaton, extended finite automaton, performance evaluation

摘要： 为对现有的高性能正则表达式匹配算法进行综合比较与分析，实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法，采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明，在存储空间方面，与mDFA相比，XFA的存储空间减少84.9%~89.9%；在匹配效率方面，与mDFA相比，XFA的匹配时间增加了38.9%~174.6%；XFA在存储空间和匹配效率上具有良好的可伸缩性，即当规则数增加到8倍时，mDFA的存储空间增长了64倍，而XFA的存储空间仅增加了16倍，匹配时间仅增加了61.3%。

关键词: 正则表达式匹配, 确定有限自动机, 扩展有限自动机, 性能评估

CLC Number: 

• N945