Paper: A* Parsing: Fast Exact Viterbi Parse Selection

ACL ID N03-1016
Title A* Parsing: Fast Exact Viterbi Parse Selection
Venue Human Language Technologies
Session Main Conference
Year 2003

We present an extension of the classic A* search procedure to tabular PCFG parsing. The use of A* search can dramatically reduce the time required to find a best parse by conservatively estimating the probabilities of parse completions. We discuss vari- ous estimates and give efficient algorithms for com- puting them. On average-length Penn treebank sen- tences, our most detailed estimate reduces the to- tal number of edges processed to less than 3% of that required by exhaustive parsing, and a simpler estimate, which requires less than a minute of pre- computation, reduces the work to less than 5%. Un- like best-first and finite-beam methods for achieving this kind of speed-up, an A* method is guaranteed to find the most likely parse, not just an approximation. Our parser, which is simple...