Java Reference
In-Depth Information
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
Figure9.1 The bit array for the set of primes in the range 0 to 15. The bit at
position i is set to 1 if and only if i is prime.
This approach to compression is similar in spirit to Ziv-Lempel coding, which
is a class of coding algorithms commonly used in file compression utilities. Ziv-
Lempel coding replaces repeated occurrences of strings with a pointer to the lo-
cation in the file of the first occurrence of the string. The codes are stored in a
self-organizing list in order to speed up the time required to search for a string that
has previously been seen.
9.3
Bit Vectors for Representing Sets
Determining whether a value is a member of a particular set is a special case of
searching for keys in a sequence of records. Thus, any of the search methods
discussed in this topic can be used to check for set membership. However, we
can also take advantage of the restricted circumstances imposed by this problem to
develop another representation.
In the case where the set values fall within a limited range, we can represent the
set using a bit array with a bit position allocated for each potential member. Those
members actually in the set store a value of 1 in their corresponding bit; those
members not in the set store a value of 0 in their corresponding bit. For example,
consider the set of primes between 0 and 15. Figure 9.1 shows the corresponding
bit array. To determine if a particular value is prime, we simply check the corre-
sponding bit. This representation scheme is called a bit vector or a bitmap. The
mark array used in several of the graph algorithms of Chapter 11 is an example of
such a set representation.
If the set fits within a single computer word, then set union, intersection, and
difference can be performed by logical bit-wise operations. The union of sets A
and B is the bit-wise OR function (whose symbol is | in Java). The intersection
of sets A and B is the bit-wise AND function (whose symbol is & in Java). For
example, if we would like to compute the set of numbers between 0 and 15 that are
both prime and odd numbers, we need only compute the expression
0011010100010100 & 0101010101010101:
The set difference AB can be implemented in Java using the expression A&˜B
( ˜ is the symbol for bit-wise negation). For larger sets that do not fit into a single
computer word, the equivalent operations can be performed in turn on the series of
words making up the entire bit vector.
 
Search WWH ::




Custom Search