Prague Stringology Conference 2014
Ryutaro Kurai, Norihito Yasuda, Hiroki Arimura, Shinobu Nagayama and Shin-ichi Minato
Fast Regular Expression Matching Based On Dual Glushkov NFA
| 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 transitions 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 symbols at the one time. We use information of next symbol 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |