Java Reference
In-Depth Information
Column
Row 12345
1
L
P
2
Q
R
3
U
4 WX
5
Y
Z
Figure 5.20: Sparse table
T
.
We begin by considering
compaction
methods that convert a table
T
into a
representation devoid of default entries. Such methods operate as follows.
1. The nondefault entries of
T
are stored in compacted form.
2. A mapping is provided from the index pair (
i
,
j
)totheset
E
∪{
de f ault
}
.
3. The LL(1) parser is modified. Wherever the parser accesses
T
[
i
,
j
], the
mapping is applied to (
i
,
j
) and the compacted form supplies the contents
of
T
[
i
,
j
].
Binary Search
The compacted form can be achieved by listing the nondefault entries in order
of their appearance in
T
, scanning from left to right, top to bottom. For the
original table shown in Figure 5.20, the resulting compact table using binary
search is shown in Figure 5.21. If row
r
of the compact table contains the
nondefault entry
T
[
i
,
j
], then row
r
also contains
i
and
j
, which are necessary
for key comparison when the table is searched. We save space if 3
×
E
<
N
×
M
,
assuming each table entry takes one unit of storage. Because the data is sorted
by rowand column, the compact table can be accessed by
binary search
.Given
E
nondefault entries, each access takes
O
(log(
E
)) time.
Hash Table
The compact table shown in Figure 5.22 uses
1 slots and stores
T
[
i
,
j
]ata
location determined by
hashing
i
and
j
, using the hash function
|
E
|+
h
(
i
,
j
)
=
(
i
×
j
)mod(
|
E
|+
1)
