view release on metacpan or  search on metacpan

lib/Algorithm/AM/lattice.pod  view on Meta::CPAN

The value of I<n>, and thus the size of the lattice, is determined by
the length of the I<feature vector> of the test item (see F<AM.pod>
for more explanation).  There is a set corresponding to each I<n>-bit
positive integer; furthermore, if set I<A> corresponds to integer I<a>
and set I<B> corresponds to integer I<b>, then I<A> is a superset of
(or "below") I<B> if I<a> & I<b> = I<b>.

=item *

Many of the elements of the supracontextual lattice are equal as sets;
i.e., they have precisely the same members.  Thus, for those of you
who know a lot of math, it is important not to confuse the
supracontextual lattice with the Boolean algebra generated by the
power set of a set.  The supracontextual lattice I<is> a Boolean
algebra of sets; where these sets come from is explained in F<AM.pod>.

To store the supracontextual lattice, it is enough to create an array
C<lattice[]> of length 2^I<n>, where C<lattice[>I<a>C<]> contains a
pointer to a structure containing information about the elements of
the set corresponding to I<a>.

Of course, the size of C<lattice[]> grows exponentially with I<n>; to
overcome that, see the section on L<lattices as products of smaller
lattices|"LATTICES AS PRODUCTS OF SMALLER LATTICES">.

=item *

The supracontextual lattice is built up by adding elements to these
sets one at a time.  When a new element is added to a set, it is a
simple thing to C<memcpy> (actually, we use Perl's safe equivalent,
C<Copy>) the original set to a new location, append the new element,
and change the pointer.  We only have to do this once; F<Parallel.xs>
keeps track of the creation of new sets, so sometimes all that is
necessary is the changing of a pointer.

=back

=head1 TRAVERSING A LATTICE

During the course of the AM algorithm, it is necessary to visit all
the supracontexts that lie "below" a given supracontext.  For
example, given that a supracontext is labeled

 1001011

AM requires an iterator that produces

 1001111
 1011011
 1011111
 1101011
 1101111
 1111011
 1111111

though the order in which these seven are produced is immaterial.

F<Parallel.xs> does this by using a I<Gray code>.  This is a method by
which only one bit flips (either from 0 to 1 or from 1 to 0) at each
step.  Deciding which bit to flip is done as follows:

=over 4

=item 1

List the "gaps"; for

 1001011

the gaps are

 0100000 = gaps[0]
 0010000 = gaps[1]
 0000100 = gaps[2]

Each gap has exactly one 1 bit which lines up with a 0 in the original
number.

=item 2

If there are I<g> gaps, list the I<g>-bit integers in reverse order:
in this case, 111, 110, ..., 001, 000.

=item 3

Take each of these numbers in succession.  Determine where the
rightmost 1 is; its position determines which bit to flip:

 1001011
 1101011 = 1001011 ^               0100000 (rightmost 1 of 111 is bit 0, use gap[0])
 1111011 = 1101011 ^        0010000        (rightmost 1 of 110 is bit 1, use gap[1])
 1011011 = 1111011 ^               0100000 (rightmost 1 of 101 is bit 0, use gap[0])
 1011111 = 1011011 ^ 0000100               (rightmost 1 of 100 is bit 2, use gap[2])
 1111111 = 1011111 ^               0100000 (rightmost 1 of 011 is bit 0, use gap[0])
 1101111 = 1111111 ^        0010000        (rightmost 1 of 010 is bit 1, use gap[1])
 1001111 = 1101111 ^               0100000 (rightmost 1 of 001 is bit 0, use gap[0])

=back

(As I write this, I see that finding the bit to flip is the same
problem of deciding which disk to move in the Towers of Hanoi
problem.)

=head1 LATTICES AS PRODUCTS OF SMALLER LATTICES

Consider the following lattice: the first number is the binary label,
and the other numbers represent the elements of the set with that
label:

 label  elements

  0000

  0001  3
  0010
  0100  6
  1000

  0011  3
  0101  3 6
  0110  6
  1001  1 3
  1010  4
  1100  5 6

  0111  2 3 6
  1011  1 3 4 7
  1101  1 3 5 6
  1110  4 5 6

  1111  1 2 3 4 5 6 7

(Verify that this is a lattice.)

This lattice can be stored as two smaller lattices:

 label  elements

    00  3
    01  2 3 6
    10  1 3 4 7
    11  1 2 3 4 5 6 7

 label  elements

    00  5 6
    01  1 3 5 6
    10  4 5 6
    11  1 2 3 4 5 6 7

The set labeled by 1001 in the large lattice is precisely the
intersection of the sets labeled by 10 and 01 respectively in the
smaller lattices: {1, 3} is the intersection of {1, 3, 4, 7} and {1,
3, 5, 6}.

C<AM::Parallel> breaks the supracontextual lattice up into 4 smaller
lattices, resulting in a great savings of memory at the expense of
finding a lot of intersections.  But since the elements of the sets
are listed as increasing sequences of positive integers, finding the
intersection is actually quite straightforward.