TCS -TR-A-14-73

TCS Technical Report

Fast Regular Expression Matching
Using Dual Glushkov NFA
byRyutaro Kurai, Norihito Yasuda, Hiroki Arimura,
Shinobu Nagayama, and Shin-ichi Minato

Division of Computer Science
Report Series A
May 26, 2014

Hokkaido University

Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7682+81-011-706-7682

Fast Regular Expression Matching
Using Dual Glushkov NFA
Ryutaro Kurai1,2
Norihito Yasuda1
Hiroki Arimura2
3
1,2
Shinobu Nagayama
Shin-ichi Minato
1)

JST ERATO MINATO Discrete Structure Manipulation System Project, Japan
Graduate School of Information Science and Technology, Hokkaido University, Japan3)
Department of Computer and Network Engineering, Hiroshima City University, Japan{kurai,yasuda,minato}@erato.ist.hokudai.ac.jp
arim@ist.hokudai.ac.jp,s_naga@hiroshima-cu.ac.jp
2)

May 26, 2014
Abstract
This paper presents a new regular expression matching method byusing Dual Glushkov NFA. Dual Glushkov NFA is the variant of Glushkov
NFA, and it has the strong property that all the outgoing edges to astate of it have the same labels. We propose the new matching method
Look Ahead Matching that suited to Dual Glushkov NFA structure. Thismethod executes NFA simulation with reading two input characters at theone 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.

1

Introduction

1.1

Background

Regular expression matching is one of the fundamental research topics in computer science [13], since it plays such important role in emerging applications
in large-scale information processing fields, such as: Network Intrusion Detection System (NIDS), Bioinformatics search engines, linguistic vocabulary, andpattern matching in cloud computing [9, 11, 14, 15, 17].

1.2

Problems with previous approaches

For regular expression matching, there are three well-known approaches: backtracking, DFA, and NFA. Among them, backtracking is the most widely used1

in practical applications. However, this approach is so slow if it manipulates
some diﬃcult patterns and texts, like a?n an as pattern and an as text, which
triggers many backtracking on the input text [6]. The deterministic finite automaton (DFA) approach is extremely fast if the input regular expression canbe compiled into a DFA of small size, but it is not practical if a given regularexpression causes the exponential explosion of the number of states.
The Nondeterministic Finite Automaton (NFA) approach can avoid such
explosion in the number of states, and shown to be faster than the naive backtrack approach for the case that the backtracking approach suﬀer from manynear-misses. Unfortunately, NFA approach is not so fast in practice. One of
the major reasons is the cost of maintaining a set of active states; every time
next input letter comes, NFA has to update the all the active states to the next
states or to just discard them. If the number of active states becomes large, theupdating cost will also increase.
We can further classify the NFA into three types; Thompson NFA, Glushkov
NFA and Dual Glushkov NFA. The most popular one is Thompson NFA, whichis easy to construct, and its number of edges and states are constant multiple ofassociated regular expression’s length. Thompson NFA includes many of epsilontransitions. Those transitions make many of active states when we simulate such
NFA.
Glushkov NFA is the other popular NFA. It has strong property that it has
no epsilon transition and its all the incoming edges to a state of Glushkov NFA
have the same labels. Dual Glushkov NFA is a variant of Glushkov NFA, but
has a special feature that is worth our attention. In an opposed manner of the
Glushkov NFA, all the outgoing edges from a state of Dual Glushkov NFA havethe same labels.

1.3

Speed-up methods

We can simulate Glushkov NFA faster than Thompson NFA because of its property that it has no epsilon edge. The property causes less active states. Nevertheless, we have to manipulate amount of active state, and it slows down
matching speed, if we treat complex regular expression. To cope with this problem, we propose a new method Look Ahead Matching.
That is the new matching method that reads two characters of the input
text at one time. We call the first of the two characters the “current character”,
and second one the “next character”. Ordinary matching methods read only
current character, and calculate NFA active states from current active states andthe character. Our method uses the next character to narrow down the active
state size. We set states active only if the states have incoming edge labeled
by first character and outgoing edge labeled by second character. However, fast
matching by two input characters creates large memory demands if we use the
Glushkov NFA. To treat this problem, we employ a Dual Glushkov NFA. The
structure of Dual Glushkov NFA is similar to that of Glushkov NFA, but isbetter suited to building an index of transitions for look ahead matching. We
have to make transitions table for combination of two characters to enable thisnew matching method. We can generate such table without additional space
if we use the above Dual Glushkov NFA’s property. Therefore, we propose the
new look ahead matching method by using Dual Glushkov NFA.

2

1.4

Main Results

In this paper we propose a new matching method created by combining Dual
Glushkov NFA and look ahead matching. Then we compare our proposal against
other methods such as original Thompson NFA, Glushkov NFA, and a combination of Glushkov NFA and look ahead matching. For reference, we also compare our method with NR-grep [10]. In most cases our method is faster thanThompson NFA or Glushkov NFA. Our method is only slightly slower than the
combination of Glushkov NFA and look ahead matching, but it uses far lessmemory.

1.5

Related Works

Many regular expression matching engines use the backtracking approach. They
traverse the syntax tree of a regular expression, and backtrack if they fail tofind a match. Backtracking has a small memory footprint and high throughput for small and simple regular expressions. However, in worst case, it takes
exponential time in the size of the regular expression [6].
Another approach, compiling regular expression has been used from the1970s [2]. Such an algorithm converts a regular expression into an NFA, whichis then converted into a DFA. This intermediate NFA (called Thompson NFA)
has linear size memory in the length of the input regular expression. However,the final subset-constructed DFA takes exponential space in the size of the NFA
and overflows the main memory of even recent computers.
In recent years, NFA evaluation for regular expression matching has been
attracting much attention. Calculations performed on GPU, FPGA, or somespecial hardware can’t use abundant memory, but their calculation speed ismuch faster and concurrency is larger than typical computers. Therefore, using
just the basic approach is adopted in some fields [5, 7]. Cox proposed the NFA
based regular expression library RE2 [1]. For fast evaluation, it caches a DFA
generated from an NFA on the fly. RE2 seems to be the only NFA based librarythat is being used widely; it has guaranteed computation time due to the NFAoriented execution model.
Berry and Sethi popularized Glushkov NFA [3]. Navarro has finely researched Glushkov NFA and its applications [10, 12]. And Brüggemann-Klein
and Wood showed the relationship between Thompson NFA and Glushkov
NFA [4].

1.6

Organization

Sec. 2 briefly introduces regular expression matching, non-deterministic automata, and their evaluation. Sec. 3 presents our methods including preprocessing and runtime methods. Sec. 4 shows the results of computer experiments
on NFA evaluation. Sec. 5 concludes this paper.

3

9

1

A

3

T

8

5

0

10

A

T

11

12

G

A

13

14

A

15

16

7
2

G

4

A

6

Figure 1: T-NFA for R = (AT |GA)((AG|T AA)∗)

2

Preliminaries

2.1

Thompson NFA

The NFA constructed by Thompson’s algorithm for regular expression R iscalled the Thompson NFA (or T-NFA, for short). It precisely handles the language statement Σ∗ L(R), which represents the substring match of R against a
substring of a text.
Formally, T-NFA for R is a 5-tuple NR = (V, Σ, E, I, F ), where V is a set ofstates, Σ is an alphabet of letters, E ⊆ V × Σ ∪ {ε} × V is a set of letter- andε-edges, called the transition relation, I and F ⊆ V are the sets of initial andfinal states respectively. Each edge e in E is called a letter-transition if its label
is a letter c in Σ, and a ε-transition the label is ε. And each edge is described as(s, char, t) ∈ E, in this expression, s and t mean source state and target state.
char is a label of the edge.
The T-NFA NR for R has nested structure associated with the parse tree
for R. Let the length of associated regular expression be m. It has at most 2m
states, and every state has in-degree and out-degree of two or less. Specifically,
state s in V can have at most one letter-transition or two ε-transitions from s.
We show an example of T-NFA when R = (AT |GA)((AG|T AA)∗) in Fig. 1.

2.2

Glushkov NFA

Another popular method of constructing an NFA from a regular expression is
Glushkov’s algorithm [3]. We call the automaton constructed by this method
Glushkov NFA (also known as Position Automata); abbreviated here to G-NFA.
However, G-NFA can also be converted from T-NFA by using the algorithm in
Fig. 4(Brüggemann-Klein and Wood showed in [4]). This algorithm removes
the ε-transitions from T-NFA by canonical rule. For instance, we show the newedges that skip ε-transition by the bold edges in Fig. 2 and the fully converted
G-NFA from T-NFA in Fig. 3. Both examples show NFAs that precisely handle
R = (AT |GA)((AG|T AA)∗).

2.3

G-NFA Properties

G-NFA has some very interesting properties.
• It has no ε-transitions. We call this property ε-free.
• For any state, the state’s incoming edges are labeled by the same character.

4

A
G
G

A

4

T

6

2

11

A
G

13

A

A

A
T

0

A

9
A

T

3

5

7

8
10

1

T

12

14

A

A

15

16

T
T

Figure 2: T-NFA and skip edges of ε-edges
G

A
0

3

T

A

11

5

T

T

G
4

A

13

A
A

A
6
T

12

A

14

A

15

T

Figure 3: G-NFA for R = (AT |GA)((AG|T AA)∗)• It has only one initial state.
• It has one or more final states.
• It’s number of states is m̃ + 1. m̃ is the length of the associated regularexpression, but the number excludes the special symbols like “∗”, “(”, or“+”.
• The number of transitions is m̃2 at worst.

2.4

Dual Glushkov NFA

A variation of G-NFA is Dual Glushkov NFA (also called Dual Position Automata [16]), we call it Dual G-NFA for short. The algorithm that converts
T-NFA into Dual G-NFA (Fig. 7) is similar to the algorithm that converts TNFA into G-NFA (fig. 4).
When we convert T-NFT into G-NFA, we generate a skip edge as follows.
First, we search the path that started by epsilon-path and ended only one
charcter-edge. Then we create skip edge from the start state to the end statefor each such path. The label of new skip edge is taken from the last edge ofthe path.
When we convert T-NFA into Dual G-NFA, we generate a skip edge asfollows. First, we search the path that started only one character-edge andended epsilon-path. Then we create skip edge from the start state to the end

5procedure BuildG-NFA(N = (V, Σ, E, I, F ))V ′ ← ∅, E ′ ← ∅, F ′ ← F!
GlushkovState ← V \s′s′ ,∃s∈V,(s,ε,s′ )∈E

for all s ∈ GlushkovState dofor s′ ∈ Eclose(s) do
if s′ ∈ F thenF ′ ← F ′ ∪ {s′ }end iffor (s′ , char, t) ∈ E do
if char ̸= ε thenE ′ ← E ′ ∪ {(s, char, t)}
end ifend forend forend forreturn (V ′ , Σ, E ′ , I, F ′ )end procedure
procedure Eclose(s ∈ E)
Closure ← {s}for (s, char, t) ∈ E do
if char = ε then
Closure ← Closure ∪ Eclose(t)end ifend forreturn Closure
end procedure

Figure 4: Algorithm Converting T-NFA to G-NFA

6

T
A
T
A

T

3

T

10

12

5

A

A

1

A

T

G

0

14
A

A

2

15
G
A

4

8

7

6

9

A
G

G

11

G

13

16

A

A

Figure 5: T-NFA to Dual G-NFA
T
1

A

3
T

G
7

T

9

G
A

11

G

10
A

T

12
A

A

A
14

A

2

G

A
4
A

Figure 6: Dual G-NFA for R = (AT |GA)((AG|T AA)∗)
state for each such path. The label of new skip edge is taken from the first edgeof the path.
In addition, an original T-NFA has same number of outgoing and incomingedges for all section of T-NFA. In fact, Conjunction, Concatenation, and Kleene
Closure section of T-NFA have same in-degree and out-degree. Because of thisT-NFA’s property, we can consider that above “Dual G-NFA” is dual of “GNFA”.
For instance, we show the new edges that skip ε-transition by bold edges
in Fig. 5 , and the fully converted Dual G-NFA from TNGA in Fig. 6. Bothexamples show NFAs that precisely handle R = (AT |GA)((AG|T AA)∗).

2.5

Dual G-NFA Properties

Dual G-NFA has properties similar to those of G-NFA.
• It is ε-free.
• For any state, the state’s outgoing edges are labeled by same character.
• It has only one final state.
• It has one or more initial states.
7

procedure BuildDualG-NFA(N = (V, Σ, E, I, F ))V ′ ← ∅, E ′ ← ∅, I ′ ← ∅!
DualGlushkovState ← V \{s′ }s′ ,∃s∈V,(s′ ,ε,s)∈E

for s ∈ Eclose(I) do
if s ∈ DualGlushkovState thenI ′ ← I ′ ∪ {s}end ifend forfor all s ∈ DualGlushkovState dofor (s, char, t) ∈ E dofor t′ ∈ Eclose(t) do
if t ̸= t′ and char ̸= ε and t′ ∈ DualGlushkovState thenE ′ ← E ′ ∪ {(s, char, t′ )}end ifend forE ′ ← E ′ ∪ {(s, char, t)}
end forend forreturn (V ′ , Σ, E ′ , I, F ′ )end procedure
Figure 7: Algorithm Converting T-NFA to Dual G-NFA• It’s number of states is m̃ + 1.
• The number of transitions is m̃2 at worst.
There is a duality between G-NFA and Dual G-NFA in the sense of the properties
of initial sates, final states, and labels of edge.

2.6

Regular Expression Matching Method

For both G-NFA and Dual G-NFA, ε-free NFAs have the same simulation algorithm like that of Fig.8
This algorithm reads input character tn one by one, then searches for a statethat has outgoing edge labeled tn from current active state set (CurrentActivein Fig. 8). For fast search we use the index created by BuildIndex. If suchstates are found, we add a transitive state to next state set (N extActive in
Fig. 8). At the end of a step, we check if the N extActive includes a final state.
If a final state is found, we recognize that the input characters match a given
regular expression.

3

Our Method

3.1

Look ahead matching

The above NFA simulation method reads input characters one by one, andcalculates state transitions. However, it is quite easy to read a next input
character. We consider how to more eﬀectively calculate state transitions. Let
8

procedure G-NFACountMatching(N=(V, Σ, E, I, F ), T
t1 , t2 , t3 , ..., tn )CurrentActive ← ∅N extActive ← ∅M atchCount ← 0Index ← BuildIndex(E)for pos ∈ 1...n do
CurrentActive ← CurrentActive ∪ I
for s ∈ CurrentActive do
N extActive ← N extActive ∪ Index[tpos ][s]end forif N extActive ∩ F ̸= ∅ thenM atchCount ← M atchCount + 1
end ifSwap(CurrentActive, N extActive)
N extActive ← ∅end forreturn M atchCountend procedure
procedure BuildIndex(V, Σ, E)
for s ∈ V dofor char ∈ Σ do
Index[char][s] = ∅end forend forfor (s, char, t) ∈ E do
Index[char][s] = Index[char][s] ∪ {t}end forreturn Index
end procedure
Figure 8: Regular Expression Matching Using NFA

9=the current input character be ti , next input character ti+1 . When we know
ti+1 , we want to treat the states that satisfy the next formula as active states.
LookAheadActive(s, ti , ti+1 ) = {s′ : (s, ti , s′ ) ∈ E, (s′ , ti+1 , s′′ ) ∈ E}
And we formally define normal active states as follows.
Active(s, ti ) = {s′ : (s, ti , s′ ) ∈ E}
For any LookAheadActive(s, ti , ti+1 ), the size of LookAheadActive(s, ti , ti+1 )is equal or less than the size of Active(s, ti ). Because of this diﬀerence in sizeof active states, we consider that look ahead matching can calculate transitions
faster than normal matching. We formally show this algorithm in Fig. 9.
The problem of this matching method is the large size of the state transition table associated with ti and ti+1 . The state transition table has duplicate
transitions and costs O(|E|2 ) space to build from G-NFA.
For example, we show the transition table of Fig. 1 as Table 1. This tablehas 19 records, more than the number of original G-NFA’s transitions. The
diﬀerence is due to the duplication of transitions.

id
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

target state
id ti ti+1 source state target state
15 A
T
1
3
12
2
A
T
4
10
12
3
A
T
14
10
12
4
G
A
2
4
12
5
G
A
11
9
65 A
G
9
11
76 T
A
10
12
14
8
T
A
3
9
15
9
A
A
12
14
10
6 A
A
4
9
15
11 A
A
14
9
12
3 T
*
3
7
13 T
T
3
10
14
4 A
*
4
7
13
15 A
*
14
7
11
16 G
*
11
7
11
17 G
T
11
10
11
Table
11 2: Look Ahead Transition Table
for Dual G-NFA
Table 1: Look Ahead Transition Table
for G-NFA and Dual G-NFA

3.2

ti
T
T
T
T
T
T
A
A
A
A
A
A
G
G
G
A
A
A
A

ti+1
A
A
A
A
A
T
A
A
A
T
T
T
A
A
T
G
G
G
G

source state
3
5
6
13
15
3
4
12
14
4
14
0
11
0
11
5
6
13
15

Dual G-NFA Look Ahead Transition Function

As shown in the above section, Dual G-NFA has the very desirable property
that all outgoing edge of a state have the same label. Because of this property,
10procedure
Dual
G-NFACountLookAheadMatching(N(V, Σ, E, I, F ), T = t1 , t2 , t3 , ..., tn )CurrentActive ← ∅N extActive ← ∅M atchCount ← 0(Index, F inalIndex) ← BuildLookAheadIndex(E)for pos ∈ 1...n − 1 do
CurrentActive ← CurrentActive ∪ I
for s ∈ CurrentActive dofor (t ∈ Index[tpos ][tpos+1 ][s]) do
N extActive ← N extActive ∪ {t}end forend forfor s ∈ CurrentActive dofor (t ∈ F inalIndex[tpos+1 ][s]) do
N extActive ← N extActive ∪ {t}end forend forif N extActive ∩ F ̸= ∅ thenM atchCount ← M atchCount + 1
end ifSwap(CurrentActive, N extActive)
N extActive ← ∅end forreturn M atchCountend procedure
procedure BuildLookAheadIndex(V, Σ, E, F )for s ∈ V dofor char1 ∈ Σ dofor char2 ∈ Σ do
Index[char1 ][char2 ][s] = ∅end forF inalIndex[char1 ][s] = ∅end forend forfor (s, char1 , t) ∈ E dofor (t, char2 , t′ ) ∈ E do
Index[char1 ][char2 ][s] = Index[char1 ][char2 ][s] ∪ {t}end for
if t ∩ F ̸= ∅ thenF inalIndex[char1 ][s] = F inalIndex[char1 ][s] ∪ {t}end ifend forreturn (Index, FinalIndex)
end procedure
Figure 9: Look Ahead Regular Expression Matching Using Dual G-NFA

11=

when the source state and ti are given, the pairs of ti+1 and the target state
are determined uniquely. Therefore, the transition tables size is O(|E|). This iseﬀectively smaller than G-NFA’s size of O(|E|2 ).
For instance, we show the transition table of Fig. 6 in table 2. This tablehas 17 records, equaling the number of original Dual G-NFA’s transitions. A
final state of Dual G-NFA has no outgoing edge, so we show the “∗” on ti+1
column for the transitions that go to final state.

4

Experiments and Results

To confirm the eﬃciency of Dual G-NFA with Look Ahead matching (for short,
Dual G-NFA with LA), we conducted three experiments. All experiments use“English.100MB” text in Pizza&Chili Corpus [8] as the input texts, and wecompared our method with G-NFA, and G-NFA with Look ahead matching (forshort G-NFA with LA). For reference, the results of a simple T-NFA implementation by Russ Cox [6], and NR-grep, a bit parallel implementation of G-NFA
by Gonzalo Navarro are shown. All experiments were executed 10 times andshown time is average.
The first experiment examines fixed string patterns. In this experiment,
patterns were generated as follows. n words were randomly chosen from aword dictionary and then words were joined by conjunction character “|”. We
used /usr/share/dict/words file on Mac OS X 10.9.2 as the word dictionary.
None of words included special characters of regular expressions like “∗”, “?”,or “+”. Thus, the Aho-Corasick algorithm is clearly the most suited method
for this problem. However, to measure trends of our methods, we make thisexperiment.
Table. 3 shows the time (in seconds) needed to convert regular expression
to NFAs. From Table. 3, the needed time is far little time from matching time.
T-NFA (by Cox) was so fast to measure the converting time accurately (It wasunder micro seconds).
n
20
40
60
80
100
120
140
160
180
200

G-NFA
immeasurable
0.01
0.01
0.02
0.02
0.03
0.04
0.05
0.06
0.07

Dual G-NFA
immeasurable
0.01
0.01
0.02
0.02
0.03
0.04
0.05
0.06
0.07

Table 3: Needed time converting regular expression to NFAs in (seconds)
Fig. 10 shows the time (in seconds) needed to match the whole text. From
Fig. 10, the time taken linearly increases with the number of words with T-NFA,
G-NFA or Dual G-NFA. In contrast, G-NFA with LA or Dual G-NFA with LA,
which uses look ahead matching method took constant time regardless of n. We
assume this is because look ahead matching kept the active state size small.
12

600

100

TNFA
nrgrepGNFA
GNFA-Look-Ahead
D-GNFAD-GNFA-Look-Ahead

500

TNFA
nrgrepGNFA
GNFA-Look-Ahead
D-GNFAD-GNFA-Look-Ahead

80

400

time (sec)
40

200

20
100

0

0
20

40

60

80

100
120
#pattern

140

160

180

200

20

40

60

80

100
120
#pattern

140

160

180

200

Figure 10: Needed time (sec) to matching whole text for 1st experiment.

8

GNFA
GNFA-Look-Ahead
D-GNFAD-GNFA-Look-Ahead

7

6

Average active states

time (sec)

60
300

5

4

3

2

1

0
20

40

60

80

100
120
#pattern

140

160

180

200

Figure 11: Average number of active state for 1st experiment.
NR-grep couldn’t treat large regular expressions, so we only measured patterns for n = 20, 40, and 60;
Fig. 11 shows the average active state size, total number of active states
divided by the number of all input characters. As the graph shows, there isstrong correlation between the average active state size and matching time.
In the second experiment, we generated patterns as follows. We inserted
special symbols of regular expressions such as “∗”,“?”, or “+” into the words
used in the first experiment. Insert positions were randomly selected excluding
the first and last word positions. We then joined these generated regular expression patterns by conjunction. In this case, the Aho-Corasick algorithm is clearly
the most suited method since the pattern is a set of fixed string. However, we
can see the basic speed of pattern matching by treating the pattern as a regularexpression.
Fig. 12 shows the results. The trends resemble those of first experiment.
G-NFA-Look-Ahead or Dual G-NFA-Look-Ahead was superior in terms of calculation time.
In the third experiment, we challenged our method with some actual regularexpression patterns in Table. 4. First pattern “suﬃx” matches to words thathave some specific suﬃxes. There were 35 suﬃxes. Second pattern “prefix”
matches to words that have some specific prefixes. There were 32 prefixes. Third
pattern “name” matches to some people’s names. The names were combinationof ten common given names and ten common surnames. Forth pattern “user”
13

600

100

TNFA
nrgrepGNFA
GNFA-Look-Ahead
D-GNFAD-GNFA-Look-Ahead

500

TNFA
nrgrepGNFA
GNFA-Look-Ahead
D-GNFAD-GNFA-Look-Ahead

80

400

time (sec)
40

200

20
100

0

0
20

40

60

80

100
120
#pattern

140

160

180

200

20

40

60

80

100
120
#pattern

140

160

180

200

Figure 12: Needed time (sec) to matching whole text for 2nd experiment.

9

GNFA
GNFA-Look-Ahead
D-GNFAD-GNFA-Look-Ahead

8

7

Average active states

time (sec)

60
300

6

5

4

3

2

1

0
20

40

60

80

100
120
#pattern

140

160

180

200

Figure 13: Average number of active state for 2nd experiment.
matches to popular expression of user and computer name. Fifth pattern “title”
matches all capital strings like a chapter title in books. These patterns include
character classes like “[a-zA-Z]”.
name
suﬃx
prefix
names
user
title

pattern sample[a-zA-Z]+(able|ible|al|...|ise)(in|il|im|infra|...|under)[a-zA-Z]+(Jackson|Aiden|...|Jack) (Smith|Johnson|...|Rodriguez|Wilson)[a-zA-Z]+@[a-zA-Z]+([A-Z]+ )+Table 4: Regular expression patterns used in third experiment.

As shown in Table 5, Dual G-NFA with LA is the fastest in some cases, once
again to the reduction in active state size. Look ahead methods never match
slower than T-NFA, G-NFA and Dual G-NFA. If that input consists of only
small regular expression like pattern “name”, “user” or “title” , NR-grep is thefastest. For such patterns, bit parallel method implemented in NR-grep canmanipulate G-NFAs eﬀectively.

14

pattern
suﬃx
prefix
names
user
title

T-NFA (by Cox)
113.48
14.33
12.95
78.14
38.88

ngrep
20.24
5.295
0.216
0.08
0.186

G-NFA
9.74
2.74
2.97
12.11
2.93

G-NFA with LA
7.51
3.97
2.74
7.41
2.38

Dual G-NFA
106.6478.39
3.21
185.22
2.68

Table 5: Needed time (sec) to matching with whole text
pattern
suﬃx
prefix
names
user
title

G-NFA
2.33
1.50
1.01
1.77
1.03

G-NFA with LA
1.65
1.15
1.00
1.59
1.01

Dual G-NFA
50.44
8.11
0.01
40.67
0.75

Dual G-NFA with LA
1.15
0.33
0.001
0.59
0.01

Table 6: Average active state5

Conclusion

We proposed the new regular expression matching method that based on Dual
G-NFA and Look Ahead Matching. We have shown that Dual G-NFA can construct a look ahead matching index without additional space. Simulations haveshown the eﬀectiveness of look ahead matching in accelerating NFA. From theexperimental results, our method can be useful for regular expression matchingin practical usage. G-NFAs are used in some bit parallel methods, so we now
plan to apply bit parallel techniques to Dual G-NFA methods.

References[1] re2aneﬃcient,
principled
https://code.google.com/p/re2/.

regularexpression

library):[2] A. V. Aho and J. E. Hopcroft: The Design and Analysis of Computer
Algorithms, Addison-Wesley, 1st ed., 1974.
[3] G. Berry and R. Sethi: From regular expressions to deterministic automata. Theoretical computer science, 48 1986, pp. 117–126.
[4] A. Brüggemann-Klein and D. Wood: The validation of sgml content
models. Mathematical and computer modelling, 25(4) 1997, pp. 73–84.
[5] N. Cascarano, P. Rolando, F. Risso, and R. Sisto: infant: Nfa
pattern matching on gpgpu devices. ACM SIGCOMM Computer Comm.
Review, 40(5) 2010, pp. 20–26.
[6] R. Cox:
Regular Expression Matching Can Be Simple And
Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...).
http://swtch.com/~rsc/regexp/regexp1.html, January 2007.
15

Dual G-NFA with LA
3.35
3.82
2.76
3.36
2.21

[7] P. Dlugosch, D. Brown, P. Glendenning, M. Leventhal, and
H. Noyes: An eﬃcient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed
Systems, 2013.
[8] P. Ferragina and G. Navarro: The pizza & chili corpus, 2007.
[9] Y. Kaneta, S. Yoshizawa, S. Minato, H. Arimura, and
Y. Miyanaga: Dynamic reconfigurable bit-parallel architecture for largescale regular expression matching, in Proc. FPT’10, Dec 2010, pp. 21–28.
[10] G. Navarro: Nr-grep: a fast and flexible pattern-matching tool. Software:
Practice and Experience, 31(13) 2001, pp. 1265–1312.
[11] G. Navarro and M. Raffinot: Flexible pattern matching in strings— practical on-line search algorithms for texts and biological sequences.,
Cambridge, 2002.
[12] G. Navarro and M. Raffinot: New techniques for regular expression
searching. Algorithmica, 41(2) 2005, pp. 89–116.
[13] D. Perrin: Finite automata, in Handbook of Theor. Comput. Sci, Vol.B,
Chap. 1, J. van Leeuwen, ed., 1990, pp. 1–57.
[14] G. van Noord: Treatment of epsilon moves in subset construction. Comput. Linguist., 26(1) Mar. 2000, pp. 61–76.
[15] Y. Wakaba, M. Inagi, S. Wakabayashi, and S. Nagayama: Aneﬃcient hardware matching engine for regular expression with nested kleene
operators, in Proc. FPL’11, 2011, pp. 157–161.
[16] H. Yamamoto: Regular expression matching algorithms using dual position automata. Programme Chairs, 7 2009, p. 190.
[17] F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz: Fast andmemory-eﬃcient regular expression matching for deep packet inspection, in
Proc. ANCS’06, ACM, 2006, pp. 93–102.

16