Information Technology Reference
In-Depth Information
Step 1.
Case 1. If
j<t
i
,gotoStep2.
Case 2. If
j
=
t
i
,gotoStepF.
Step 2.
Case 1. If
d
i,j
∈
L
+
(
v
), say
l
(
vu
)=
d
i,j
where
u
∈
N
+
(
v
), then go to
Step 3.
Case 2. If
d
i,j
∈ L
+
(
v
), then go to Step 4.
Step 3.
Case 1. If
N
+
(
u
)
=
∅
(
u
is not a leave of the tree
T
), then
v
←
u
,
j
+1,
go to Step 1.
Case 2. If
N
+
(
u
)=
j
←
∅
(
u
is a leave of the tree
T
), then
P
(
u
)
←P
(
u
)
∪{
w
}
,
v
←
v
0
,
j
←
j
+1,
w
w
+1,
go to Step 1.
←
Step 4.
Case 1. If
d
ij
=
,
j
j
+1
and go back to Step 4;
←
Case 2. If
d
ij
=
,
v
←
v
0
,
w
+1,
Go to Step 1.
Step F.
Output:
w
←
P
(
K
μ
), for each
K
μ
∈
V
L
.
3.3.2 Complexity
of the document
D
i
is compared with
N
+
(
v
)or
N
+
(
v
)
Each character
d
i,j
∪
N
+
(
v
0
)forsomevertex
v
∈
V
(
T
). That is, it costs at most (
|
Σ
|
+ 1) units
for comparisons. So, the total cost is (
t
i
where
c
is a small constant
cost for re-indexing of
j
,
v
and updating the records
|
Σ
|
+
c
)
×
(
K
μ
).
Thus, the complexity of keyword searching is
O
(
t
i
), where
t
i
is the length
of the input document
D
i
.
P
3.4 Signature Vector of a Document
The
signature vector
R
(
D
i
) for a given document
D
i
is to be calculated in
this section.
