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
 
Search WWH ::




Custom Search