Information Technology Reference
In-Depth Information
Space complexity:
O
(
N
l
)
.
S
The failure probability
P [5] achieved by
N
detectors is
R
N
P
=
(
P
)
.
(1)
R
f
m
Where P is the probability of a match between two random strings.
Since the partial matching rule is Hamming distance, the probability of a match be-
tween two random strings is
l
i
l
i
l
l
l
1
1
1
P
=
=
(2)
m
l
i
2
2
i
2
i
=
r
i
=
r
.
Normally,
P
is small. Table 1 lists some values of
P
with different l and r .
P with different l and r
Table 1. Some values of
r
P m
r
P m
l
l
8
6
0.1445
32
20
0.1077
8
7
0.0351
32
24
0.0035
16
11
0.1051
32
28
9.6506e-6
16
12
0.0384
32
30
1.2317e-007
16
13
0.0106
64
40
0.0300
16
14
0.0021
64
48
3.8665e-005
16
15
0.0003
64
56
2.7813e-010
Notably, these above formula are under an assumption that all detectors are inde-
pendent. In this paper, the other formulas are all based on this assumption. Since the
candidate detectors are generated randomly, the overlap of the detectors will increase
as
N
and
P increase [7].
S
3 Heuristic Detector Generation Algorithm for Negative Selection
Algorithm with Hamming Distance Partial Matching Rule
3.1 Some Definitions
Firstly, some definitions are given.
Definition 1. Template: A template of order i is a size l string consisting of l-i
“blank” symbols (represented by “*” here). For example, “11*1*” is a template of
order 3 with two “blanks” [7].
In this paper, a detector is a string that consists of {0, 1, *}, where “*” can match with
“0” and “1”. Therefore, a template with some “blanks” could be a detector if this
 
Search WWH ::




Custom Search