Java Reference
In-Depth Information
T
's Nondefault
From
T
's
Hashes
Index
Contents
Row Column
to
0
R
2
5
10
≡
0
1
L
1
1
1
2
Y
5
2
10
≡
0
3
Z
5
4
20
≡
0
4
P
1
4
4
5
Q
2
2
4
6
W
4
1
4
7
8
X
4
2
8
9
U
3
3
9
Figure 5.22: Compact version of the table in Figure 5.20 using
hashing. Only the boxed information is stored in the compact
table.
The compression algorithm we study is called
double-o
set indexing
.
ff
The algorithm, shown in Figure 5.23, operates as follows:
•
The algorithm initializes a vector
V
at Marker
14
. Although the vector
could hold
N
×
M
entries, the final size of the vector is expected to be
closer to
|
E
|
.Theentriesof
V
are initialized to the parse table's default
value.
•
Marker
15
considers the rows of
T
in an arbitrary order.
•
When row
i
is considered, a shift value for the row is computed by the
F
method. The shift value, retained in
R
[
i
], records the amount
by which an index into row
i
ind
S
hift
is shifted to find its entry in vector
V
.
Method F
checks to be certain that, when shifted, row
i
fits into
V
without any collision with the nondefault entries already established
in
V
.
its
•
The size of
V
is reduced at Marker
16
by removing all default values at
V
's high end.
To use the compressed tables, entry
T
[
i
,
j
] is found by inspecting
V
at location
l
=
R
[
i
]
+
j
.Iftherowrecordedat
V
.
fromrow
[
l
]is
i
, then the table entry at
V
.
entry
[
l
] is the nondefault table entry from
T
[
i
,
j
]. Otherwise,
T
[
i
,
j
]hasthe
default value.
We illustrate the e
ectiveness of the algorithm in Figure 5.23 by applying
it to the sparse table shown in Figure 5.20. Suppose the rows are considered
ff