TCS -TR-A-10-40

TCS Technical Report

An Eﬃcient Matching Algorithm for Acyclic Regular
Expressions with Bounded Depth
byYusaku Kaneta, Shin-ichi Minato, and Hiroki
ArimuraDivision of Computer Science
Report Series A
February 23, 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

An Eﬃcient Matching Algorithm for
Acyclic Regular Expressions with Bounded Depth
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 study the regular expression matching problem for a subclass ofregular expressions of small depth. A regular expression is acyclic if it is over the basis Σ∪{·, |}.
By extending the SHIFT-AND approach by Wu and Manber (JACM 39(2),1992), we present
an eﬃcient algorithm that solves the regular expression matching problem for acyclic regularexpressions with length m and depth d and an input text of length n in O(nmd/w) time usingO(md) preprocessing and O(md/w) space in words on unit-cost RAM model with word length
w. When the depth d is constant, typical in real applications, our algorithm runs in O(nm/w)
time and O(m/w) space, while the algorithm by Bille (ICALP, 2006) runs in O(nm log w/w)
time and O(m log w/w) space. Hence, this achieves O(log m) and O(log w) speed-ups in small
automata (m ≤ w) and in large automata (m > w) cases, resp., still keeping O(m/w) space.

1

Introduction

Recent emergence of massive text and sequence data in networks has attracted much attention to researches on eﬃcient string processing technologies [1, 3, 4, 6, 7, 9, 12, 13]. In thispaper, we study the regular expression matching problem, which is one of the most important problems in string processing. This problem is stated as follows: Given a regularexpression R of length m and an input text T of length n, to determine if there exists some
substring of T that belongs to the language deﬁned by R.
For the regular expression matching problem, in 1968, Thompson [11] devised an eﬃcientalgorithm using the idea of simulating a special NFA called a TNFA (Thompson NFA),
which is obtained from an input regular expression by a transformation (the 2nd columnof Fig. 1). This gives an O(nm) time and O(m) space algorithm for the problem.
In 1992, Myers [6] gave the ﬁrst improvement of O(nm) time complexity of Thompson’salgorithm by presenting an O(nm/w) = O(nm/ log n) time algorithm on the (log n)-uniform
RAM model, where w = O(log n) by using so-called four Russians technique, which is acombination of modular decomposition of a TNFA and its simulation using table lookup(the 3rd column of Fig. 1). The space complexity of the algorithm is O(nm/ log n) space(in words), which is still dependent of the text size n 1 .
Then, Bille [4] breaks the O(m) space barrier of space complexity by giving algorithmsof O(nm log w/w) time for large automata and O(n log m) time for small automata using
O(m) words space (the 4th column of Fig. 1). His algorithm is based on a hierarchical decomposition of a given TNFA to a balanced binary tree with O(log m) depth, and simulates
the TNFA level by level in a topdown manner using bit-parallelism with Boolean operations
and subtraction.
In this paper, we study eﬃcient regular expression matching for unbounded regularexpressions with simple structure, large branching, and small depth, typically appearing
1

For any ﬁxed 0 < ϵ ≤ 1, we can derive an algorithm with space O(m2x ) = O(m1+ϵ ) bits by setting theblock length x = ϵ log m. However, its time complexity become O( 1ϵ (nm/ log m)) with factor 1ϵ .

2Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura
Algorithm

PatternThompson [11]Myers [6]Bille [4] (m > w)
(m ≤ w)
Ours(m > w)Sec. 3 (m ≤ w)

REG(Σ, ε, ·, |, ∗) O(nm)
O(m)
O(m)
REG(Σ, ε, ·, |, ∗) O(nm/w)
O(nm/w) O(nm/w)
REG(Σ, ε, ·, |, ∗) O(nm log w/w) O(m log w) O(m log w/w)
O(n log m)O(m log m) O(log m)
REG(Σ, ·, |)O(nmd/w)
O(md)
O(md/w)
O(nd)
O(md)
O(d)

Time

Preprocess Space (in words)

Fig. 1. Summary of the results on regular expression matching algorithms in terms of time T , space S (inwords), and preprocessing P for unbounded acyclic regular expressions over constant alphabets in text sizen, pattern size m, pattern depth d, and word length w.

in practical applications such as NIDS [9, 10]. As a main result, for the class AREG of
unbounded acyclic regular expressions over the basis of letters in Σ, dot ’·’, and union ’|’,
we present an algorithm that solves the regular expression matching problem in O(nmd/w)
time using O(md + m|Σ|/w) preprocessing and O(md/w + m|Σ|/w) space in words, whered ≥ 0 is the depth of a given regular expression. When the depth d is constant, this result
gives an O(log w) time speed up of the O(nm log w/w) algorithm by Bille [4] still keepingO(m/w) space bound. The key of our algorithm is eﬃcient simulation of the ϵ-closure on
TNFA tailored for acyclic regular expressions with small depth. Since our TNFAs are ofunbounded branching, we cannot directly apply Bille [4]’s simulation technique. Hence, we
introduce new simulation techniques based on an extension of the SHIFT-AND bit-paralleltechnique [7, 12], called scatter and gather operations using word-level parallelism.
The advantages of our approach to regular expression matching are summarized asfollows. (i) Simple and eﬃcient: Since our algorithm naturally exploits the composition
structure of TNFA and does not use complex module decomposition as in [4] (in the small
automata case), it is particularly eﬃcient for regular expressions with small depth. (ii)
Hardware friendly: Since it uses only simple bit-operations and addtion/subtraction andavoids the use of table-lookup, it has potential to be implemented on modern parallel
hardwares with simple structure, such as GPGPUs or FPGAs. We can even implement
these instructions directly on hardwired circuits.
The organization of this paper is as follows. In Section 2, we give basic deﬁnitions.
In Section 3 and Section 4, we present our algorithm BPD (Algorithm with Bit-Parallel
Distribution Techniques) for AREG = REG(Σ, ·, |). In Section 5, we report our experimental
results and, in Section 6, we conclude.

2

Preliminary

In this section, we give basic deﬁnitions and notations in the regular expression matchingproblem according to [4, 6]. For detailed deﬁnitions, please consult text books [2, 5, 7].

2.1

Regular expressions and the matching problem

Basic definitions. Let Σ be a ﬁnite alphabet of letters. A string on Σ is a sequence
S = s1 · · · sn of letters, where S[i] = si ∈ Σ for every 1 ≤ i ≤ n. We denote by S[i..j] thesubstring si · · · sj for every i ≤ j, and by ε the empty
string. For a set S ⊆ Σ ∗ of strings,∑
we denote by |S| the cardinality and by ||S|| = s∈S |s| the total size of S. We denote byΣ ∗ and Σ + = Σ ∗ \{ε} the sets of all strings and all non-empty strings on Σ.

An Eﬃcient Matching Algorithm for Acyclic Regular Expressions with Bounded Depth

3

Fig. 2. The parse tree for an acyclic regular expression R1 = (AB|BC|CA)(AA|BB|CC)(BA|CB|AC).

Regular expressions. The class of regular expressions on Σ is deﬁned recursively as
follows: (1) If a ∈ Σ ∪ {ε} then a is a regular expression. (2) If R1 , . . . , Rn are regularexpressions then (R1 · · · Rn ), (R1 | · · · |Rn ), (R1 )+ , and (R1 )∗ are regular expressions. In theabove deﬁnition, regular expressions are unbounded , i.e., n ≥ 1 can be any integer, whilen = 2 in the standard deﬁnition [2, 4, 7]. The length (or the size) of R is deﬁned by the
number of symbols of Σ ∪ {ε, ·, |, ∗, +} appearing in R. A regular expression R deﬁnes thelanguage L(R) ⊆ Σ ∗ in the standard way [2, 7].
Acyclic regular expressions. As notation, for any subset O ⊆ {Σ, ε, ·, |, ∗, +}, wedenote by REG(O) the subclass of REG of all regular expressions constructed from the lettersand the operators in O. Then, we denote by REG = REG(Σ, ε, ·, |, ∗) = REG(Σ, ε, ·, |, ∗, +)the class of regular expressions. In this paper, we introduce a subclass of REG, the class
AREG = REG(Σ, ·, |) of acyclic regular expressions2 , The depth of R, d(R), is deﬁned
by: d(a) = 0 for a ∈ Σ ∪ {ε}. d((R1 · · · Rn )) = d((R1 | · · · |Rn )) = 1 + maxi d(Ri ), andd((R1 )+ ) = d((R1 )∗ ) = 1 + d(R1 ). For every d ≥ 0, we denote by AREGd the subclassconsisting only of expressions with depth no more than d.
Example 1. R1 = ((AB|BC|CA)(AA|BB|CC)(BA|CB|AC)) ∈ AREG3 is an acyclic regular expression with depth d = 3. R2 = (A|B|C|D) ∈ AREG1 and R3 = ((A|B)|(C|D)) ∈AREG2 are acyclic regular expression with depth 1 and depth 2, respectively.
Parse trees. The parse tree for a regular expression R is a labeled, rooted, and ordered
tree TR with node set dom(TR ) satisfying: (1) The leaves are labeled with symbols lab(v)from Σ ∪ {ε}. (2) The internal nodes are labeled with operators lab(v) from {·, |, ∗, +}. (3)The internal nodes labeled with ∗ or + have one child, and those labeled with . and | haveunbounded number of children. We denote the depth of node v by d(v) and the depth of TRby d(TR ). Parse trees have one-to-one correspondence to regular expressions in a standard
manner [5]. Fig. 2 shows an example of the parse tree TR1 for R1 in Example 1.
Non-deterministic finite automata. We use non-deterministic ﬁnite automata forrecognizing the strings in a regular language. A non-deterministic finite automaton (NFA,
for short) is a quadruple N = (V, E, θ, ϕ), consists of the followings: (1) A set V of nodes,
called states. (2) A set E ⊆ V ×(Σ ∪ {ε})×V of labeled, directed edges. (3) Distinguishednodes θ and ϕ ∈ V , called the source and the sink of N . Each element (x, a, y) ∈ E, wherea ∈ Σ ∪ {ε}, is called an a-edge or a a-transition from state x to state y. We deﬁne a path asa connected sequence π of edges. A path π spells a string s if s is obtained by concatenating
the labels of the edges in π. The language accepted by N is the set L(N ) ⊆ Σ ∗ of all strings
spelled on the paths from the source θ to the sink ϕ in N .
2

Note that this is diﬀerent from the notion of acyclic regular languages [8], which is the class of languages
deﬁned by extended regular expressions without “∗” and “+”, but with complement · .

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

Fig. 3. Construction of Thompson automata (TNFAs).

2.2

Regular expression matching problem

A pattern is any regular expression and a text of length n is a string T over Σ. We say thata regular expression R occurs in a text T if there exist some i ≤ j such that T [i..j] ∈ L(R)holds. Then, the index j is called the end position of R in T . Let C ⊆ REG be any subclassof REG. Now, we state our problem below.
Definition 1. The regular expression matching problem for C is, given a regular expression
R ∈ C of length m and a text T = t1 · · · tn of length n, to output the set of all end positionsof R in T .
As the model of computation, we assume the uniform-cost RAM with word lengthw ≥ log n [5]. Let M ≥ 0 be a positive integer. A bitmask is a vector of M bits X =bM · · · b1 ∈ {0, 1}M . If M ≤ w we say the small automata case, and if M > w we say thelarge automata case [4]. For a bit b ∈ {0, 1}, bk denotes the bitmask consisting of m copies
of b. We assume that for bitmasks with M ≤ w, Boolean and arithmetic operations bitwiseand “ & ”, bitwise-or “ | ”, bitwise-not “∼”, left-shift “<<”, right-shift “>>”, addition“+” and subtraction “−” are executed in O(1) time. The space complexity is measured in
the number of computer words.

3

Eﬃcient State-set Simulation of Thompson Automata

In this section, we review Thompson’s algorithm for regular expression matching based on
the state-set simulation of a special class of automata, called TNFAs. Next, we discuss how
to speed-up the simulation of TNFA.

3.1

Construction of Thompson automata

Thompson [11] gave a method to construct a NFA in a special form, called a TNFA, from a
regular expression R that exactly accepts the language L(R). The classiﬁcation of ε-edges
into scatter, gather, mid, and back edges below is not contained in the original [11] andnewly introduced in this paper.
Let R ∈ AREG be any acyclic regular expression and TR be the parse tree for R. For
each node v, let R(v) be the regular expression that corresponds to the subtree TR (v)rooted at v. The following method recursively constructs the TNFA N (v) = NR = (V (v),E(v), θ(v), ϕ(v)) for each node v by traversing the parse tree TR in the post-order. During
the traversal, we construct the following auxiliary information for each node v: the source
θ(v) and the sink ϕ(v); the sets of edges LE(v), SE(v), GE(v), and ME(v) whose members
are called letter, scatter, gather , and mid edges; First, we suppose that v is a leaf of TR .
(a) For R(v) = α ∈ Σ with lab(v) = α, we build TNFA N (v) = Nα = ({θ, ϕ}, LE(v), θ, ϕ)by connecting θ = θ(v) and ϕ = ϕ(v) with letter-edge in LE(v) = {(θ, α, ϕ)} as in (a)of Fig 3.

An Eﬃcient Matching Algorithm for Acyclic Regular Expressions with Bounded Depth

5Fig. 4. The TNFA for an acyclic regular expression R1 = (AB|BC|CA)(AA|BB|CC)(BA|CB|AC) ∈ AREG.

Next, we suppose that v is an internal node with n children v1 , . . . , vn for n ≥ 1. For
every 1 ≤ i ≤ n, we assume that a TNFA NRi = (Vi , Ei , θi , ϕi ) with source θi = θ(vi ) andsink ϕi = ϕ(vi ) is already built for Ri = R(vi ).
(b) For concatenation R(v) = (R1 · · · Rn ) with lab(v) = ’·’, we build TNFA N (v) =N(R1 ···Rn ) by adding new source θ = θ(v) and sink ϕ = ϕ(v), and by connecting subautomata R1 , . . . , Rn in serial by edges in SE(v) = {(θ, ε, θ1 )}, M E(v) = {(ϕi , ε, θi+1 ) | 1 ≤i ≤ n − 1 }, and GE(v) = {(ϕn , ε, ϕ)} as in (b) of Fig 3.
(c) For union R(v) = (R1 | · · · |Rn ) with lab(v) = ’|’, we build TNFA N (v) = N(R1 |···|Rn )by adding new source θ = θ(v) and sink ϕ = ϕ(v), and by connecting subautomata
R1 , . . . , Rn in parallel by edges in SE(v) = { (θ, ε, θi ) | 1 ≤ i ≤ n } and GE(v) ={ (ϕi , ε, ϕ) | 1 ≤ i ≤ n } as in (c) of Fig 3.
(d) In the above deﬁnition, if any of the sets LE(v), SE(v), GE(v), M E(v), and BE(v)is undeﬁned, then we deﬁne that it is empty. We also deﬁne Ψ (v) = {θ(v), ϕ(v)} and∆(v) = LE(v) ∪∪SE(v) ∪ GE(v) ∪ ME(v) ∪ BE(v). Then, we deﬁne
the node set by∪
V (v) = Ψ (v) ∪ ( ni=1 Ψ (vi )) and the edge set by E(v) = ∆(v) ∪ ( ni=1 Ei ).
In Fig. 4, we show the TNFA for the acyclic regular expression R1 of Example 1.

3.2

Eﬃcient State-set Simulation

Most of the previous regular expression matching algorithms [3, 4, 6, 7, 12] employ the standard state-set simulation method developed by Thompson [5, 11]. In this method, an algorithm ﬁrst builds TNFA NR of a given regular expression R, and then simulates thecomputation by NR on text T using an appropriate data structure.
Let R be a regular expression, and let NR = (VR , ER , θR , ϕR ) be the TNFA for R
constructed in Section 3.1. In Thompson’s state-set simulation [11], the current status of
the TNFA NR is represented by a set S ⊆ VR of active states. Let N = NR be the TNFA
and V = VR be its state set. For any set S ⊆ V of active states and any letter α ∈ Σ, wedeﬁne the following operations:– InitN returns the initial state set {θR } and AcceptN returns the sink state set {ϕR }.
– MoveN (S, α) returns the set of all states that is reachable from a current active state
by a single α-transition in E. That is, MoveN (S, α) = { y ∈ V | x ∈ S, (x, α, y) ∈ ER }.
– EpsCloN (S) returns the set of all states that is reachable from a current active state
by one or more ε-transitions in E. That is, EpsCloN (S) = { y ∈ V | x ∈ S, (x1 , ε, x2 ),(x2 , ε, x3 ), . . . , (xn−1 , ε, xn ) ∈ ER }, and called the ε-closure of S.

6

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura

algorithm RunTNFA(T = t1 · · · tn : a text, N : a procedure EpsClo(S : state set):TNFA)
1: for k ← d(R), . . . , 0 do S ← Apply[GE[k]](S);1: X ← InitN ; //The initial state set
2: for k ← d(R), . . . , 0 do S ← Apply[ME[k]](S);2: X ← EpsCloN (X); //Simulate ε-transition
3: for k ← 0, . . . , d(R) do S ← Apply[SE[k]](S);3: for i ← 1, . . . , n do
4: return X;
4:
X ← MoveN (X, ti ); //Simulate α-transition
5:
X ← EpsCloN (X); //Simulate ε-transition
Fig. 6. The algorithm EpsClo for computing ε-closure
6:
if X ∩ AcceptN ̸= ∅ thenfor acyclic regular expressions
7:
output M atch; //A match found
8: end forFig. 5. The algorithm RunTNFA for scanning phase.

In Fig. 5, we show an algorithm RunTNFA that simulates the computation of TNFA N
on an input text T . We can show that the following lemma [11].
Lemma 1 (Thompson [11]). For any input text T = t1 · · · tn , the algorithm RunTNFAin Fig. 5 correctly solves the regular expression matching problem for REG.
Eﬃcient implementation of MoveN is not hard either by using table lookup [6] or using
SHIFT-AND bit-parallel technique [12]. However, an eﬃcient implementation of EpsCloN
is not straightforward since we have to compute the transitive closure of ε-edges.
The key of our algorithm is an eﬃcient implementation of EpsCloN by hierarchicaldecomposition. We partition the ε-edges of TNFA NR into a collection of mutually disjoint
layers as follows. Let VR = V [1] + · · · + V [k] be the partition of the node set VR by theirdepths, where V [k] = { v ∈ VR | d(v) = k } for every level 1 ≤ k ≤ d(TR ). V [k] is called thek-th layer of VR . We deﬁne the sets LE[k], SE[k], GE[k], M E[k], and BE[k] for level k as
follows. For Z ∈ {LE, SE, GE, M E, BE}, the k-th layer Z[k] of the edge set Z is deﬁneby Zk = { e | e ∈ Z(v), v ∈ V [k] }. For any subset F ⊆ ER of ε-edges and any set S ⊆ VR
of active states, we deﬁne the operation Apply[F ](S) by the set of all states reachable froma current active state by zero or one ε-transition in F. In Fig. 6, we present an algorithm
that computes ε-closure for acyclic regular expressions in AREG = REG(Σ, ε, ·, |).
Lemma 2. Let R be any unbounded acyclic regular expression with depth d = d(R) and NR
be its TNFA. For any state set S ⊆ VR , the algorithm EpsClo of Fig. 6 correctly computes
the ε-closure EpsClo(S) of S on NR .
Proof. We can see that if R is acyclic then for any subexpression R′ with source θ′ andsink ϕ′ , there is no ε-path from θ′ to ϕ′ . Furthermore, we can see that if π is any ε-pathin the TNFA then it has the form π = (gp , gp−1 , . . . , gr , mr , sr , sr+1 . . . , sq ), ﬁrst going up
by gather edges gp , gp−1 , . . . , gr ∈ GE[k], reaching a mid edge mr ∈ M E[r], and then going
down by scatter edges sr , sr+1 . . . , sq ∈ SE[k], such that their depths satisﬁes 0 ≤ r ≤min{p, q} ≤ d(R). Then, we see that EpsClo simulates the transition along π.
⊓⊔

4

An eﬃcient algorithm for acyclic regular expressions

4.1

Outline of the algorithm

In this section, we present an algorithm BPD (Bit-Parallel Algorithm using Bit-Distribution)that eﬃciently solves the regular expression matching problem for acyclic regular expressions in AREG. For an acyclic regular expression R ∈ AREG with length m and depth d andAn Eﬃcient Matching Algorithm for Acyclic Regular Expressions with Bounded Depth7a text T with length n, this algorithm runs in O(nmd/w) time using O(md) preprocessing
and O(md/w) space in words on unit-cost RAM with word length w.
Our matching algorithm BPD consists of a preprocessing phase that transform an input
regular expression R ∈ AREG into a number of tables followed by a scanning phase thatsearch for the occurrences of R in an input text T in the following steps.
algorithm BPD
Preprocessing phase:(1) Construct the parse tree of TR from a regular expression R ∈ AREG.
(2) Construct the TNFA (Thompson automata) NR from TR .
(3) Construct a set of bitmasks A from NR .
Scanning phase:(4) Simulate the TNFA NR on an input text T using algorithm RunTNFA.

Fig. 7. The outline of our regular expression matching algorithm BPD

4.2

Preprocessing phase: Computation of bitmasks

In this subsection, we will describe the preprocessing phase. The key of our algorithm iseﬃcient bit-parallel simulation of ε-closure EpsCloA (X). Given a regular expression R, thepreprocessing phase ﬁrst builds the parse tree TR , and then the TNFA NR from TR . The
algorithm then builds a set of bitmasks from NR using the construction described below.
Numbering of states. For the TNFA NR with M states, our algorithm uses M bit integer X ∈ {0, 1}M as a bitmask with length M to encode any subset of VR . To
do this, we assign a unique bit-position 1 ≤ Bit(x) ≤ M to each state x ∈ VR by thedepth-ﬁrst traversal of DR , where the source θ(v) and the sink ϕ(v) are numbered at
node v in the pre-order and the post-order, respectively. For any state set S ⊆ VR , deﬁne
BIT (S) = {Bit(x) | x ∈ S }. For any subset X ⊆ [1, M ], deﬁne N U M (X) to be the bitmask
that represents X. Then, it is ensured that for each node v, the states subautomata N (v)occupies a continuous interval I(v) = [Bit(θ(v)), Bit(ϕ(v))] ⊆ [1, M ], in a bitmask. For
distinct u, v ∈ V [k] in the same level k, their intervals do not overlap, i.e., I(u) ∩ I(v) = ∅.
Construction of bitmasks. For any acyclic regular expression R ∈ AREG with depthd = d(R) = d(TR ) and its TNFA NR , we construct a number of bitmasks in the preprocessing phase as follows.
(1) Alpha-edge transition: For α ∈ Σ,
Chr[α] = |v∈dom,lab(v)=α N U M (Bit(ϕ(v))).
(2) Scatter-edge transition: For k ∈ [0, d],SSrc[k] = |v∈V [k] N U M (Bit(θ(v))).
SDst[k] = |v∈V [k],(θ=θ(v),ε,θ′ )∈SE(v) N U M (Bit(θ′ )).
SBlk[k] = |v∈V [k] N U M (Bit(ϕ(v))).
(3) Gather-edge transition: For k ∈ [0, d],GSrc[k] = |v∈V [k],(ϕ′ ,ε,ϕ=ϕ(v))∈GE(v) N U M (Bit(ϕ′ )).
GDst[k] = |v∈V [k] N U M (Bit(ϕ(v))).
GBlk[k] = |v∈V [k] N U M ([Bit(θ(v)), Bit(ϕ(v)) − 1]).

8

Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimura

Fig. 8. Scatter transitions.

Fig. 9. Gather transitions.

(4) Mid-edge transition: For k ∈ [0, d],
M id[k] = |v∈V [k],(θ′ ,ε,ϕ′ )∈M E(v) N U M (Bit(ϕ′ )).

4.3

Scanning phase: Simulating TNFA in bit-parallel computation

The scanning phase simulate the behavior of the TNFA NR in a standard state-set simulation by bit-parallel computation using previously constructed bitmasks. This is done asfollows. Let S be any state set and X = N U M (BIT (S)) be the corresponding bitmask.
Then, we deﬁne a number of procedures for state transition as follows.
(1) Alpha-edge transition: For α ∈ Σ, deﬁne Alpha(X, α) byX ← (X << 1) & Chr[α](1)This is same as the SHIFT-AND method for exact string matching [3, 12]. For any
letter-edge (x, α, y) ∈ LE(v), Bit(y) = Bit(x) + 1 by construction, Thus, the abovecode correctly implements Move(S).
(2) Scatter-edge transition: For k ∈ [0, d], deﬁne Scatter(X, d) byX ← (X | (SBlk[d] − (X & SSrc[d])) & SDst[d])(2)We explain the behavior of Scatter(X, d) for the N (v) for each v ∈ V [k]. Let SE(v) ={ (θ, ε, θi ) | 1 ≤ i ≤ n } for some n ≥ 1. Firstly, Y = X & SSrc[d] obtains the bitat the source position Bit(θ), which is the lowest in I(v), in the current state set X.
SBlk[d] is the bitmask that only the highest bit of I(v) is set to on and the others
remain oﬀ. Subtracting Y from SBlk[d], Z = SBlk[d] − Y , results that all the bits in[Bit(θ) + 1, Bit(ϕ) − 1] turn on if the source bit Bit(θ) of Y is on, and all bits turnoﬀ otherwise. Thus, taking destination mask SDst[d] and then take bitwise-or to X,
X ′ = (X | (Z & SDst[d])), turns all bits but the destination bits oﬀ. In summary, theabove steps correctly copy the source bit in X to all destination bits in X ′ .

An Eﬃcient Matching Algorithm for Acyclic Regular Expressions with Bounded Depth

9(3) Gather-edge transition: For k ∈ [0, d], deﬁne Gather(X, d) byX ← (X | (GBlk[d] + (X & GSrc[d])) & GDst[d])(3)Since this is similar to the case for Scatter except that Gather uses addition, while Scatter
uses subtraction, we omit the details.
(4) Mid-edge transition: For k ∈ [0, d], deﬁne Mid(X, d) byX ← (X | (X << 1) & M id[k])(4)
For mid edge (ϕi , ε, θi+1 ) ∈ M E(v), Bit(θi+1 ) = Bit(ϕi ) + 1, and it works correctly.
We can show the next lemma that says that the above bit-parallel method correctly implements α-transitions and ε-transitions of all types necessary for our similation of T N F A.
Lemma 3. Let R ∈ AREG and NR be the TNFA for R. For any state set S, the bitmask
X = N U M (BIT (S)) for S, and for any 1 ≤ d ≤ d(R): (1) X = Alpha(X, α) if andonly if S = Move(S, α). (2) X = Scatter(X, d) if and only if S = Apply[SE[d]](S). (3)X = Gather(X, d) if and only if S = Apply[GE[d]](S). (3) X = Mid(X, d) if and only if
S = Apply[M E[d]](S). Furthermore, if M ≤ w then the procedures Alpha, Scatter, Gather,and Mid run in O(1) time on uniform-cost RAM.

4.4

Correctness and complexities

Now, we have the algorithm BPD of Fig. 7 combined with RunTNFA of Fig. 5, EpsClo ofFig. 6, and codes for Alpha, Scatter, Gather, and Mid in the previous subsection. In thefollowings, R ∈ AREG is an acyclic regualr expression with length m and depth d, T is an
text with length n, M is the length of bitmasks, and w is the bit-width of a computer word.
In the small automata case with M ≤ w, we have the main results of this paper from
Lemma 1, Lemma 2, and Lemma 3.
Theorem 1 (case for small automata). Suppose that m ≤ w. Given acyclic regularexpression R ∈ AREG and input text T with length n, The algorithm BPD of Fig. 7 solves
the regular expression matching problem in O(nd) time using O(md + |Σ|) preprocessing
and O(d + |Σ|) space in words.
In the case large automata case with M > w, we can show the following theorem bycombining our Theorem 1 and Lemma 5 of [4].
Corollary 1 (case for large automata). Suppose that m > w. For acyclic regular expressions in AREG, the regular expression matching problem can be solved in O(nmd/w)
time using O(md + m|Σ|/w) preprocessing and O(md/w + m|Σ|/w) space in words.
Corollary 2 (bounded depth). For every d ≥ 0, the regular expression matching problem
for the class AREGd of acyclic regular expressions with depth d is solved in O(nm/w) timeusing O(m) preprocessing and O(m/w) space in words, where w is the bit-width of a word.

5

Experimental Results

In this section, we give the experimental results for the algorithm BPD.
Experimental settings. For input texts, we used a DNA sequence data with length
10MB and alphabet size |Σ| = 4, which is a copy of a part of E.coli in the Canterbury Corpus 3 . For patterns, we used a regular expression, called (K, L)-CNF-Regexp,
3

http://corpus.canterbury.ac.nz/

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

10
9
8
7
6
5
4
3
2
1
0

depth = 8
depth = 2

Running
nning time (sec)Runningning time (sec)10n = 4 (MB)1.5

n = 8 (MB)

1.0
05
0.5
0.0

0

1

2

3
4
5
6
7
The input size (MB)8

9Fig. 10. Running time for the input size.

10(16, 1)(8, 2)(4, 4)(2, 8)
CNF-Regexp type: (# of UNION, # of CONCAT)

Fig. 11. Running time for CNF-Regexp.

1 ) · · · (RL | · · · |RL ) varying parameters bywith depth d = 2 of the form R = (R11 | · · · |RK
1
K(K, L) ∈ {(16, 1), (8, 2), (4, 4), (2, 8)}, where each Rij is a string of length 4. The patterns
have constant depth d and almost constant size m regardless their parameters (K, L). We
implemented the proposed algorithm BPD in C++. All experiments were run on a PC (Intel Core 2 Duo CPU P8600, 2.40 GHz, 32bit words, 4GB RAM, Windows Vista, g++4.3.4
on Cygwin), where an input text is stored on the main memory and the cpu time does notinclude I/O.
Experiment A. Fig. 10 shows the running time of BPD by varying the input sizen = 1 ∼ 10MB for patterns with depth d = 2 and 8 by explicitly inserting parentheses tothe orginal pattern. Then, the running time seems to be linear in the input size n, and also,
increased with the depth d.
Experiment B. Fig. 11 shows the running time of BPD by varying combination of(K, L) keeping the depth d and the size m of R constant, where the input sizes n are
4MB and 8MB. Then, the running time seems to be independent of (K, L) and the shapeof patterns when d and m are constant. These observations are consistent to theoreticalanalysis of algorithm BPD in Section 4.

6

Conclusion

In this paper, we presented a fast matching algorithm for a subclass of the regualr expressions. For the subclass, our algorithm BPD solves the regular expression mathcing problem
in T = O(nmd/w) time, S = O(md/w) space in words, and P = O(md) preprocessing timewith ﬁnite alphabet Σ where d is the depth of regular expression w is the bit-width of acomputer word. If d, b, and |Σ| are constants, BPD runs in O(nm/w) time and O(m/w)
space in words.
In this paper, we considered a restricted subclass AREG of REG, called acyclic regularexpressions without backward edges. Unfortunately, the scatter and gather techniques are
not directly applicable to TNFA with backward edges. Extension of the result of this paperfor subclasses of regular extensions allowing Kleene-plus and Kleene-star is an interesting
research topic. This will be discussed elsewhere.

An Eﬃcient Matching Algorithm for Acyclic Regular Expressions with Bounded Depth

11

References
1. J. Agrawal, Y. Diao, D. Gyllstrom, N. Immerman. Eﬃcient pattern matching over event streams.
Proc. ACM SIGMOD’08 , pp. 147–160, 2008.
2. A. V. Aho. Algorithms for Finding Patterns in Strings. Handbook of Theoretical Computer Science,Vol. A, pp. 255–300, 1990.
3. R. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Communications of the ACM,
Vol. 35, No. 10, pp. 74–82, 1992.
4. P. Bille. New algorithms for regular expression matching. In Proc. of the 33rd International Colloquium
on Automata, Languages and Programming(ICALP), pp. 643–654, 2006.
5. A. V. Aho, J. E. Hopcroft, J. D. Ullman. The Design and Analysis of Computer Algorithms. AddisonWesley, 1974.
6. E. W. Myers. A four-russian algorithm for regular expression pattern matching. Journal of the ACM,
Vol. 39, No. 2, pp. 430–448, 1992.
7. G. Navarro, and M. Raﬃnot. Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms
for Texts and Biological Sequences. Cambridge University Press 2002.
8. D. Perrin, Finite Automata, Handbook of Theoretical Computer Science, Vol. A, pp. 1–57, 1990.
9. R. Sidhu and V. K. Prasanna. Fast regular expression matching using FPGAs. In The 9th Annual IEEE
Symposium on Field-Programmable Custom Computing Machines (FCCM 2001), pp. 227–238, 2001.
10. Snort. http://www.snort.org/
11. K. Thompson. Programming techniques: regular expression search algorithm. Communications of theACM, Vol. 11, No. 6, pp. 419–422, 1968.
12. S. Wu and U. Manber. Fast text searching: allowing errors. Communications of the ACM, Vol. 35,
No. 10, pp. 83–91, 1992.
13. H. Yamamoto. A New Recognition Algorithm for Extended Regular Expressions. Proc. ISAAC 2001,
pp. 257-267, 2001.