Algorithms for Deterministic Incremental Dependency Parsing
Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics)
Subscriber deck — free during early access
1 cards in “5.2 Projective Parsing” · whole deck
5.2 Projective Parsing
- How does the projective list-based parser differ from the non-projective one?It skips any pair that could create a non-projective arc: LEFT-ARC deletes the dependent and empties \(\lambda_2\); RIGHT-ARC moves \(j\) onto \(\lambda_1\) and empties \(\lambda_2\); NO-ARC requires that \(i\) already has a head, since an arc spanning a root would violate projectivity. Worst case \(O(n^2)\), but in practice it behaves linearly.
- Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §5.2, pp. 533–537
Source
- Joakim Nivre. 2008. Algorithms for Deterministic Incremental Dependency Parsing. In Computational Linguistics, pp. 513–553. doi:10.1162/coli.07-056-R1-07-027 https://aclanthology.org/J08-4003/