Regular Expression Grouping Algorithm Based on Graph Partitioning

doi:10.3969/j.issn.1000-3428.2012.18.037

Computer Engineering ›› 2012, Vol. 38 ›› Issue (18): 137-139. doi: 10.3969/j.issn.1000-3428.2012.18.037

• Networks and Communications • Previous Articles Next Articles

Regular Expression Grouping Algorithm Based on Graph Partitioning

WEI Qiang, LI Yun-zhao, CHU Yan-jie

(Key Laboratory of Blind Signals Processing, Chengdu 610041, China)

Received:2011-11-14 Revised:2012-01-03 Online:2012-09-20 Published:2012-09-18

基于图划分的正则表达式分组算法

魏强，李云照，褚衍杰

(盲信号处理重点实验室，成都 610041)

作者简介:魏强(1987－)，男，硕士研究生，主研方向：模式匹配，人工智能，网络数据处理；李云照，博士；褚衍杰，博士研究生

Abstract

Abstract: This paper focuses on the explosion in states when many regular expressions are grouped together into a single Deterministic Finite Automaton(DFA). Based on the original grouping algorithm, an improved algorithm is proposed by introducing graph partitioning. The proposed algorithm can reduce 30% states number on average when group number is same to the original one, and sometimes gets fewer groups. Experimental results show that the proposed algorithm can reduce the complexity of matching algorithm effectively.

Key words: deep packet detection, pattern matching, regular expression, Deterministic Finite Automaton(DFA), grouping algorithm, graph partitioning

摘要： 针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题，借鉴图划分的思想，提出一种改进的分组算法。与原分组算法相比，该算法在分组数相同时状态数平均减少30%，在某些情况下能获得更少的分组数。实验结果证明，该算法能有效降低匹配算法的复杂度。

关键词: 深度包检测, 模式匹配, 正则表达式, 确定型有限自动机, 分组算法, 图划分

CLC Number:

TP393

WEI Jiang, LI Yun-Zhao, CHU Yan-Jie. Regular Expression Grouping Algorithm Based on Graph Partitioning[J]. Computer Engineering, 2012, 38(18): 137-139.

魏强, 李云照, 褚衍杰. 基于图划分的正则表达式分组算法[J]. 计算机工程, 2012, 38(18): 137-139.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2012.18.037

http://www.ecice06.com/EN/Y2012/V38/I18/137

References

[1]Kumar S, Dharmapurikar S, Yu Fang, et al. Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection[C]//Proc. of 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Commu- nications. New York, USA: [s. n.], 2006.
[2]Kumar S, Turner J, Williams J. Advanced Algorithms for Fast and Scalable Deep Packet Inspection[C]//Proc. of 2006 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. New York, USA: ACM Press, 2006.
[3]Ficara D, Giordana S, Procissig G, et al. An Improved DFA for Fast Regular Expression Matching[J]. Computer Communication Review, 2008, 38(5): 29-40.
[4]Becchi M, Crowley P. A Hybrid Finite Automaton for Practical Deep Packet Inspection[C]//Proc. of the International Conference on Emerging Networking Experiments and Technologies. New York, USA: [s. n.], 2007.
[5]刘鹏, 姚远, 邰铭, 等. 一种高效匹配PCRE的扩展自动机[J]. 计算机工程, 2010, 36(12): 39-42.
[6]Becchi M, Crowley P. An Improved Algorithm to Accelerate Regular Expression Evaluation[C]//Proc. of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems. New York, USA: ACM Press, 2007.
[7]Kong S, Smith R, Estan C. Efficient Signature Matching with Multiple Alphabet Compression Tables[C]//Proc. of the 4th International Conference on Security and Privacy in Communication. New York, USA: [s. n.], 2008.
[8]Yu Fang, Chen Zhifeng, Diao Yanlei, et al. Fast and Memory-efficient Regular Expression Matching for Deep Packet Inspection[C]//Proc. of 2006 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. San Jose, USA: ACM Press, 2006.
[9]Jain S, Swamy C, Balaji K. Greedy Algorithms for k-way Graph Partitioning[C]//Proc. of the 6th International Conference on Advanced Computing. Pune, India: [s. n.], 1998.

[1]	LIU Zhiguo, SONG Guangyue, CAI Wenzhu, LIU Qingli. Frame Location Method of Unknown Network Protocol Based on TextRank Algorithm [J]. Computer Engineering, 2020, 46(7): 179-184.
[2]	WANG Xiang,LU Yuhai,MA Wei,LIU Yanbing. A Regular Expression Matching Method for DFA State Explosion [J]. Computer Engineering, 2019, 45(4): 148-156.
[3]	WEI Changbao,YAO Ruxian. Improved Algorithm of Graph Partitioning Structure Detection Based on Minimum Description Length [J]. Computer Engineering, 2016, 42(1): 231-236,242.
[4]	JIN Ge,XUE Zhi,QI Kaiyue. Main Boot Record Rootkit Modeling and Its Static Detection Method [J]. Computer Engineering, 2015, 41(7): 184-189.
[5]	WEI Changbao,YAO Ruxian. Improved Algorithm of Graph Partitioning Change Detection Based on Minimum Description Length [J]. Computer Engineering, 2015, 41(7): 274-279,284.
[6]	WU Xujing,XU Yong,ZHANG Yanan. Key Pre-distribution Scheme of Wireless Sensor Network Based on Fingerprint Pattern Matching [J]. Computer Engineering, 2015, 41(3): 106-109.
[7]	ZHANG Zhichang,CHEN Songyi,LIU Xin,MA Huifang. Hyponymy Relation Validation Combined with Context and Brown Clustering Feature [J]. Computer Engineering, 2015, 41(2): 145-150.
[8]	CHEN Wei,TENG Hongshun. Efficient Single Pattern Matching Algorithm Based on BM Window Competition [J]. Computer Engineering, 2015, 41(12): 144-149.
[9]	LIU Chunhui,HUANG Yu,SONG Qi. An Improved AC Multiple Pattern Matching Algorithm [J]. Computer Engineering, 2015, 41(10): 280-285.
[10]	Yiliyaer Dawut,Halidan Abudureyimu,YANG Nana. Research on Multiple Pattern Matching Algorithm for Uyghur [J]. Computer Engineering, 2015, 41(1): 143-149.
[11]	YANG Jia-jia,JIANG La-lin,JIANG Lei,DAI Qiong,TAN Jian-long. Regular Expression Compression Algorithm Based on Cluster Clustering and Runlength Encoding [J]. Computer Engineering, 2014, 40(8): 282-287,292.
[12]	WANG Zhen, LI Ren-fa, LI Yan-biao, TIAN Zheng. A Parallel Multiple Pattern Matching Algorithm on Chinese/English Mixing [J]. Computer Engineering, 2014, 40(4): 318-320.
[13]	WANG Yan-xia, JIANG Yan-xia, WANG Ya-gang, LI Ye. Research and Improvement of BMH2C Single Pattern Matching Algorithm [J]. Computer Engineering, 2014, 40(3): 298-302.
[14]	HOU Zhengfeng,ZHANG Hao,ZHANG Na. Chinese Webpage Encoding Identification Algorithm Based on Word Frequency Distribution [J]. Computer Engineering, 2014, 40(12): 199-204.
[15]	SONG Hui, SHI Nan-sheng. Comment Object Extraction Based on Pattern Matching and Semi-supervised Learning [J]. Computer Engineering, 2013, 39(10): 221-226.

Please choose a citation manager

Content to export

Regular Expression Grouping Algorithm Based on Graph Partitioning

基于图划分的正则表达式分组算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

模态框（Modal）标题

Please choose a citation manager

Content to export

Regular Expression Grouping Algorithm Based on Graph Partitioning

基于图划分的正则表达式分组算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments