Paper: A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices

ACL ID P10-1153
Title A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2010
Authors

Constructing an encoding of a concept lat- tice using short bit vectors allows for ef- ficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encod- ing, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits, resulting in a smaller vector size. A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is pro- vided comparing the extended representa- tion of failure with traditional bit vector techniques.