Databases Reference
In-Depth Information
the next element of the sequence as
2
. We can then update the equations for the tag interval as
l
(
3
)
=
0
.
312
+
(
0
.
6
−
0
.
312
)
F
X
(
1
)
=
0
.
312
+
0
.
288
×
0
.
8
=
0
.
5424
u
(
3
)
=
0
.
312
+
(
0
.
8
−
0
.
312
)
F
X
(
2
)
=
0
.
312
+
0
.
288
×
0
.
82
=
0
.
54816
As the tag interval is now contained entirely in the upper half of the unit interval, we rescale
using
E
2
to obtain
l
(
3
)
=
2
×
(
0
.
5424
−
0
.
5
)
=
0
.
0848
u
(
3
)
=
2
×
(
0
.
54816
−
0
.
5
)
=
0
.
09632
We also shift out a bit from the tag and shift in the next bit. The tag is now 000110. The
interval is contained entirely in the lower half of the unit interval. Therefore, we apply
E
1
and
shift another bit. The lower and upper limits of the tag interval become
l
(
3
)
=
2
×
(
0
.
0848
)
=
0
.
1696
u
(
3
)
=
2
×
(
0
.
09632
)
=
0
.
19264
and the tag becomes 001100. The interval is still contained entirely in the lower half of the
unit interval, so we shift out another 0 to get a tag of 011000 and go through another rescaling:
l
(
3
)
=
2
×
(
0
.
1696
)
=
0
.
3392
u
(
3
)
=
2
×
(
0
.
19264
)
=
0
.
38528
Because the interval containing the tag remains in the lower half of the unit interval, we
shift out another 0 from the tag to get 110000 and rescale one more time:
l
(
3
)
=
2
×
0
.
3392
=
0
.
6784
u
(
3
)
=
2
×
0
.
38528
=
0
.
77056
Now the interval containing the tag is contained entirely in the upper half of the unit interval.
Therefore, we shift out a 1 from the tag and rescale using the
E
2
mapping:
l
(
3
)
=
2
×
(
0
.
6784
−
0
.
5
)
=
0
.
3568
u
(
3
)
=
2
×
(
0
.
77056
−
0
.
5
)
=
0
.
54112
Now we compare the tag value to the tag interval to decode our final element. The tag is
100000, which corresponds to 0
.
5. This value lies in the first 80% of the interval, so we
decode this element as
1
.
If the tag interval is entirely contained in the upper or lower half of the unit interval, the scal-
ing procedure described will prevent the interval from continually shrinking. Nowwe consider
the case where the diminishing tag interval straddles the midpoint of the unit interval. As our
trigger for rescaling, we check to see if the tag interval is contained in the interval [0.25, 0.75).
