Information Technology Reference
In-Depth Information
Step 1.
Case 1. If
λ<s
i
.Consider
N
+
(
v
).
Subcase 2-a. If
N
+
(
v
)=
L
+
(
v
),
∅
,orif
k
i,λ
∈
/
then go to Step 2.
Subcase 2-b. If
k
i,λ
∈
L
+
(
v
),
say,
k
i,λ
=
L
(
vu
)forsome
u
∈
N
+
(
v
),
then go to Step 3.
Case 2. If
λ
=
s
i
. (Reach the end of the keyword
K
i
.)
If
i<m
then
i
←
i
+1
λ
←
1
v
1
and go back to Step 1;
If
i
=
m
(reach the last keyword) then go to Step F.
v
←
Step 2.
(This is the step that adds a directed path with tail at the vertex
v
).
Add a directed path
u
0
···
u
z
with
{
u
1
,
···
,u
z
}
as new vertices and
u
0
=
v
and
l
(
u
0
u
1
)=
k
i,λ
,l
(
u
1
u
2
)=
k
i,λ
+1
,
···
,l
(
u
z−
1
u
z
)=
k
i,s
i
.
Then
λ
s
i
andgotoStep1.
←
Step 3.
(In this step, an existing arc
vu
will be used since
l
(
vu
)=
k
i,λ
).
λ
←
λ
+1,
v
u
,
go to Step 1.
Step F.
Final step: Output.
←
3.2.2 Complexity
Let
len
K
=
i
=1
|
.Steps1-3
form a loop that repeats
len
K
times. For Case 1, and Subcase 2-a, each costs
1 unit for each character of
K
i
; for Subcases 2-b, it costs at most
K
i
|
denote the total length of all keywords in
K
units
(for comparisons). For each subcase, an iteration of Step 2 or 3 is followed
and afterward, return back to Step 1 for another loop.
Hence, the complexity of constructing the searching tree is
O
(
len
K
).
Remark: since we only build up this tree once in the whole procedure, the
complexity of constructing the searching tree will not be counted into the
total complexity.
|
Σ
|
