With the development of globalization, the needs for automatic or semi-automatic translation techniques grow rapidly. The aim of word alignment is to find the translation relation between the corresponding words of parallel bilingual text. Word alignment is a fundamental technique to provide the basis for statistical machine translation, i.e. a technology for automatically translating texts in one language into another by a computer using statistical methods, and it has significant influence on translation quality. In addition, word alignment provides a technique to support technologies such as cross-language retrieval.
Inversion transduction grammar is a family of bilingual synchronous grammars proposed by Dekai Wu. Each instance of inversion transduction grammar consists of several grammar rules, which define the transduction relationship between a particular set of symbols. A pair of start symbols may be synchronously rewritten into a pair of new strings by applying these rules. The inversion transduction grammar requires that each grammar rule should be in one of the following six forms:                s→ε/ε        A→x/ε        A→ε/y        A→x/y        A→[B C]        A→<B C>where ε denotes an empty string, the first four rules denote that the symbols on the left of the arrow can generate the two symbols on the right of the arrow. For example, the 4th rule denotes that symbol A can generate symbol x and y; the 5th rule denotes that symbol A can generate two strings “B C” and “B C” at the same time; the 6th rule denotes that symbol A can generate two strings “B C” and “C B” at the same time.        
Existing research shows that introducing the inversion transduction grammar constraint into word alignment (i.e. requiring that the word alignment can be generated with the inversion transduction grammar) significantly improves the quality of word alignment. The computational cost for searching over all possible word alignments that satisfy the inversion transduction grammar constraint is, however, too high to be used in practical. A few approximating search algorithms has been proposed to reduce computational cost by searching over only part of all the potential word alignments that satisfy the inversion transduction grammar constraint. The computational cost is still too high for practical use.