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?
Linguistics Stack Exchange is a question and answer site for professional linguists and others with an interest in linguistic research and theory. It only takes a minute to sign up.
Sign up to join this communityFor 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?
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.
Michael Collins gives a nice explanation in his MOOC on NLP, summarized in this slide:
In short:
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:
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
There are several factors at play:
There are constituent parsers that implement an O(N) algorithm similar to that used by most dependency parsers:
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.
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.