📄 Efficient Parsing of Highly Ambiguous Context-Free Grammars with Bit Vectors

Summary

Treebank-derived context-free grammars give good coverage but are massively ambiguous. Ordinary chart parsers often exhaust memory or time on them, especially when every analysis is needed and not only the single best one. Schmid presents BitPar, a CKY-style parser that keeps the number of edges and instead makes each edge cheap to store and build. The chart is a dense bit array. The core step, joining two adjacent constituents under a binary rule, is done with bitwise AND over whole vectors of split points rather than one position at a time. Parsing runs in separate passes. A recogniser first fills the chart. A top-down pass then rebuilds a compact parse forest. For Viterbi parsing, filtering, probability computation and best-tree extraction follow the recogniser. Tested on a large annotated Penn treebank grammar, BitPar beat the earlier LoPar parser at every sentence length and used far less memory. Its measured growth with sentence length stayed below cubic. The parser suits tasks that need the whole analysis set, and its Viterbi mode returns the exact best parse without any tuning.

Key points

• Grammar and hardware: 65,855 rules and 4,444 categories, extracted from a Penn treebank version enriched with features similar to Klein and Manning (2003b). Average rule length was 3.7. Tests ran on a Sun Blade 1000 (750 MHz, 4 GB).
• Parse times: 1000 random sentences (24,595 tokens) were parsed.
  • Viterbi parsing took 27,596 s, about 1.14 s per word.
  • Parse-forest generation took 26,840 s, about 1.09 s per word.
• Growth with length: Runtime grew with an exponent of roughly 2.6 for sentences of 4–50 words. The author attributes this to bit-vector operations becoming more effective as vectors get longer.
• Memory:
  • At length 22, LoPar needed about 1 GB, while BitPar used 180 MB for the forest and 55 MB for Viterbi.
  • At length 55, BitPar needed 113 MB for Viterbi and 3,185 MB for the forest. LoPar could not parse sentences that long.
• Viterbi time breakdown: chart building took about 15%, filtering 28%, probability computation 57%, and best-parse extraction was negligible.

Interesting ideas

• I1. Recognise first, analyse later. The first pass only records whether a constituent exists, so it can stop at the first successful derivation. Full analyses are built afterwards, and only for constituents that belong to a complete parse. Separating cheap existence checks from expensive structure building could help any search over dense candidate spaces.
• I2. Precomputed closure vectors. For each category, the parser stores a bit vector of everything reachable from it through chain (unary) rules. Adding a constituent then inserts all its unary ancestors with a single OR. Precomputed transitive closures used as bitmasks would also work in type hierarchies or tag-set expansions.
• I3. Memory layout matched to the hot loop. The chart is kept twice, in two bit orderings. This lets the left-child and right-child vectors each be copied out in contiguous blocks, at the price of slower insertion. Trading duplicated storage for fast access in the dominant operation is a broadly reusable engineering choice.
• I4. Cheap adaptive ordering. Rules are tried in order of how often they have succeeded, with counts gathered online during parsing. Categories that unlock many chain-rule derivations are processed first. This makes early exits happen sooner, and the same trick applies to any search that stops at the first success.
• I5. Greedy frequency-based binarisation. Following Eisele's method, the most frequent adjacent symbol pair is repeatedly replaced by a new non-terminal. This keeps the binarised grammar small and resembles BPE-style merging, so it may suit other grammar or sequence compression tasks.