TCS -TR-A-10-47

TCS Technical Report

Fast Bit-Parallel Matching for Network and Regular
Expressionsby

Yusaku Kaneta, Shin-ichi Minato and Hiroki
ArimuraDivision of Computer Science
Report Series A
November 12, 2010

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

arim@ist.hokudai.ac.jp

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

Fast Bit-Parallel Matching for Network andRegular Expressions
Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura
Hokkaido University, N14, W9, Sapporo 060-0814, Japan{y-kaneta,minato,arim}@ist.hokudai.ac.jp

Abstract. In this paper, we extend the SHIFT-AND approach by Baeza-Yates and Gonnet(CACM 35(10), 1992) to the matching problem for network expressions, which are regularexpressions without Kleene-closure and useful in applications such as bioinformatics andevent stream processing. Following the study of Navarro (RECOMB, 2001) on the extended
string matching, we introduce new operations called Scatter, Gather, and Propagate to eﬃciently compute ε-moves of the Thompson NFA using the Extended SHIFT-AND approachwith integer addition. By using these operations and a property called the bi-monotonicity of
the Thompson NFA, we present an eﬃcient algorithm for the network expression matchingthat runs in O(ndm/w) time using O(dm) preprocessing and O(dm/w) space, where m andd are the length and the depth of a given network expression, n is the length of an input
text, and w is the word length of the underlying computer. Furthermore, we show a modiﬁed
matching algorithm for the class of regular expressions that runs in O(ndm log(m)/w) time.

1

Introduction

Recent emergence of massive text and sequence data in networks has attracted
much attention to string processing technologies [1, 3, 4, 11, 14, 16, 18]. In this paper,
we study the regular expression matching problem, which is one of the most important problems in string processing. Especially, for the last decades, approaches basedon eﬃcient NFA simulation have been extensively studied for restricted subclassesof regular expressions, namely, the four-russian approach for the class REG of regular expressions [4, 11]; the SHIFT-AND approach for the class STR of strings [3,18], and the SHIFT-ADD approach for the classes of k-mismatch string patterns [3,8]. In particular, Navarro and Raﬃnot [13, 14] presented eﬃcient bit-parallel approach, called Extended SHIFT-AND approach tailored to a restricted but useful
subclass EXT of extended string patterns, which are regular expressions in linear
form, such as R0 = ([AB]+ )(B.{1, 3})([BC]?)(.∗ )C, that consists of letters a ∈ Σ, wildcards “.”, classes of letters α = [ab · · · ], optional letters α?, bounded repeats α{x, y},and unbounded repeats α∗ and α+ , where α ⊆ Σ. In this approach, Navarro andRaﬃnot [14] nicely extended the original approach of [3, 18] by introducing a new
bit-parallel simulation technique, called the propagation, with the use of integer addition “+” (or subtraction “−”) in addition to usual Boolean operations on RAM
to deal with a special case of ε-closure caused by optional letters α? and bounded
repeats α{x, y} in extended string patterns as well as unbounded repeats α∗ withthe use of an extended letter mask.
In this paper, inspired by the work by Navarro and Raﬃnot [14], we study thepattern matching problem for a special class NET of regular expressions, called network expressions, which are introduced in Myers [12]. A network expression (overstrings) in NET is a regular expression without Kleene-closure, that is, an expression constructed recursively from strings in STR applying ε-edges, concatenation,

2

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura

and union. Similarly, we can deﬁne the class EXNET of extended network expressions, which are network expressions over extended string patterns in EXT. For
example, R1 = A(BA|CD)(CD|AB)B and R2 = A(AB|B?)(B?.∗ |AB)C are examples of expressions in NET and EXNET, respectively. Network expressions and extended network expressions are widely used in applications in the various ﬁelds including suchas bioinformatics [12], event stream processing [1], and network intrusion detection
systems [16].
As main results in this paper, we show the followings. Let RAM (op) denote a
unit-cost random access machine equipped with a set op of arithmetic operations inaddition to the standard Boolean operations “&”, “|”, “∼”, and “⊕”. We present aneﬃcient algorithm that solves the regular expression matching problem for the classes
NET and EXNET in O(nd⌈m/w⌉) time using O(dm + |Σ|⌈m/w⌉) preprocessing andO(d⌈m/w⌉ + |Σ|⌈m/w⌉) space on RAM (+), where Σ is a ﬁxed alphabet, m and d
are the length and the depth of an input expression R, and n is the length of an input
text T over Σ. Furthermore, we show that the regular expression matching problem
for the full class REG can be solved in O(nd⌈m/w⌉ log m) time using O(dm log m +|Σ|⌈m/w⌉) preprocessing and O(d⌈m/w⌉ log m + |Σ|⌈m/w⌉) space on RAM (+). If
we allow the reversal of bitmasks inv as a primitive, then the problem can be solvedin the same time, preprocessing, and space complexities as NET and EXNET on
RAM (+, inv).
To obtain above results, we devise the following techniques to achieve eﬃcient bitparallel simulation of Thompson NFA (TNFA, for short) for classes NET and EXNET.
A key of NFA simulation for the full class REG is an eﬃcient simulation of ε-closure in
TNFA as mentioned in the previous works [4, 11]. Hence, by extending the previous
SHIFT-AND [3, 18] and Extended SHIFT-AND [14] approaches, we introduce a
set of new bit-parallel simulation operations, called Scatter, Gather and Propagate
operations to deal with the long succession and the branching of ε-edges caused byconcatenation and union in network expressions in NET and EXNET. Furthermore,
we also devise a transformation technique of a given TNFA into a special formof NFA that satisﬁes a property called “bi-monotonicity” of ε-moves by attachingnew ε-edges to all subexpressions whose initial and ﬁnal states are ε-reachable in
the original expression. Furthermore, we introduce the barrel shifter technique for
implementing backward ε-edges for REG based on a well-known technique in the
VLSI circuit design.
The advantages of our approach to regular expression matching are summarized
as follows. (i) Simple and eﬃcient: Since our algorithm naturally exploits the composition structure of TNFAs and does not use complex module decompositions asin [4], it is particularly eﬃcient for regular expressions with small depth. (ii) Hardware friendly: Since it uses only simple bit-operations and addition/subtraction andavoids the heavy use of table-lookup, it has potential to be implemented on modern
parallel hardwares with simple structure, such as GPGPUs or FPGAs. To conﬁrm
the above observations, we developed a hardware implementation of a multiple regular expression matching system on FPGA based on the proposed algorithm. The
experimental results showed that the system could match 256 patterns at the sametime against a text stream with throughput of 1.6Gbps and 0.5Gbps in total for
NET and EXNET, respectively.

Fast Bit-Parallel Matching for Network and Regular Expressions

3

Related works. There are a number of researches on the regular expression
matching problem for REG other than the Extended SHIFT-AND approach. In the
Table-Lookup approach, Myers [11] developed an O(nm/ log n) time and space algorithm. Improving the space complexity of [11], Bille and Thorup [5] presentedO(nm(log log n)/(log n)3/2 + n + m) time and O(m) space algorithm. For DFA simulation by Brute force determinization, Navarro and Raﬃnot [15] proposed an O(n)time and O(m2m ) bits space algorithm using DFA simulation of Glushkov’s NFAs,
while Wu and Manber [18] presented an O(n) time and O(m22m ) bits space algorithm based on the DFA simulation of Thompson’s NFAs. Champarnaud et al. [7]improves this result by obtaining an expected exponential reduction of the spacecomplexity. Papers [6, 12, 13] study pattern matching with bounded and unbounded
gaps.
Organization of this paper. In Section 2, we give basic deﬁnitions and notations. In Section 3, we present our algorithm for the class NET of network expressions
as well as extended network expressions EXNET. In Section 4, we give a modiﬁed
algorithm for the full class REG of regular expressions. In Section 5, we show experimental results on the hardware implementation of the proposed algorithms. In
Section 6, we conclude this paper.

2

Preliminary

In this section, we give basic deﬁnitions and notations in the regular expression
matching problem according to [2, 11, 14].
Regular expression matching problem. Let N = {0, 1, 2, . . .}. For i ≤ j, wedeﬁne [i..j] = {i, i + 1, . . . , j}. Let Σ be a ﬁnite alphabet of letters. A string on Σ isa sequence S = s1 · · · sn of letters, where si ∈ Σ for every i. For every 1 ≤ i ≤ j ≤ n,
We denote by S[i] = si ∈ Σ, by S[i..j] the substring si · · · sj , and by ε the empty
string. If i > j, we deﬁne S[i..j] = ε. For a string S, we denote by |S| the length (orthe size) of S.
The class REG of regular expressions on Σ is deﬁned recursively as follows: (1) Ifa ∈ Σ ∪ {ε} then a ∈ REG. (2) If R1 , . . . , Rn ∈ REG then (R1 · · · Rn ), (R1 | · · · |Rn ),(R1 )∗ ∈ REG. In this paper, regular expressions are unbounded , i.e., n ≥ 1, whilen = 2 in the standard deﬁnition [4, 14]. The length (or the size) of R is deﬁned by the
number ||R|| of symbols from Σ ∪ {ε, ·, |, ∗} appearing in R. For a regular expression
R, the parse tree TR , the language L(R) ⊆ Σ ∗ , and the depth (or the height) d(R),respectively, are deﬁned in the standard way [14]. Let C ⊆ REG be any subclass of
REG. A pattern is any regular expression R ∈ C and a text is a string T ∈ Σ ∗ overΣ. We say that a regular expression R of length m occurs in a text T of length n if
there exist some i ≤ j such that T [i..j] ∈ L(R) holds. Then, the index j is called theend position of R in T . Now, we state our problem below. The regular expression
matching problem for a class C ⊆ REG is, given a regular expression R ∈ C of lengthm and an input text T of length n, to output the set of all end positions of R in T .
Subclasses of regular expressions. We introduce the classes STR, EXT, NET,and EXNET of string patterns, extended string patterns, network expressions, andextended network expressions, respectively, as follows. A string pattern over Σ isa string R ∈ Σ ∗ . An extended string pattern [13] over Σ is a regular expression
R = r1 · · · rm (m ≥ 0), where for every 1 ≤ i ≤ m, ri is one of the following forms:

4

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura(i) letters a ∈ Σ, (ii) wildcards “.”, (iii) classes of letters α = [ab · · · ], (iv) optional
letters α?, (v) bounded repeats α{x, y}, and (vi) unbounded repeats α∗ and α+ ,where α ⊆ Σ. The semantics of the additional operations is given by the notational
equivalence: “.” ≡ Σ, α? ≡ (α|ε), α{x, y} ≡ (α?)y−x αx , and α+ ≡ (α α∗ ).
A network expression (over strings) in NET [12] is a regular expression overstrings, that is, a regular expression obtained from strings, ε-edges, concatenation,and union. An extended network expression in EXNET [12] is a network expression
over extended string patterns in EXT. For example, R0 = ([AB]+ )(B.{1, 3})([BC]?)(.∗ )C,
R1 = A(BA|CD)(CD|AB)B, and R2 = A(AB|B?)(B?.∗ |AB)C are examples of expressions
over Σ = {A, B, C} in EXT, NET, and EXNET, respectively.
Model of computation. As the model of computation, we assume a unit-cost
RAM with word length w [2]. For any bitmask length L ≥ 0, A bitmask is a vector
X = bL · · · b1 ∈ {0, 1}L of L bits. for a bit b ∈ {0, 1}, we denote by bk the bitmask
consisting of k copies of b. For bitmasks with L ≤ w, we assume that the following
Boolean and arithmetic operations are executed in O(1) time: bitwise and “&”,bitwise or “|”, bitwise not “∼”, bitwise xor “⊕”, left shift “≪”, right shift “≫”on RAM (), integer addition “+” and integer subtraction “−” on RAM (+). The
space complexity is measured in the number of words.

3

Fast Bit-parallel Algorithm for Extended Network Expressions

In this section, we present an eﬃcient algorithm that receives any input extended
network expression R in NET or EXNET with length m and depth d and an input
text T on Σ with length n, and ﬁnds all the occurrences of R in T in O(nd⌈m/w⌉)
time using O(dm + |Σ|⌈m/w⌉) preprocessing and O(d⌈m/w⌉ + |Σ|⌈m/w⌉) space on
RAM (+). In what follows, we assume an input regular expression R with length mand depth d and the input text T with length n.

3.1

Basic NFA simulation algorithm

We show the outline of our algorithm BP-Match. First, in the preprocessing phase,
we construct a set of the bitmasks MR from a given extended network expression
R ∈ EXNET, and then, in the runtime phase, we search for all the end positions of
R in an input text T based on NFA simulation of NR .
Algorithm BP-Match(T ∈ Σ ∗ : an input text, R ∈ EXNET: an extended network
expression)
Preprocess:(1) Transform R to its expanded form Expand(R).
(2) Construct the TNFA NR from Expand(R).
(3) Construct a set MR of the bitmasks from NR .
Runtime:(4) Simulate NR on T by using MR
Transformation of a regular expression to its expanded form. As preprocessing, we ﬁrst expand all the occurrences of bounded repeats α{x, y} andFast Bit-Parallel Matching for Network and Regular Expressions(a) N( ):"(b) N(!):

p-edgepedge(c) N(!?):
!
"
#
-edge
g
p-edge

!
"
#
-edge
edge

#

(e) N((R1 ... Rn)):

N(Rn)#1 ... "n#n = #= "2 = #n-1

b-edged#1 g-edge

....

N(R1)

N(R
( 1)
1

"
ss-edgeedge "n

!

!
"
#
-edge
g
p-edge(g) N((R1)*):(f) N((R1 | ... | Rn)):s-edged"" = "1(d) N(!*):

5s-edge "N(R1)1#1 g-edge

#

N(Rn)

"

#

p-edge#n g-edgeg edgeFig. 1. The construction of Thompson automata (TNFAs).
depth 0A01
0,1depth 1A
2,3
2
3

R2 = A(AB|B?)(B?.∗ |AB)C

·
0,15
|
1,7
·
2,4
B
3,4
3
4

!
|
7,14

C
14,15

!

depth 1

1

2

2

0

3

B
4

8

!
9

10
C

1

7

14
A

B
5

Fig. 2. The parse tree of an extended network expression R2 = A(AB|B?)(B?.∗ |AB)C.
0

B

A

·
·
8,10
11,13
.*
A
B
B? B?
5,6
5
6 8,9
8 9 9,10
9 10 11,12
11 12 12,13
12 13

depth 0 A

A

3

4

5

6

7

8

9

10

11

12

13

12

13

B? .*

14

15

C

“|“
B?

11

Fig. 3. An extended network expression R2 and its
TNFA N2 = N (R2 ).

“|”
A B

6

15

B

A

B

Fig. 4. The bit-position assignment for subexpressions of Expand(R2 ), where the depth is compressed byignoring internal nodes labeled with concatenation “·”.

unbounded repeats α+ in an input expression R using the equivalence α{x, y} ≡(α?)y−x αx and α+ ≡ (αα∗ ), respectively. Furthermore, we apply the operation, called
bypassing, that replaces all the subexpressions S in R such that ε ∈ L(S) with theexpression S ′ ≡ (S | ε). This bypassing does not change the language L(R). We
denote by Expand(R) the resulting extended network expression. The properties ofExpand(R) will be examined later.
Construction of TNFA. We construct the parse tree TR of R as shown in
Fig. 2. By the construction in Fig. 1, we compute the Thompson NFA (TNFA, forshort) N (R) = (V, E, θ, ϕ) of Expand(R) as shown in Fig. 3, where V = {0, . . . , L}
for L ≥ 0. As a special case, for the subexpression S ′ ≡ (S|ε) introduced by thebypassing, we add the ε-edge to S directly connecting from θS to ϕS instead of rule(f). In Fig. 3, we show an example of TNFA for R2 = A(AB|B?)(B?.∗ |AB)C. For eachnode v of TR , let S = S(v) be the subexpression of Expand(R) associated with v
and NS = N (S) = (VS , ES , θS , ϕS ) be its corresponding TNFA, called the component
TNFA for v, with a state set VS , an edge set ES , initial and ﬁnal states θS and ϕS . By
depth-ﬁrst search of TR from left to right, we assign the set V (v) = {θS , ϕS } ⊆ [0..L]of the initial and ﬁnal states of S to each node v of TR as in Fig. 2, and deﬁne thedepth d(v) by the number of non-concatenation nodes on the path from the root tov. For each x ∈ V (v), we deﬁne d(x) = d(v), and for each subexpression S = S(v),we associate the interval IS = [θS ..ϕS ] ⊆ [0..L]. In Fig. 4, we show a bit-position
assignment related to TR in Fig. 2. A labeled edge e = (u, β, v) ∈ ES is an α-edge if
β ⊆ Σ, and is an ε-edge if β = ε.

6Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura

Algorithm RunTNFA(T = t1 · · · tn : an input text,
N (R): a TNFA)
1: D ← InitN ; //initial state set
2: D ← EpsCloN (D); //ε-closure
3: for i ← 1, . . . , n do
4:
if D ∩ AcceptN ̸= ∅ then5:
report “match at i − 1”;
6:
D ← MoveN (D, ti ); //α-edges
7:
D ← EpsCloN (D); //ε-closure
8: end for
9:
10:

Procedure EpsCloN (D: the state set for a TNFA
N (R))
1: for k ← d(R), . . . , 1 do
2:
D ← Propagate(D, k);
3:
D ← Gather(D, k − 1);
4: end for
5: D ← Propagate(D, 0);
6: for k ← 1, . . . , d(R) do
7:
D ← Scatter(D, k − 1);
8:
D ← Propagate(D, k);
9: end for
10: return D;

Fig. 5. The algorithm RunTNFA for NFA simulationin the runtime phase.

Fig. 6. The procedure EpsCloN for computing
ε-closure.

Eﬃcient NFA simulation. Next, we describe the standard NFA simulation
method developed by Thompson [2, 17] that most of the previous regular expression
matching algorithms [3, 4, 11, 14, 18] employ. In Thompson’s algorithm [17], the current status of the TNFA NR = (VR , ER , θR , ϕR ) is represented by a set D ⊆ VR ofactive states. Then, we deﬁne the following operations: InitN returns the set {θR };AcceptN returns the set {ϕR }; For any letter c ∈ Σ, MoveN (D, c) returns the set{y ∈ VR | y is reachable from some x ∈ D by exactly one α-edge such that c ∈ α}; EpsCloN (D) returns the set {y ∈ VR | y is reachable from some x ∈ D by zero or
more ε-edges }, called the ε-closure of D.
In Fig. 5, we show the algorithm RunTNFA that simulates the computation of
the TNFA NR on an input text T . We can show the following lemma [17].
Lemma 1 (Thompson [17]). For any input text T , the algorithm RunTNFA in
Fig. 5 correctly solves the regular expression matching problem for REG.
Fine classiﬁcation of ε-moves. It is not hard to eﬃciently implement MoveN
either by using table-lookup [11] or SHIFT-AND approach [3, 18], while it is notstraightforward to eﬃciently implement EpsCloN since we have to compute ε-closure.
The key of our algorithm is an eﬃcient implementation of EpsCloN based on a setof new bit-parallel operations Scatter, Gather, and Propagate deﬁned as follows.
In the construction (a)–(g) of TNFA in Fig. 1, we categorize ε-edges in a component TNFA N (S) into four types: (i) e = (θ, ε, θi ) in (f) or (g) is a scatter edge
(s-edge) with depth d(θ), (ii) e = (ϕi , ε, ϕ) in (f) or (g) is a gather edge (g-edge)
with d(ϕ), (iii) e = (θ, ε, ϕ) in (a), (c), (d), or (g) is a propagate edge (p-edge) withd(θ) = d(ϕ), and (iv) e = (ϕi , ε, θi ) in (g) is a back edge (b-edge) with d(θi ) = d(ϕi ),where θ and ϕ are the initial and the ﬁnal states of N (S). We classify the ε-edge
introduced by bypassing as a propagate edge. For scatter, gather, propagate, andback edges in N (S), we assign the depth of the outermost node θ or ϕ of N (S). The
next lemma gives a characterization of ε-edges.
Lemma 2. If e = (u, ε, v) is an ε-edge in the TNFA NR for R ∈ EXNET, then
∆ = d(v) − d(u) ∈ {+1, 0, −1} holds. Moreover, (i) if ∆ = +1, e is a scatter edge,(ii) if ∆ = −1, e is a gather edge, and (iii) if ∆ = 0, e is a propagate edge.

Fast Bit-Parallel Matching for Network and Regular Expressions

7

For any set D ⊆ V and any k = 0, . . . , d(R), we deﬁne Scatter(D, k) (orGather(D, k)) the sets of states from some states in D reachable by exactly one
scatter edge (or one gather edge, resp.) with depth k. On the other hand, the set
Propagate(D, k) is deﬁned by the ε-closure of D restricted by the propagate edges
with depth k. For any component TNFA S, an ε-block B ⊆ VS is a set of statesthat induces a maximal connected component consisting only of propagate edges.
By construction of TNFA and bypassing, we can see that any such ε-block forms a
chain. Clearly, all states in B have the same depth d, which is called the depth of
B. For example, an expression R2 = A(AB|B?)(B?.∗ |AB)C in Fig. 3 has three ε-blocks,
B1 = {1, 7, 14}, B2 = {5, 6}, and B3 = {8, 9, 10}.
Now, we show the key lemma, called the bi-monotonicity lemma on bypassing
transformation. For any d, d′ ∈ N, we deﬁne d ≤1 d′ if d′ −d ≤ 1 holds. For any statesx, y in TNFA N (R), a ε-path π = (x1 = x, . . . , xn = y) ∈ (VR )∗ is said to be bimonotone if there exists some state xk (1 ≤ k ≤ n) such that d(x1 ) ≥1 · · · ≥1 d(xk )and d(xk ) ≤1 · · · ≤1 d(xn ) hold, that is, the depth sequence for the ﬁrst half is nondecreasing and the latter half is non-increasing. By induction on the construction of
TNFA, we can show the next lemma.
Lemma 3 (bi-monotonicity lemma). Let x, y be any states in Expand(R). If π
be any ε-path from x to y, then there also exists some bi-monotone ε-path from x toy in Expand(R).
Based on the bi-monotonicity of an expanded version of TNFA, we present in
Fig. 6 the procedure EpsCloN that computes the ε-closure for EXNET.
Lemma 4. Suppose that Scatter, Gather, and Propagate operations are correctly
implemented for R ∈ EXNET with depth d(R). Then, the algorithm EpsClo in Fig. 6
correctly computes the ε-closure EpsCloN (R) (D) of any state set D.
Proof. The soundness is obvious from construction. The completeness follows that
if a state y is ε-reachable from a state x, then the applications of operators in theorder of the regular expression (Propagete.Gather)∗ Propagete (Scatter.Propagete)∗moves x to y by the existence of a bi-monotone ε-path by Lemma 3. Since this iswhat EpsCloN does, the lemma is proved.
⊓
⊔

3.2

Bit-parallel implementation

To simulate the TNFA NR for an extended network expression Expand(R), we use a
set MR of bitmasks of L bits CHR[c], REP[c], BLKτ [k], SRCτ [k], and DSTτ [k] ∈ {0, 1}L ,for every c ∈ Σ, 0 ≤ k ≤ d(R), and τ ∈ {S, G, P}, where L is the number of thestates of NR . Then, by further generalizing the Extended SHIFT-AND approach,
we simulate the ε-closure operations Scatter, Gather, and Propagate as follows. Let
NS = (V, E, θ, ϕ) be any component TNFA in depth k.
Simulation of Move operation. Preprocess: Let e = (θ, α, ϕ) ∈ E be an αedge of NS , where α ⊆ Σ. To implement the Move operation, we precompute thefollowing bitmasks. For every letter c ∈ α and every NS , we deﬁne: (M.1) CHR[c]has 1 in the bit-position j = ϕ. (M.2) REP[c] has 1 in the bit-position j = ϕ suchthat θ = ϕ holds, that is, an α-edge e is a self-loop, equivalently, either S = α∗ or
S = α+ .

8Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura

Copy

OR

LSB

MSB

...

1

...

n

LSB

MSB
1

...

!
1

...

...

!

1

n

n

(a) Scatter

n

Copy
Copy
LSB

...

MSB
1

... !1 ... !n

!
...
"1
= !2

!1
!

(b) Gather"n(c) Propagate

Fig. 7. The bit-operations and the corresponding parts of TNFAs

Runtime: To simulate the Move(D, ti ), we performD ← (((D ≪ 1) & CHR[ti ]) | 1) | (D & REP[ti ]);(1)

where ti ∈ Σ be an input letter. This code is the same as the code for α-moves inthe Extended SHIFT-AND approach [14]. For the details, see [14].
Simulation of Scatter operation. Preprocess: Let e = (θ, ε, θi ) ∈ E be ascatter edge of NS . To implement the Scatter operation, we precompute the following
bitmasks. For every depth k and every NS , we deﬁne: (S.1) BLKS [k] has 1 in the
bit-position j = ϕ − 1. (S.2) SRCS [k] has 1 in the bit-position j = θ. (S.3) DSTS [k]has 1 in the bit-position j iﬀ j = θi for all i (Fig. 7).
Runtime: To simulate the Scatter(D, k), we performD ← D | ((BLKS [k] − {D & SRCS [k]}) & DSTS [k]);(2)Firstly, by the formula (D & SRCS [k]), we extract the values of source bits from
D. Then, by subtracting the values from BLKS [k], all the destination bits are set
to 1 if the source bits is 1, and all to 0 otherwise. Note that this is done by carrypropagation of subtraction “−”. Finally, we extract the destination bits by and-ing
the result with DSTS [k], and put all the destination bits to D.
Simulation of Gather operation. Preprocess: Let e = (ϕi , ε, ϕ) ∈ E be a gatheredge of NS . For every depth k and every NS , we deﬁne: (G.1) BLKG [k] has 1 in the
bit-position j ∈ [θ + 1..ϕ − 1]. (G.2) SRCG [k] has 1 in the bit-position j iﬀ j = ϕi for
all i. (G.3) DSTG [k] has 1 in the bit-position j = ϕ (Fig. 7).
Runtime: To simulate the Gather(D, k), we do the following
D ← D | ((BLKG [k] + {D & SRCG [k]}) & DSTG [k]);(3)

Since this code is similar to one of Scatter except that Gather uses addition, while
Scatter uses subtraction, we omit the details.
Simulation of Propagate operation. Preprocess: Let e = (θ, ε, ϕ) ∈ E be a
propagate edge of NS . For every k and ε-block B with depth k, we deﬁne: (P.1)
BLKP [k] has 1 in the bit-position i ∈ B. (P.2) SRCP [k] has 1 in the bit-positioni = min(B). (P.3) DSTP [k] has 1 in the bit-position i = max(B) (Fig. 7).
Runtime: To simulate the Propagate(D, k), we perform the followingA ← (D & BLKP ) | DSTP [k];D ← D | (BLKP [k] & ((∼ (A − SRCP [k])) ⊕ A));

(4)
(5)

Fast Bit-Parallel Matching for Network and Regular Expressions

9

The above code works since any ε-block is a chain in the same depth, and thus the
propagation of the carry bits in the subexpression (A−SRCP [k]) correctly implements
the ε-closure on a chain as shown in [13, 14].

3.3

Main results

From Navarro and Raﬃnot (Sec. 1.3.1, [14]), we know that the integer additionand subtraction can be executed in O(⌈m/w⌉) time and space by simulating carrypropagation. Combining this and the arguments in the previous section, we have thefollowing lemma.
Lemma 5. By the above construction, the Move(D, c), Scatter(D, k), Gather(D, k),
and Propagate(D, k) operations for N (R) are correctly implemented to run in O(⌈m/w⌉)
time on RAM (+), where c ∈ Σ, 0 ≤ k ≤ d(R), D is any m-bit mask, m is the number of states in N (R) and w is the word length.
From Lemma 5, in the large automata case with m > w, we can use inexpensive simulation of primitive operations on RAM (+) instead of expensive module
decomposition technique used tabling-based algorithms as in [4, 11]. This will bean advantage of our algorithm in implementing it on parallel hardwares such as
GPGPUs and FPGAs. Now, we show the main result of this paper.
Theorem 1. The algorithm BP-Match solves the regular expression matching problem for NET and EXNET of network and extended network expressions in O(nd⌈m/w⌉)
time using O(dm + |Σ|⌈m/w⌉) preprocessing and O(d⌈m/w⌉ + |Σ|⌈m/w⌉) space,
where n = |T |, m = ||R||, d = d(R), w is the word length.
Proof. The correctness follows from Lemma 1, Lemma 4, and Lemma 5. Then, theresult immediately follows from that the for-loop is executed at most d(R) times
and each code can be executed in O(⌈m/w⌉) time from Lemma 5⊓⊔

4Extension for general regular expressions

To generalize our algorithm in Sec. 3 for the full class REG in the Extended SHIFTAND approach, we need to simulate backward ε-edges corresponding to the Kleeneclosure “∗”. However, the backward ε-edges from lower to higher bits seems hard tocompute on RAM (+). To overcome this diﬃculty, we introduce a technique calledbarrel shifter as follows.
The idea is to decompose each backward ε-moves from higher to lower bits having
the length J bits into a series of right-shifts “≫” having the widths 20 = 1, 21 =2, . . . , 2ℓ , where ℓ = ⌈log δ⌉ and δ = O(m) is the maximum length of the backward
ε-edges in TNFA. More precisely, for each back edge e in a certain depth of R, if
the edge e has the width J ≥ 0, we∑have the unique binary expansion bin(J) =i
Jℓ−1 · · · J0 ∈ {0, 1}L such that J = ℓ−1
i=0 Ji 2 . For each k = 0, . . . , d(R) and i =0, . . . , ℓ − 1, the bitmask BLKB [k][i] is deﬁned by: for each back edge e = (ϕi , ε, θi )in depth k, we ﬁll the interval Ie = [θi ..ϕi ] with 1’s if Jk = 1 and with 0’s if
Jk = 0. In run-time, we set jmp ← 1, and repeatedly perform D ← (D & ∼BLKB [k][i]) | ((D & BLKB [k][i]) ≫ jmp); jmp ← jmp ≪ 1. From the construction,
this operation can be implemented in O(d⌈m/w⌉ log m) time using O(dm log m)
preprocessing and O(d⌈m/w⌉ log m) space.

10

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura

Table 1. Summary of experimental results on the hardware implementation, where #op, #add, #reg,#bram, and #slice, are the numbers of 32 bit operations, 32 bit integer additions, registers, block RAM
lines, resp., per PMM. #pat and #char are the number and the total size of input patterns, resp.

.

Class
#op #add #reg #bram #slice frequency throughput load time #pat #char
STR
5
0
3
256
54 363 MHz 2.9 Gbps 0.182 ms 256 8,192
EXT
11
1
6
512
123 202 MHz 1.6 Gbps 0.328 ms 128 4,096
EXNET
20
9
24
512
736 65 MHz 0.5 Gbps 1.055 ms 128 4,096

Theorem 2. The regular expression matching problem for the class REG can besolved in O(nd⌈m/w⌉ log m) time using O(dm log m + |Σ|⌈m/w⌉) preprocessing andO(d⌈m/w⌉ log m + |Σ|⌈m/w⌉) space.
As an alternative, if there are at most constant number of back edges withmutually distinct lengths, then we can replace the O(log m) term with O(1). As otheroption, if the O(1)-bit-reversal inv is available, we can also replace the O(log m) termwith O(1) on RAM (+, inv) by simulating backward ε-moves by Scatter (or Gather)and inv. Thus, we obtain the same complexity as Theorem 1.

5

Experimental results

To evaluate the performance, we implemented our regular expression matching algorithm on FPGA in Verilog-HDL for STR, EXT, and EXEXT. We designed thealgorithm as a collection of up to 256 pattern matching modules (PPMs) working
simultaneously [10], where the word length is w = 32 bits, and masks are stored inblock RAMs and a set of registers. We used the Xilinx ISE Design Suite 10.1 andSynopsys VCS development tools. Having targetted an FPGA device, Xilinx Virtex5 LX330 with −1 speed grade, which had 51,840 slices and 288 block RAMs with 36
Kbits, we could install up to 256 PPMs. For more details of the experiments, see thecompanion paper [10]. Table. 1 shows the summary of the experimental results on
our hardware. The #bram is given by the number of block RAMs times |Σ| = 256.
Then, we can observe that our hardware achieves the high throughput of 0.5 Gbps
for the class EXNET and of 1.6 Gbps for the class EXT, which is hard to achieve
by software implementation on the current general CPUs. Hence, our algorithm issuitable to hardware implementation.

6

Conclusion

In this paper, we presented an eﬃcient bit-parallel algorithm that solves the regularexpression matching problem for the class EXNET of extended network expressionsin O(nd⌈m/w⌉) time using O(d⌈m/w⌉) space and O(dm) preprocessing by extending
the Extended SHIFT-AND approach [14]. Furthermore, we show that the problem
for the full class REG of regular expressions is solvable in O(nmd log w/w) time on
RAM (+). Experiments on its hardware implementation showed that the proposed
algorithm is suitable to parallel execution on hardwares. Other advantage is theguaranteed worst-case time complexity. Thus, it may be useful as a base algorithm
for other approaches such as ﬁltration as mentioned in [8, 14]. Application of the
Extended SHIFT-AND to tree and XML matching [9] will be an interesting future
research.

Fast Bit-Parallel Matching for Network and Regular Expressions

11

Acknowledgements
The authors would like to thank Osamu Watanabe, Ryuhei Uehara, Takashi Horiyama,
Yoshio Okamoto, Thomas Zeugmann, Shinobu Nagayama, Ayumi Shinohara, Masayuki
Takeda, for their discussions and valuable comments, and to Shingo Yoshizawa, andYoshikazu Miyanaga for their warm encouragements and constant supports on VLSI
circuit design. This research was partly supported by MEXT Grant-in-Aid for Scientiﬁc Research (A), 20240014, FY2008–2011, and interdisciplinary research project“high performance FPGA-based string matching hardwares” under MEXT/JSPS
Global COE Program, FY2007–2011.

References
1. J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Eﬃcient pattern matching over event streams.
In Proc. ACM SIGMOD’08 , 147–160, 2008.
2. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms.
Addison-Wesley, 1974.
3. R. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Communications of the ACM,
35(10), 74–82, 1992.
4. P. Bille. New algorithms for regular expression matching. In Proc. ICALP’06 , 643–654, 2006.
5. P. Bille and M. Thorup. Faster regular expression matching. In Proc. ICALP’09 , 171–182, 2009.
6. P. Bille and M. Thorup. Regular expression matching with multi-strings and intervals. In
Proc. SODA’10 , 1297–1308, 2010.
7. J. -M. Champarnaud, F. Coulon, and T. Paranthoën. Compact and fast algorithms for safe regularexpression search. Int. J. Comput. Math., 81(4), 383–401, 2004.
8. S. Grabowski and K. Fredriksson. Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉)
worst case time. Inf. Proccess. Lett., 105(5), 182–187, 2008.
9. Y. Kaneta and H. Arimura. Faster bit-parallel algorithm for unordered pseudo-tree matching and tree
homeomorphism. In Proc. of IWOCA’10 , Jul. 2010. (also appeared as Hokkaido U., TCS-TR-A-10-43,
May 2010.)
10. Y. Kaneta, S. Yoshizawa, S. Minato, H. Arimura, and Y. Miyanaga. Dynamic reconﬁgurable bitparallel architecture for large-scale regular expression matching. Hokkaido U., TCS-TR-A-10-45, June2010 (submitting).
11. E. W. Myers. A four-Russian algorithm for regular expression pattern matching. Journal of the ACM,
39(2), 430–448, 1992.
12. E. W. Myers. Approximate matching of network expessions with spacers. J. Computational Biology,
3(1), 33–51, 1996.
13. G. Navarro and M. Raﬃnot. Fast and simple character classes and bounded gaps pattern matching,with application to protein searching. In Proc. RECOMB’01, 231–240, 2001.
14. G. Navarro and M. Raﬃnot. Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms
for Texts and Biological Sequences. Cambridge, 2002.
15. G. Navarro and M. Raﬃnot. New techniques for regular expression searching. Algorithmica, 41(2),89–116, 2005.
16. R. Sidhu and V. K. Prasanna. Fast regular expression matching using FPGAs. In Proc. IEEE
FCCM’01, 227–238, 2001.
17. K. Thompson. Programming techniques: regular expression search algorithm. Communications of theACM, 11(6), 419–422, 1968.
18. S. Wu and U. Manber. Fast text searching: allowing errors. Communications of the ACM, 35(10),83–91, 1992.