Extracting Synchronous Grammar Rules From Word-Level Alignments in Linear Time

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 1081–1088 Manchester, August 2008 Extracting Synchronous Grammar Rules From Word-Level Alignments in Linear Time Hao Zhang and Daniel Gildea Computer Science Department University of Rochester Rochester, NY 14627, USA David Chiang Information Sciences Institute University of Southern California Marina del Rey, CA 90292, USA Abstract We generalize Uno and Yagiura’s algo- rithm for finding all common intervals of two permutations to the setting of two sequences with many-to-many alignment links across the two sides. We show how to maximally decompose a word-aligned sentence pair in linear time, which can be used to generate all possible phrase pairs or a Synchronous Context-Free Grammar (SCFG) with the simplest rules possible. We also use the algorithm to precisely analyze the maximum SCFG rule length needed to cover hand-aligned data from various language pairs. 1 Introduction Many recent syntax-based statistical machine translation systems fall into the general formalism of Synchronous Context-Free Grammars (SCFG), where the grammar rules are found by first align- ing parallel text at the word level. From word- level alignments, such systems extract the gram- mar rules consistent either with the alignments and parse trees for one of languages (Galley et al., 2004), or with the the word-level alignments alone without reference to external syntactic anal- ysis (Chiang, 2005), which is the scenario we ad- dress here. In this paper, we derive an optimal, linear-time algorithm for the problem of decomposing an ar- bitrary word-level alignment into SCFG rules such that each rule has at least one aligned word and is minimal in the sense that it cannot be further de- composed into smaller rules. Extracting minimal rules is of interest both because rules with fewer words are more likely to generalize to new data, c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. and because rules with lower rank (the number of nonterminals on the right-hand side) can be parsed more efficiently. This algorithm extends previous work on factor- ing permutations to the general case of factoring many-to-many alignments. Given two permuta- tions of n, a common interval is a set of numbers that are consecutive in both. The breakthrough algorithm of Uno and Yagiura (2000) computes all K common intervals of two length n permu- tations in O(n + K) time. This is achieved by designing data structures to index possible bound- aries of common intervals as the computation pro- ceeds, so that not all possible pairs of beginning and end points need to be considered. Landau et al. (2005) and Bui-Xuan et al. (2005) show that all common intervals can be encoded in O(n) space, and adapt Uno and Yagiura’s algorithm to produce this compact representation in O(n) time. Zhang and Gildea (2007) use similar techniques to factor- ize Synchronous Context Free Grammars in linear time. These previous algorithms assume that the input is a permutation, but in machine translation it is common to work with word-level alignments …

Content truncated to 500 words