Why is dependency parsing so much faster than constituency parsing?

Question

For example, Cer, Daniel M., et al. "Parsing to Stanford Dependencies: Trade-offs between Speed and Accuracy." LREC. 2010. :

Why is dependency parsing so much faster than constituency parsing?

Answer 1

Parsing speed obviously depends on a lot of factors, but in this case I would say that algorithmic complexity is the most important. The transition-based dependency parsers (all except MSTParser and RelEx) use greedy decoding and achieve linear complexity (or quadratic in the case of the Covington algorithm). This should be compared to the constituency-based parsers, which are all based on CKY-style dynamic programming, which is O(n^5) for lexicalized models. MSTParser is somewhere in between. It uses dynamic programming, but thanks to the Eisner style split-head representation it runs in O(n^3) time. The more constrained nature of the dependency parsing problem, mentioned in several comments, also plays a role in that it tends to give tighter "grammar constants" (fewer cases to consider in each derivation step), and it also facilitates the use of split-head representations to reduce complexity.

Answer 2

Michael Collins gives a nice explanation in his MOOC on NLP, summarized in this slide:

In short:

• with the usual CKY algorithm in PCFG parsing, which is based on dynamic programming and yields a constituency-based tree, you have a time complexity of O(n^3 * G^3) as the dynamic programming algorithm is also looking for which non-terminal to choose (hence G^3).
• in dependency parsing, the dynamic programming algorithm (e.g. (Covington 2001) that jlawler cited) doesn't have to choose any non-terminal, so the time complexity is simply O(n^3)

Since G (the number of non-terminals in the grammar) is in the order of 50, if your O(n^3) takes 10 seconds to run (in the dependency parsing case), it will take almost 10 minutes if it becomes O(n^3 * G^3) (in the constituency parsing case).

---

References:

• (Covington 2001) Covington, Michael A. "A fundamental algorithm for dependency parsing." Proceedings of the 39th annual ACM southeast conference. 2001.
• For a nice overview of dependency parsing algorithms: Kübler, Sandra, Ryan McDonald, and Joakim Nivre. "Dependency parsing." Synthesis Lectures on Human Language Technologies 1.1 (2009): 1-127.

Answer 3

I asked Michael Covington, whose name is on one of the faster parsers, and he replies:

I don't know the inner workings of any of these parsers (not even the one with my name on it, which was implemented by Joakim Nivre). Choice of programming language may have a lot to do with it.

Another factor is that with dependency parsing, the search space can be considerably smaller because you're only linking together nodes that already exist, not creating an unknown number of new ones. The person to ask is Joakim Nivre. Here's the paper that, in some sense, started the ball rolling: http://www.ai.uga.edu/mc/dgpacmcorr.pdf

Answer 4

There are several factors at play:

• The implementation language: C/C++ is faster than Java is faster than Python
• The algorithm: Most of the constituent parsers, as well as MSTParser, use a dynamic programming approach with O(N^3) time consumption. The ones with "Nivre" in the name use a stepwise deterministic approach with O(N) time consumption. The "Covington" algorithm has O(N^2) time consumption
• The classification algorithm: "Nivre Eager Feature Interact" uses a classification algorithm that is more expensive than the normal linear classifier used by most others
• Finally, there is something called the "Grammar constant" - In constituent parsing, you have labels on the phrases, and deciding on which labels are appropriate depends on the label set.

There are constituent parsers that implement an O(N) algorithm similar to that used by most dependency parsers:

• User Manual of ZPar
• Stanford SRParser

The Stanford SRParser is about 30x as fast as the "Stanford" parser from the table, with better accuracy. It is still slower than the dependency parsers, presumably because of the "grammar constant" - it is reasonable to expect a constituent parser to be 2-3x slower when using a roughly comparable algorithm.

The table above does not use a "roughly comparable algorithm", so it is more of an apples-to-oranges comparison based on the most popular software implementations that people use.

Answer 5

I have no experience building parsers, but I would guess that Dependency parsing is faster because the trees that need to be built are simpler. If you know a given word's part of speech, you have to answer just one more question: which other word in the sentence is its parent? In CG parsing, you need to know which other word or words in the sentence are in the same constituent, and what kind of constituent is it?

The programming language can play a role as well, but it is also possible that we now have such specialized programming languages that a given language can do only one kind of tree or the other. In that case, I expect the languages that can do only DG trees to be simpler than the ones that can do only CG trees.