Eficiency in Unification-Based N-best Parsing

Yi Zhang, Stephan Oepen, John Carroll

In: Harry Bunt , Paola Merlo , Joakim Nivre (Hrsg.). Trends in Parsing Technology: Dependency Parsing, Domain Adaptation, and Deep Parsing. Seiten 223-241 Text, Speech and Language Technology Series 43 ISBN 9789048193516 Springer 2010.


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 uni- fication grammars containing significant proportions of globally inconsistent analy- ses. 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 ac- curacy.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence