Grammars are a powerful technique for modeling and extracting document structure. One challenge, however, is computational complexity. The cost of grammatical parsing is related to both the size of the input and the ambiguity of the grammar. For programming languages, where the terminals appear in a linear sequence and grammars are unambiguous, parsing is O(N). For natural languages, which are linear yet have ambiguous grammars, parsing is O(N3). For documents, where the terminals are arranged in two dimensions and grammars are ambiguous, parsing time can be exponential in the number of terminals. In this paper we introduce (and unify) several geometric data structures which can be used to significantly accelerate parsing. Each structure embodies a different geometric constraint on the set of possible valid parses. The structures are very general: they can be used by any type of grammatical model and applied in a wide variety of document understanding tasks. With a cleanly designed implementation a single parsing framework can be tested with various geometric constraints to determine the most effective combination.

# Efficient Geometric Algorithms for Parsing in Two Dimensions

Efficient Geometric Algorithms for Parsing in Two Dimensions

International Conference on Document Analysis and Recognition (ICDAR) 2005