基于膨胀系数的正则表达式分组算法

doi:10.3969/j.issn.1006-2475.2014.07.029

计算机与现代化

基于膨胀系数的正则表达式分组算法

(1.重庆大学计算机学院，重庆 400030; 2.重庆大学信息与网络管理中心，重庆 400030; 3.重庆大学软件学院，重庆 401331）

收稿日期:2014-03-10 出版日期:2014-07-16 发布日期:2014-07-17
作者简介:王美阳(1985-),男,江西上饶人,重庆大学计算机学院硕士研究生，研究方向：网络安全，下一代互联网; 唐学文(1955-),男,重庆大学信息与网络管理中心高级工程师,研究方向：网络技术与信息安全; 杨正益(1979-),男,重庆大学软件学院讲师，博士,研究方向：计算机软件与智能控制，程序性能优化。
基金资助:
国家自然科学基金资助项目（51105396）

Regular Expression Grouping Algorithm Based on Expansion Coefficient

(1. School of Computer Science, Chongqing University, Chongqing 400030, China;
2. Information and Campus Network Management Center, Chongqing University, Chongqing 400030, China;
3. School of Software, Chongqing University, Chongqing 401331, China)

Received:2014-03-10 Online:2014-07-16 Published:2014-07-17

摘要/Abstract

摘要： 确定性有限自动机(Deterministic Finite Automata, DFA)匹配速度远快于非确定性有限状态自动机(Non-deterministic Finite state Automata, NFA)，但大量正则表达式转换为DFA时会引起状态爆炸而占用巨大的存储空间。首先定义膨胀系数(Expansion Coefficient, EC)来描述正则表达式的膨胀特性，然后在膨胀系数这一概念基础上，提出一种高效的分组算法——IGA(Improved Grouping Algorithm)算法对正则表达式进行有效分组，将容易引起状态爆炸的正则表达式相互隔离，从而节省存储空间。实验结果表明，与原有算法相比，在相同分组数目时IGA算法平均能够减少25%的状态数。

关键词: 膨胀系数, 正则表达式, 分组算法, DFA

Abstract: Matching speed of deterministic finite automata (DFA) is far faster than that of the non-deterministic finite state automata (NFA). However, when a large number of regular expressions transform into a DFA, the DFA may consume huge storage space because of state explosion. Firstly, to describe characteristics of the regular expressions, expansion coefficient was defined. Based on the concept of expansion coefficient, a more efficient grouping algorithm which named IGA algorithm was proposed. IGA algorithm isolated those regular expressions which easily lead to state explosion, thus saved storage space. Experimental results show that, compared with the original algorithm, when the number of groups is same to the original one, IGA algorithm could reduce 25 percents of the number of states averagely.

Key words: expansion coefficient, regular expression, grouping algorithm, DFA

中图分类号:

TP393.08

王美阳1，唐学文2，杨正益3. 基于膨胀系数的正则表达式分组算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2014.07.029.

WANG Mei-yang1, TANG Xue-wen2, YANG Zheng-yi3. Regular Expression Grouping Algorithm Based on Expansion Coefficient[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.07.029.

参考文献 16

[1]	姚远,刘鹏,单征,等. 面向存储的正则表达式匹配算法综述[J]. 计算机应用, 2009,29(12):3171-3173.
[2]	邓凯元,姜磊. 正则表达式匹配引擎性能分析[J]. 计算机与现代化, 2011(7):105-107.
[3]	Kumar S, Dharmapurikar S, Yu Fang, et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection[C]// Proceedings of the 2006 ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. 2006:339-350.
[4]	Kumar S, Turner J, Williams J. Advanced algorithms for fast and scalable deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2006:81-92.
[5]	Ficara D, Giordano S, Procissi G, et al. An improved DFA for fast regular expression matching[J]. Computer Communication Review, 2008,38(5):29-40.
[6]	Smith R, Estan C, Jha S. XFA: Faster signature matching with extended automata[C]// Proceedings of the 2008 IEEE Symposium on Security and Privacy. 2008:187-201.
[7]	Yu Fang, Chen Zhifeng, Diao Yanlei, et al. Fast and memory-efficient regular expression matching for deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2006:93-102.
[8]	Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection[C]// Proceedings of the 2007 ACM Conference on Emerging Network Experiment and Technology. 2007.
[9]	李鲲鹏,兰巨龙,李印海. 基于Bloom filter的高效正则表达式匹配算法[J]. 计算机应用研究, 2012,29(3):950-954.
[10]	徐乾,鄂跃鹏,葛敬国,等. 深度包检测中一种高效的正则表达式压缩算法[J]. 软件学报, 2009,20(8):2214-2226.
[11]	王磊,陈曙晖,苏金树,等. 深度报文检测中基于GPU的正则表达式匹配引擎[J]. 计算机应用研究, 2010,27(11):4324-4327.
[12]	吴鸿伟,郭东辉,庄进发,等. 基于多GPU的正则表达式匹配技术[J]. 华中科技大学学报(自然科学版), 2013,41(1):51-55.
[13]	Mitra A, Najjar W, Bhuyan L. Compiling PCRE to FPGA for accelerating SNORT IDS[C]// Proceedings of the 2007 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2007:127-136.
[14]	Lee J, Hwang S H, Park N. A high performance NIDS using FPGA-based regular expression matching[C]// Proceedings of the 2007 ACM Symposium on Applied Computing. 2007:1187-1191.
[15]	Dan Lo C, Tai Yi-Gang, Psarris K. Hardware implementation for network intrusion detection rules with regular expression support[C]// Proceedings of the 2008 ACM Symposium on Applied Computing. 2008:1535-1539.
[16]	唐球,姜磊,谭建龙,等. FPGA实现的正则表达式匹配性能分析[J]. 小型微型计算机系统, 2012,33(11):2405-2409.

基于膨胀系数的正则表达式分组算法

Regular Expression Grouping Algorithm Based on Expansion Coefficient

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 16

相关文章 7

编辑推荐

Metrics

本文评价

[1]	夏琨1，丁波1，刘俊1，刘子豪1，林亮成2. 基于内容分析的网络协议指纹识别[J]. 计算机与现代化, 2018, 0(05): 121-.
[2]	刘萍. 计算SKY的预排序分组算法[J]. 计算机与现代化, 2014, 0(2): 69-72.
[3]	邓凯元姜磊. 正则表达式匹配引擎性能分析[J]. 计算机与现代化, 2011, 7(7): 105-107,.
[4]	周冬初;鞠凤娟;郭东珲 . 基于Struts2框架校验数据及整合正则表达式的实现方法[J]. 计算机与现代化, 2011, 1(1): 85-3.
[5]	常捷. 利用CLR实现SQL Server 2005复杂字符串格式的验证[J]. 计算机与现代化, 2010, 1(10): 186-188.
[6]	苏秀芝;楼新远. 正则表达式与XML配置文件相结合的数据提取[J]. 计算机与现代化, 2009, 169(9): 30-31.
[7]	孙勤红;朱颖文. 正则表达式在计算机类教材知识点提取的应用[J]. 计算机与现代化, 2009, 1(7): 111-112,.