Databases Reference
In-Depth Information
because as soon as the upper limit slips below the halfway mark or the lower limit slips above
the halfway mark we double the interval. However, on closer examination, we can see that
this is not the case. When the upper limit is barely above the halfway mark, the lower limit
is not required to be at 0. In fact, the lower limit can be just below the quarter range without
any rescaling being triggered. However, the moment the lower limit goes above the quarter
mark an
E
3
rescaling is triggered and the interval is redoubled one or more times. Thus the
smallest the active range can be is a quarter of the total range. This means that we need to
accommodate
Total_Count
values in a quarter of the total range available, that is
1
4
2
m
>
Total
_
Count
or
m
>
log
2
(
4
×
Total
_
Count
)
=
2
+
log
2
(
Total
_
Count
)
Because of the way we mapped the endpoints and the halfway points of the unit interval,
when both
l
(
n
)
and
u
(
n
)
are in either the upper half or lower half of the interval, the leading
bit of
u
(
n
)
and
l
(
n
)
will be the same. If the leading or most significant bit (MSB) is 1, then
the tag interval is contained entirely in the upper half of the
interval. If
the MSB is 0, then the tag interval is contained entirely in the lower half. Applying the
E
1
and
E
2
mappings is a simple matter. All we do is shift out the MSB and then shift ina1into
the integer code for
u
(
n
)
and a 0 into the code for
l
(
n
)
. For example, suppose
m
was 6,
u
(
n
)
was 54, and
l
(
n
)
was 33. The binary representations of
u
(
n
)
and
l
(
n
)
are 110110 and 100001,
respectively. Notice that the MSB for both endpoints is 1. Following the procedure above, we
would shift out (and transmit or store) the 1, and shift in 1 for
u
(
n
)
and 0 for
l
(
n
)
, obtaining a
new value for
u
(
n
)
as 101101, or 45, and a new value for
l
(
n
)
as 000010, or 2. This is equivalent
to performing the
E
2
mapping. We can see how the
E
1
mapping would also be performed
using the same operation.
To see i f the
E
3
mapping needs to be performed, we monitor the second most significant bit
of
u
(
n
)
and
l
(
n
)
. When the secondmost significant bit of
u
(
n
)
is 0 and the secondmost significant
bit of
l
(
n
)
is 1, this means that the tag interval lies in the middle half of the
[
00
...
0
,
11
...
1
]
]
interval. To implement the
E
3
mapping, we complement the second most significant bit in
u
(
n
)
and
l
(
n
)
, and shift left, shifting in a 1 in
u
(
n
)
and a 0 in
l
(
n
)
. We also keep track of the
number of
E
3
mappings in Scale3.
We can summarize the encoding algorithm using the following pseudocode:
[
00
...
0
,
11
...
1
Initialize
l
and
u
.
Get symbol.
(
u
−
l
+
1
)
×
Cum
_
Count
(
x
−
1
)
l
←
l
+
Total
_
Count
(
u
−
l
+
1
)
×
Cum
_
Count
(
x
)
u
←
l
+
−
1
Total
_
Count
