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

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1512–1521, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices Matthew Skala School of Computer Science University of Waterloo mskala@cs.toronto.edu Victoria Krakovna J´anos Kram´ar Dept. of Mathematics University of Toronto {vkrakovna,jkramar}@gmail.com Gerald Penn Dept. of Computer Science University of Toronto gpenn@cs.toronto.edu Abstract 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. 1 Introduction The use of bit vectors is almost as old as HPSG parsing itself. Since they were first suggested in the programming languages literature (A¨ıt-Kaci et al., 1989) as a method for computing the unifica- tion of two types without table lookup, bit vectors have been attractive because of three speed advan- tages: • The classical bit vector encoding uses bitwise AND to calculate type unification. This is hard to beat. • Hash tables, the most common alternative, involve computing the Dedekind-MacNeille completion (DMC) at compile time if the in- put type hierarchy is not a bounded-complete partial order. That is exponential time in the worst case; most bit vector methods avoid ex- plicitly computing it. • With large type signatures, the table that in- dexes unifiable pairs of types may be so large that it pushes working parsing memory into swap. This loss of locality of reference costs time. Why isn’t everyone using bit vectors? For the most part, the reason is their size. The classical encoding given by A¨ıt-Kaci et al. (1989) is at least as large as the number of meet-irreducible types, which in the parlance of HPSG type signatures is the number of unary-branching types plus the number of maximally specific types. For the En- glish Resource Grammar (ERG) (Copestake and Flickinger, 2000), these are 314 and 2474 respec- tively. While some systems use them nonetheless (PET (Callmeier, 2000) does, as a very notable ex- ception), it is clear that the size of these codes is a source of concern. Again, it has been so since the very beginning: A¨ıt-Kaci et al. (1989) devoted several pages to a discussion of how to “modularize” type codes, which typically achieves a smaller code in ex- change for a larger-time operation than bitwise AND as the implementation of type unification. However, in this and later work on the subject (e.g. (Fall, 1996)), one constant has been …

Content truncated to 500 words