Information Technology Reference
In-Depth Information
4.3.2.2
Phase II: Generating Strings Unmatched by S
Note that
C
1
[
s
] denotes the number of unmatched
l
-bit strings starting with the
r
-bit binary string
s
. h e total number of strings unmatched by
S
is
∑
T
C
1
[]
s
sS
⋅
C
1
[
] can be thought of as a partitioning of the space of unmatched strings into
partitions of size
C
1
[
s
] for each initial
r
-bit string
s
. Given that among all the
unmatched strings starting with
s
,
C
2
[ˆ
⋅
⋅
0] have a 0 bit next, whereas
C
2
[ˆ
1] h ave
a 1 bit next. h erefore,
C
2
[
⋅
] can be seen as a subsequent partition of the original
⋅
⋅
space. Likewise,
C
3
[
] to
C
l
−
r
+
1
[
] will defi ne corresponding partitions of the
space. Each partition after
C
l
−
r
+
1
[
] will consist of one single
l
-bit string. h ereby,
unmatched strings can be matched from 1 to
T
, using the lexicographic (natural)
order. h us, to generate a number
N
R
of unmatched strings, you can just generate
N
R
random numbers in {1, …,
T
}. If
k
⋅
∈
{1, …,
T
}, the
k
th unmatched string
u
k
is
determined as follows. Perform a binary search on
C
1
[
⋅
] to fi nd
s
1
such that
∑
∑
P
c
[]
s
k
Q c
[]
s
1
1
1
1
ss
ss
1
1
All unmatched strings in (
P
1
,
Q
1
] have
s
1
as their
r
-bit prefi x, where
u
k
is the string
that we are interested in the partition of unmatched strings numbered (
P
1
+
1), …,
Q
1
; therefore, the fi rst
r
bits of
u
k
are given by
s
1
.
For each
i
1)
th
bit of string
u
k
can be
established by determining the partition where
k
falls. To illustrate this, assume
that the bit at position (
r
=
2, …, (
l
−
r
+
1), the (
r
+
i
−
+
1) needs to be determined. Let us partition the interval
=
(
P
1
,
P
1
+
⋅
=
(
P
1
+
⋅
into intervals
I
10
0],
Q
1
), correspond-
ing to the strings concatenated with either a 0 or a 1. On one hand, a bit
b
1
=
C
2
[ˆ
1
0]) and
I
11
C
2
[ˆ
1
0 is
concatenated to the string if
k
is in
I
10
, and on the other, a bit
b
1
=
1 is added to the
string if
k
is in
I
11
. Subsequent intervals (
P
i
, Q
i
] are then computed according to
P
,
if
b
0
Pc
[
s
0
]
, f
b
0
i
1
i
1
i
1
i
i
1
i
1
P
and
Q
i
i
Pc
[
s
0
]
,
if
b
1
Q
,
if
b
i
1
i
1
i
i
1
i
1
i
1
1
h us,
s
2
=
⋅
⋅
ˆ
1
b
1
k
is in interval (
P
2
,
Q
2
), which can again be divided into two
0],
Q
2
)
.
h en, bit
b
2
is
defi ned by checking if it falls in
I
20
or
I
21
. Similar processes are followed to compute
the subsequent bits.
intervals
I
20
= (
P
2
,
P
2
+
C
3
[ˆ
2
⋅
0]) and
I
21
=
(
P
2
+
C
3
[ˆ
2
⋅
Search WWH ::
Custom Search