Top-Down K-Best A* Parsing
Adam Pauls, Dan Klein, Chris Quirk · 2010
We propose a top-down algorithm for extracting 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 before 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 simpler to both specify and implement. 1