In statistical machine translation, an alignment defines a mapping between the words in the source and in the target sentence. Alignments are used, on the one hand, to train the statistical models and, on the other, during the decoding process to link the words in the source sentence to the words in the partial hypotheses generated. In both cases, the quality of the alignments is crucial for the success of the translation process. In this paper, we propose several evolutionary algorithms for computing alignments between two sentences in a parallel corpus. This algorithm has been tested on different tasks involving different pair of languages. Specifically, in the two shared tasks proposed in the HLT-NAACL 2003 and in the ACL 2005, the EDA-based algorithm outperforms the best participant systems. In addition, the experiments show that, because of the limitations of the well known statistical alignment models, new improvements in alignments quality could not be achieved by using improved search algorithms only. (c) 2007 Elsevier B.V. All rights reserved.
