TCS-TR-A-14-73

Date: Mon May 26 21:11:02 2014

Title: Fast Regular Expression Matching Using Dual Glushkov NFA

Authors: Ryutaro Kurai, Norihito Yasuda, Hiroki Arimura, Shinobu Nagayama, and Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: minato@ist.hokudai.ac.jp

Abstract. This paper presents a new regular expression matching method by using Dual Glushkov NFA. Dual Glushkov NFA is the variant of Glushkov NFA, and it has the strong property that all the outgoing edges to a state of it have the same labels. We propose the new matching method Look Ahead Matching that suited to Dual Glushkov NFA structure. This method executes NFA simulation with reading two input characters at the one time. We use information of next character to narrow down the active states on NFA simulation. It costs additional working memory to apply Look Ahead Matching to ordinal Thompson NFA. However, we can use this method with no additional memory space if use it with Dual Glushkov NFA. Experiments also indicate that the combination of Dual Glushkov NFA with Look Ahead Matching outperforms the other methods on NFAs converted from practical regular expressions.