Information Technology Reference
In-Depth Information
self-string. If a match was found, then such a candidate was rejected, otherwise,
it was accepted. h is process was repeated until a desired number of detectors were
generated. A probabilistic analysis was used to estimate the number of detectors
required to provide a desired level of reliability. h is straightforward approach is
given in the following algorithmic form (see Algorithm 1; note that although self is
considered as a set, for most applications it is a collection of data/patterns rather).
NS Algorithm 1: Exhaustive approach in
(binary) negative detector generation
∊
≤
≤
⊂
=
=
Input:
l
,
r
,
T
N
where 1
r
l
and S
U;
l
string length,
r
=
matching threshold,
T
repertoire size
⊂
Output:
Set
D
U detectors generated using
r
-contiguous bits (
rcb
)
matching rule
1
begin
=
2
D
:
φ
<
3
while
|
D
|
T
do
∊
4
Generate randomly bit string
d
U
5
if
d
does not match any string in S
then
=
6
D
:
D
∪
{
d
}
7
end
h e major limitation of such random generation approach appears to be computa-
tional di
culty of generating valid detectors, which grows exponentially with the
size of self. Also for many choices of
l
(“length”) and
r
(“recognition threshold”)
and compositions of self, random generation of strings for detectors may be pro-
hibitive. h us, this random approach is not e
cient. Subsequently, a number of
detector generation approaches were proposed; these are presented in detail in the
following text.
4.3.2
A Dynamic Programming Approach
(Linear-Time Algorithm)
Given a collection of (equal-sized) self-strings
S
and a matching rule with partial
“matching threshold
r
,
”
called the “
r
-contiguous bits” (
rcb
, described in Chapter 3).
h is algorithm works in two phases (D'haeseleer et al., 1996) as follows:
To count recurrences to defi ne an enumeration of all unmatched strings
(not
r
-matched) by
S
in the string space for the given self-set
To generate a detector set (according to the repertoire size) by the counting
recurrence, which is used to pick the detectors at random from the set of
candidate unmatched strings
Search WWH ::
Custom Search