Chart parsers can be implemented based on Chomsky normal form or directly based on production rules. Lets for the moment assume we have a CYK chart parser that uses Chomsky normal form. The binarization is not uniquely defined. Does this impact the performance of the CYK chart parse. Can this be exploited to improve the performance of a CYK chart parser?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ The approaches create grammars of the same size, don't they? CYK always fills the complete table, so you can only speed up checking "Is there a fitting rule?". Therefore, I would expect only rule count to have an influence, not grammar structure. $\endgroup$– RaphaelJun 17, 2011 at 12:43
-
$\begingroup$ The method used for binarization also affects the size of the grammar, which affects CYK performance: informatica-didactica.de/cmsmadesimple/… discusses some alternatives to CNF $\endgroup$– MaxSep 30, 2013 at 20:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
While the obvious answer is that the fundamental complexity can't change, there may be better or worse algorithms for parsing the strings you're actually going to encounter. However, it seems like the issue is less the relative frequency of individual grammar productions (the A's, B's, and C's in the question) and more an issue of the unused, dead end parses that one binarization versus another may produce.
With a bit of searching I found Better Binarization for the CKY Parsing (Song, Ding, and Lin, EMNLP 2008), which seems to definitively conclude that you can pick a "better" or "worse" binarization relative to the strings you actually expect to have to parse. Their name for the "dead end parses" that one would hope to minimize in practice seems to be incomplete constituents, and there is a good example on the first page.
-
$\begingroup$ Consider the grammar including productions (S --> A B C) (T --> A B D). If "BC" is always preceded by "A," but "AB" is occasionally not followed by "C," there will be fewer dead ends if you combine B and C, and the relative frequency is irrelevant. Your point about "few" and "many" makes sense if words appear at random, but what I think Song, Ding, and Lin are doing is exploiting ngram frequency, which is a bit more sophisticated. They also point out that, in my example, you might still win with the "AB" binarization by exploiting sharing! $\endgroup$ Jun 29, 2011 at 3:31
$\begingroup$
$\endgroup$
Actually, Chomsky normal form (CNF) is not need to run CYK, only binarization. Binarization is essential to preserve cubic complexity of parsing, though essential only with respect to non-terminals (NT). But then, if you have rules including only 2 non-terminals and some terminals, the CYK algorithm becomes more complex to program and explain.
As you say, there are many ways to do binarisation. Some will yield smaller grammars than other. For example
X -> B C D
Y -> B C E
can be binarized as
X -> Z D
Y -> Z E
Z -> B C
thus saving one rule by factorization, which may save on the computation, and on its result size.
But with other rules, you might want to factorize the end of the rules rather than the beginning.
I am not familiar with the work of Song, Ding, and Lin, cited by Rob Simmons' answer. The idea is interesting but I wonder how effective it can be compared to other ways of optimizing the computation. I fear not so much.
The point is that analyzing the issues only with respect to a pure CKY algorithm seem a bit an academic but costly exercise since there are other kinds of optimization that can significantly improve the elimination of dead end parses.
CYK is only one of the simpler variations in a family of algorithms that are all built on the same dynamic programming model, apparently. I am saying apparently because the simplest version of these algorithms is not known as dynamic programming, but as cross-product. It is the old construction of a CF grammar G that generates the intersection of the language of CF grammar F and the regular language of a FSA A., due to Bar Hillel, Perles and Shamir (1961), as remarked by Lang in 1995.
All chart parser, or general CF parsers based on dynamic programming may be seen as "optimized" variant of that cross-product construction, the optimization being used mainly to avoid useless computations of the parser. But the problem is subtle as avoiding useless computation may result in duplicating useful ones, which may be worse.
Being bottom-up, the CKY algorithm produces useless computations of partial parses that cannot derive from the axiom of the grammar.
Algorithms like the GLR parser (to name one of the better known ones, though flawed version have been published), have some top-down knowledge that will avoid many such useless computations, possibly at cost. And there are many other variants with different behavior with respect to saving on useless computations..
It is with these optimization strategies in mind that the binarization strategy should be analyzed. What is the point of optimizing what may be a minor issue, and ignore more powerful techniques.
The optimization of the parsing process is also tightly linked to the "quality" of the parse-structure obtained, that represent all possibles parses, and is often called (shared-)parse-forest. I discuss that in another answer.
Some of these issues are discussed in the literature. For example by Billot and Lang analyse some aspects of binarisation with respect to parsing strategies.
