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

Evaluation of High-performance Regular Expression Matching Algorithms

作　　者：金军航[1] 张大方[1,2] 黄昆[2] 

机构地区：[1]湖南大学软件学院,长沙410082 [2]湖南大学计算机与通信学院,长沙410082

出　　处：《计算机工程》2010年第19期269-271,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60673155;90718008)

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

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

分 类 号：N945[自然科学总论—系统科学]