Call for Papers
About the Journal
Editorial Board
Publication Ethics
Instructions for Authors
Announcements
Current Issue
Back Issues
Search for Articles
Categories
Search for Articles
 

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, 2073 View

 
 
ⓒ Copyright 2010 KIISE – All Rights Reserved.    
Korean Institute of Information Scientists and Engineers (KIISE)   #401 Meorijae Bldg., 984-1 Bangbae 3-dong, Seo-cho-gu, Seoul 137-849, Korea
Phone: +82-2-588-9240    Fax: +82-2-521-1352    Homepage: http://jcse.kiise.org    Email: office@kiise.org