JCSE, vol. 8, no. 2, pp.78-86, 2014

DOI: http://dx.doi.org/10.5626/JCSE.2014.8.2.78

A Regular Expression Matching Algorithm Based on High-Efficient Finite Automaton

Jianhua Wang, Lianglun Cheng, and Jun Liu
Faculty of Automation, Guangdong University of Technology

Abstract: Aiming to solve the problems of high memory access and big storage space and long matching time in the regular expression matching of extended finite automaton (XFA), a new regular expression matching algorithm based on high-efficient finite automaton is presented in this paper. The basic idea of the new algorithm is that some extra judging instruments are added at the starting state in order to reduce any unnecessary transition paths as well as to eliminate any unnecessary state transitions. Consequently, the problems of high memory access consumption and big storage space and long matching time during the regular expression matching process of XFA can be efficiently improved. The simulation results convey that our proposed scheme can lower approximately 40% memory access, save about 45% storage space consumption, and reduce about 12% matching time during the same regular expression matching process compared with XFA, but without degrading the matching quality.

Keyword: Regular expression; Matching algorithm; High-efficient; Deterministic finite automaton

Full Paper:   233 Downloads, 2301 View