Paper: Top-Down K-Best A* Parsing

ACL ID P10-2037
Title Top-Down K-Best A* Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Short Paper
Year 2010

We propose a top-down algorithm for ex- tracting k-best lists from a parser. Our algorithm, TKA∗ is a variant of the k- best A∗ (KA∗) algorithm of Pauls and Klein (2009). In contrast to KA∗, which performs an inside and outside pass be- fore performing k-best extraction bottom up, TKA∗ performs only the inside pass before extracting k-best lists top down. TKA∗ maintains the same optimality and efficiency guarantees of KA∗, but is sim- pler to both specify and implement.