Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time

Mark-Jan Nederhof


We present a new cubic-time algorithm to calculate the optimal next step in shift-reduce dependency parsing, relative to ground truth, commonly referred to as `dynamic oracle'. Unlike existing algorithms, it is applicable if the training corpus contains non-projective structures.

We then show that for a projective training corpus, the time complexity can be improved from cubic to linear.


  • There are currently no refbacks.

Copyright (c) 2019 Association for Computational Linguistics

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.