A Dependency-Extended Method of Multi-pattern Matching . . .
183
0
-1 e1,e2
3
0
e5
1
e3,e4 0
2
3
e6
4
e7
3
e1
e2
?B
?C
?D
e1 e2
?B
?C
?G
?D
e3
e4
q0
q1
e1
e2
?B
?C
?D
?A
e5
e6
q2
e1
e2
?B
?C
?D
?A
e5
q3
e1
e2
?B
?C
?D
?A
e5
q4
?F
e7
(a) Multiple BGP Graphs
(b) A D-Tree of Multiple BGP Graphs
Fig. 1. Multiple BGP graphs and a dependent tree (D-Tree)
vertex u, u ∈ V q1 and u ∈ V q2 , there is a vertex v of q 2 , satisfying q 1 ≺ q 2 , such
that e(u, v) /
∈ E q1 and e(u, v) ∈ E q2 , then edge e is a outer edge of vertex u.
NFT containing inner edges is called as inner NFT (iNFT for short) and NFT
containing outer edges is called as outer NFT (oNFT for short).
NFT contains two columns: vertexes and edges. In each row of NFT, the
vertex unit only holds one vertex, and the edge unit holds the inner or outer
edges coupled with vertex unit. Thus, the inner NFT and outer NFT are formed
as iNFT(V q , iE Vq ) and oNFT(V q , oE Vq ), respectively.
The NFT is constructed based on D-Tree. In D-Tree, the vertexes and edges
of a root node are only assigned into iNFT, because no node dominates a root
node. Given any a node q 1 (not a root node), its parent node q 2 and a vertex
u of q 2 , there is a vertex v of q 1 , such that e(u, v) ∈ RE q1 , then u and e(u, v)
are assigned into oNFT. Given any a node q 1 (not a root node) and a vertex u
of q 1 , there is a vertex v of q 1 , such that e(u, v) ∈ RE q1 , then u and e(u, v) are
assigned into iNFT.
Figure 2 describes the node fragment table (NFT). The parent of q 1 is q 0 ,
which can be found from Fig. 1b. For a vertex ?B, there is a vertex ?G of q 1 , such
that e 3 (?B, ?G) ∈ RE q1 = {e 3 , e 4 }, then ?B and e 3 are assigned into oNFT. For
a vertex ?G, there is a vertex ?B of q 1 , such that e 3 (?G, ?B) ∈ RE q1 = {e 3 , e 4 },
Fig. 2. Node fragment table (NFT)