Nathan Gary Glenn > Algorithm-AM > Algorithm::AM::lattice

Download:
Algorithm-AM-2.45.tar.gz

Dependencies

Annotate this POD

Website

View/Report Bugs
Module Version: 2.45   Source   Latest Release: Algorithm-AM-2.46-TRIAL

NAME ^

Algorithm::AM::lattice - How to store and manipulate large lattices in C

VERSION ^

version 2.45

DESCRIPTION ^

The Analogical Modeling (AM) algorithm requires constructing and traversing large completely distributive lattices, also known as Boolean algebras. This document tells how we do it in Parallel.xs.

A lot of what appears below could be used generally to store lattices; that which applies specifically to AM::Parallel is so marked.

BOOLEAN ALGEBRAS AND LATTICES ^

If n is a positive integer, then the set of positive integers that can be expressed in n or fewer bits, along with the operations & (bitwise AND) and | (bitwise OR), is an example of a Boolean algebra. It is also an example of a lattice which is completely distributive. Although all the lattices used in AM are in fact Boolean algebras, it is customary to refer to them merely as lattices.

Any lattice can have a partial order imposed upon it; this is done by defining a <= b whenever a & b = b (or equivalently, a | b = a). This partial order is symmetric, transitive, and antireflexive (if a <= b and b <= a, then a = b). It's called a partial order because it is often the case that neither a <= b nor b <= a.

A common way to draw lattices on paper is by putting elements that are greater than other elements higher up on the paper, using line segments to indicate the partial order. Here's an example:

                000
                /|\
               / | \
              /  |  \
             /   |   \
           001  010  100
           | \  / \  / |
           |  \/   \/  |
           |  /\   /\  |
           | /  \ /  \ |
           011  101  110
             \   |   /
              \  |  /
               \ | /
                \|/
                111

If you can get from one element to another by only going down along the line segments, then the first element is greater than the second.

Notes for AM

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.

Parallel.xs does this by using a 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:

  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.

  2. If there are g gaps, list the g-bit integers in reverse order: in this case, 111, 110, ..., 001, 000.
  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])

(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.)

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}.

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.

To initialize, set i to point to the largest element of the first set and j to point to the largest element of the second set.

  1. Move i to the left as long as it points to an integer larger than that pointed to by j.
  2. If i points to an integer less than the integer pointed to by j, swap i and j so they point into the opposite sets; go to step 1.
  3. If i and j point to equal values, put this equal value into the intersection and move both i and j once to the left.
  4. If i can't be moved, the algorithm ends.

AUTHOR ^

Theron Stanford <shixilun@yahoo.com>, Nathan Glenn <garfieldnate@gmail.com>

COPYRIGHT AND LICENSE ^

This software is copyright (c) 2013 by Royal Skousen.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.

syntax highlighting: