Paper: Non-Projective Dependency Parsing in Expected Linear Time

ACL ID P09-1040
Title Non-Projective Dependency Parsing in Expected Linear Time
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2009
  • Joakim Nivre (Vaxjo University, Vaxjo Sweden; Uppsala University, Uppsala Sweden)

We present a novel transition system for dependency parsing, which constructs arcs only between adjacent words but can parse arbitrary non-projective trees by swapping the order of words in the input. Adding the swapping operation changes the time complexity for deterministic parsing from linear to quadratic in the worst case, but empiricalestimatesbasedontreebankdata show that the expected running time is in fact linear for the range of data attested in the corpora. Evaluation on data from five languages shows state-of-the-art accuracy, with especially good results for the labeled exact match score.