DFKI-LT - Efficiency in unification-based N-best parsing

Yi Zhang, Stephan Oepen, John Carroll
Efficiency in unification-based N-best parsing
1 Proceedings of the tenth international conference on parsing technologies (IWPT 2007), Pages 48-59, Prague, Czech, o.A., 6/2007
We extend a recently proposed algorithm for n-best unpacking of parse forests to deal efficiently with (a) Maximum Entropy (ME) parse selection models containing important classes of non-local features, and (b) forests produced by unification grammars containing significant proportions of globally inconsistent analyses. The new algorithm empirically 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 parsing with post-hoc parse selection it leads to improved parsing speed, coverage, and accuracy.
Files: BibTeX, W07-2207.pdf