Binarization of grammars is crucial for improving the complexity and performance of parsing and translation.

We present a versatile binarization algorithm that can be tailored to a number of grammar formalisms by simply varying a formal parameter.

We apply our algorithm to binarizing tree-to-string transducers used in syntax-based machine translation.

Binarization amounts to transforming a given grammar into an equivalent grammar of rank 2, i.e., with at most two nonterminals on any right-hand side.

The ability to binarize grammars is crucial for efficient parsing, because for many grammar formalisms the parsing complexity depends exponentially on the rank of the grammar.

The classical approach to binarization , as known from the Chomsky normal form transformation for context-free grammars (CFGs), proceeds rule by rule.

Note that after binarization , grandparent and sibling information becomes very important in encoding the structure.

This section introduces important implementation details, including supertagging, feature forest pruning and binarization methods.

5.3 Binarization

Since Penn Treebank trees are not binarized, we construct a simple procedure for binarizing them.

Note that the two derivations share the same ( binarized ) tree structure.

The system can provide bina-rzied CFG trees in Chomsky Norm Form, and they present a reversible conversion procedure to map arbitrary CFG trees into binarized trees.

In this work, we remain consistent with their work, using the head-finding rules of Zhang and Clark (2008), and the same binarization algorithm.1 We apply the same beam-search algorithm for decoding, and employ the averaged perceptron with early-update to train our model.

Our annotations are binarized recursive word

(Los Angeles)”, have flat structures, and we use “coordination” for their left binarization .

We present a more precise characterization of the algorithm’s complexity, an optimization analogous to binarization of context-free grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications.

We give a more precise complexity analysis in terms of the grammar and the size and maximum degree of the input graph, and we show how to optimize it by a process analogous to binarization of CFGs, following Gildea (2011).

In this section, we present a refinement that makes the rule-matching procedure explicit, and because it matches rules little by little, similarly to binarization of CFG rules, it does so more efliciently than the original.