Paper: K-Best A* Parsing

ACL ID P09-1108
Title K-Best A* Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2009

A∗ parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing k- best extraction methods can efficiently search for top derivations, but only after an exhaus- tive 1-best pass. We present a unified algo- rithm for k-best A∗ parsing which preserves the efficiency of k-best extraction while giv- ing the speed-ups of A∗ methods. Our algo- rithm produces optimalk-best parses under the same conditions required for optimality in a 1-best A∗ parser. Empirically, optimal k-best lists can be extracted significantly faster than with other approaches, over a range of gram- mar types.