Databases Reference
In-Depth Information
Notice that each succeeding interval is contained in the preceding interval. If we examine
the equations used to generate the intervals, we see that this will always be the case. This
property will be used to decipher the tag. An undesirable consequence of this process is that
the intervals get smaller and smaller and require higher precision as the sequence gets longer.
To combat this problem, a rescaling strategy needs to be adopted. In Section
4.4.2
, we will
describe a simple rescaling approach that takes care of this problem.
4.3.2 Deciphering the Tag
We have spent a considerable amount of time showing how a sequence can be assigned a
unique tag, given a minimal amount of information. However, the tag is useless unless we can
also decipher it with minimal computational cost. Fortunately, deciphering the tag is as simple
as generating it. We can see this most easily through an example.
Example4.3.6: Deciphering a Tag
Given the tag obtained in Example
4.3.5
, let's try to obtain the sequence represented by the
tag. We will try to mimic the encoder in order to do the decoding. The tag value is 0.772352.
The interval containing this tag value is a subset of every interval obtained in the encoding
process. Our decoding strategy will be to decode the elements in the sequence in such a way
that the upper and lower limits
u
(
k
)
and
l
(
k
)
will always contain the tag value for each
k
.We
start with
l
(
0
)
=
0 and
u
(
0
)
=
1. After decoding the first element of the sequence
x
1
, the upper
and lower limits become
l
(
1
)
=
0
+
(
1
−
0
)
F
X
(
x
1
−
1
)
=
F
X
(
x
1
−
1
)
u
(
1
)
=
0
+
(
1
−
0
)
F
X
(
x
1
)
=
F
X
(
x
1
)
[
F
X
(
x
1
−
),
F
X
(
x
1
))
In other words, the interval containing the tag is
1
. We need to find the
value of
x
1
for which 0.772352 lies in the interval
[
F
X
(
x
1
−
1
),
F
X
(
x
1
))
.Ifwepick
x
1
=
1
,
the interval is [0, 0.8). If we pick
x
1
=
2
, the interval is [0.8, 0.82), and if we pick
x
1
=
3
,the
interval is [0.82, 1.0). As 0.772352 lies in the interval [0.0, 0.8], we choose
x
1
=
1
.Wenow
repeat this procedure for the second element
x
2
, using the updated values of
l
(
1
)
and
u
(
1
)
:
l
(
2
)
=
0
+
(
0
.
8
−
0
)
F
X
(
x
2
−
1
)
=
0
.
8
F
X
(
x
2
−
1
)
u
(
2
)
=
0
+
(
0
.
8
−
0
)
F
X
(
x
2
)
=
0
.
8
F
X
(
x
2
)
If we pick
x
2
=
1
, the updated interval is [0, 0.64), which does not contain the tag. Therefore,
x
2
cannot be
1
.Ifwepick
x
2
=
2
, the updated interval is [0.64, 0.656), which also does not
contain the tag. If we pick
x
2
3
, the updated interval is [0.656, 0.8), which does contain
the tag value of 0.772352. Therefore, the second element in the sequence is
3
. Knowing the
second element of the sequence, we can update the values of
l
(
2
)
and
u
(
2
)
and find the element
x
3
, which will give us an interval containing the tag:
l
(
3
)
=
=
0
.
656
+
(
0
.
8
−
0
.
656
)
F
X
(
x
3
−
1
)
=
0
.
656
+
0
.
144
×
F
X
(
x
3
−
1
)
u
(
3
)
=
0
.
656
+
(
0
.
8
−
0
.
656
)
F
X
(
x
3
)
=
0
.
656
+
0
.
144
×
F
X
(
x
3
)
