检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (19): 269-271.doi: 10.3969/j.issn.1000-3428.2010.19.096

• 开发研究与设计技术 • 上一篇    下一篇

高性能正则表达式匹配算法评估

金军航a，张大方a,b，黄 昆b   

  1. (湖南大学 a. 软件学院；b. 计算机与通信学院，长沙 410082)
  • 出版日期:2010-10-05 发布日期:2010-09-27
  • 作者简介:金军航(1985－)，男，硕士研究生，主研方向：网络安全； 张大方，教授、博士、博士生导师；黄 昆，博士研究生
  • 基金项目:
    国家自然科学基金资助项目(60673155, 90718008)

Evaluation of High-performance Regular Expression Matching Algorithms

JIN Jun-hanga, ZHANG Da-fanga,b, HUANG Kunb   

  1. (a. School of Software; b. College of Computer and Communication, Hunan University, Changsha 410082, China)
  • Online:2010-10-05 Published:2010-09-27

PDF

2988

被引次数

11 | 2

摘要： 为对现有的高性能正则表达式匹配算法进行综合比较与分析，实现诸如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%。

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

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

中图分类号: