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

Efficient Parsing of Highly Ambiguous Context-Free Grammars with Bit Vectors Helmut Schmid Institute for Computational Linguistics University of Stuttgart Azenbergstr. 12 D-70174 Stuttgart Germany schmid@ims.uni-stuttgart.de Abstract An efficient bit-vector-based CKY-style parser for context-free parsing is presented. The parser computes a compact parse forest representation of the complete set of possible analyses for large treebank grammars and long input sen- tences. The parser uses bit-vector operations to parallelise the basic parsing operations. The parser is particularly useful when all analyses are needed rather than just the most probable one. 1 Introduction Large context-free grammars extracted from tree- banks achieve high coverage and accuracy, but they are difficult to parse with because of their massive ambiguity. The application of standard chart-parsing techniques often fails due to excessive memory and runtime requirements. Treebank grammars are mostly used as probabilis- tic grammars and users are usually only interested in the best analysis, the Viterbi parse. To speed up Viterbi parsing, sophisticated search strategies have been developed which find the most probable anal- ysis without examining the whole set of possible analyses (Charniak et al., 1998; Klein and Manning, 2003a). These methods reduce the number of gener- ated edges, but increase the amount of time needed for each edge. The parser described in this paper follows a contrary approach: instead of reducing the number of edges, it minimises the costs of building edges in terms of memory and runtime. The new parser, called BitPar, is based on a bit- vector implementation (cf. (Graham et al., 1980)) of the well-known Cocke-Younger-Kasami (CKY) algorithm (Kasami, 1965; Younger, 1967). It builds a compact “parse forest” representation of all anal- yses in two steps. In the first step, a CKY-style recogniser fills the chart with constituents. In the second step, the parse forest is built top-down from the chart. Viterbi parses are computed in four steps. Again, the first step is a CKY recogniser which is followed by a top-down filtering of the chart, the bottom-up computation of the Viterbi probabilities, and the top-down extraction of the best parse. The rest of the paper is organised as follows: Sec- tion 2 explains the transformation of the grammar to Chomsky normal form. The following sections describe the recogniser algorithm (Sec. 3), improve- ments of the recogniser by means of bit-vector op- erations (Sec. 4), and the generation of parse forests (Sec. 5), and Viterbi parses (Sec. 6). Section 7 dis- cusses the advantages of the new architecture, Sec- tion 8 describes experimental results, and Section 9 summarises the paper. 2 Grammar Transformation The CKY algorithm requires a grammar in Chom- sky normal form where the right-hand side of each rule either consists of two non-terminals or a sin- gle terminal symbol. BitPar uses a modified ver- sion of the CKY algorithm allowing also chain rules (rules with a single non-terminal on the right-hand side). BitPar expects that the input grammar is al- ready epsilon-free and that terminal symbols only occur in unary rules. Rules with more than 2 non- terminals …

Content truncated to 500 words