基于正则表达式的DFA拆分算法研究  

Research of Deterministic Finite Automaton Split Algorithm Based on Regular Expressions

作　　者：翟丽杰[1] 段海生[1] 

机构地区：[1]渭南师范学院物理与电气工程学院,渭南714000

出　　处：《计算机与数字工程》2012年第8期3-4,28,共3页Computer & Digital Engineering

基　　金：陕西省教育厅科学研究项目计划(编号:12JK0672);渭南师范学院研究生项目计划(编号:11YKZ023)资助

摘　　要：深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表:间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。Traditional deep packet inspection exploited a simple string matching technology to match packets with a fixed string,regular expressions can provide greater expressive power and better flexibility,but the number of states have multiplied greatly and led to huge storage host by complex structure of regular expressions.DFA split algorithm is proposed that DFA conversion tables should be spitted into three tables： an indirect index table,a conversion output table,a direct conversion table.Experiment results show that the DFA split algorithm greatly reduces the space occupied and realizes DFA compression store.

关 键 词：深度包检测 正则表达式 DFA拆分 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]