Paper: Efficiency in Unification-Based N-Best Parsing

ACL ID W07-2207
Title Efficiency in Unification-Based N-Best Parsing
Venue Conference on Parsing Technologies
Session Main Conference
Year 2007

We extend a recently proposed algorithm for n-best unpacking of parse forests to deal ef- ficiently with (a) Maximum Entropy (ME) parse selection models containing important classes of non-local features, and (b) forests produced by unification grammars contain- ing significant proportions of globally incon- sistent analyses. The new algorithm empir- ically exhibits a linear relationship between processing time and the number of analyses unpacked at all degrees of ME feature non- locality; in addition, compared with agenda- driven best-first parsing and exhaustive pars- ing with post-hoc parse selection it leads to improved parsing speed, coverage, and ac- curacy.† 1 Background—Motivation Technology for natural language analysis using lin- guistically precise grammars has matured to a ...