Aligning Sentences in Bilingual Corpora Using Lexical Information

ALIGNING SENTENCES IN BILINGUAL CORPORA USING LEXICAL INFORMATION Stanley F. Chen* Aiken Computation Laboratory Division of Applied Sciences Harvard University Cambridge, MA 02138 Internet: sfc@calliope.harvard.edu Abstract In this paper, we describe a fast algorithm for aligning sentences with their translations in a bilingual corpus. Existing efficient algorithms ig- nore word identities and only consider sentence length (Brown el al., 1991b; Gale and Church, 1991). Our algorithm constructs a simple statisti- cal word-to-word translation model on the fly dur- ing alignment. We find the alignment that maxi- mizes the probability of generating the corpus with this translation model. We have achieved an error rate of approximately 0.4% on Canadian Hansard data, which is a significant improvement over pre- vious results. The algorithm is language indepen- dent. 1 Introduction In this paper, we describe an algorithm for align- ing sentences with their translations in a bilingual corpus. Aligned bilingual corpora have proved useful in many tasks, including machine transla- tion (Brown e/ al., 1990; Sadler, 1989), sense dis- ambiguation (Brown el al., 1991a; Dagan el at., 1991; Gale el al., 1992), and bilingual lexicogra- phy (Klavans and Tzoukermann, 1990; Warwick and Russell, 1990). The task is difficult because sentences frequently do not align one-to-one. Sometimes sentences align many-to-one, and often there are deletions in *The author wishes to thank Peter Brown, Stephen Del- laPietra, Vincent DellaPietra, and Robert Mercer for their suggestions, support, and relentless taunting. The author also wishes to thank Jan Hajic and Meredith Goldsmith as well as the aforementioned for checking the aligmnents produced by the implementation. one of the supposedly parallel corpora of a bilin- gual corpus. These deletions can be substantial; in the Canadian Hansard corpus, there are many deletions of several thousand sentences and one deletion of over 90,000 sentences. Previous work includes (Brown el al., 1991b) and (Gale and Church, 1991). In Brown, align- ment is based solely on the number of words in each sentence; the actual identities of words are ignored. The general idea is that the closer in length two sentences are, the more likely they align. To perform the search for the best align- ment, dynamic programming (Bellman, 1957) is used. Because dynamic programming requires time quadratic in the length of the text aligned, it is not practical to align a large corpus as a sin- gle unit. The computation required is drastically reduced if the bilingual corpus can be subdivided into smaller chunks. Brown uses anchors to per- form this subdivision. An anchor is a piece of text likely to be present at the same location in both of the parallel corpora of a bilingual corpus. Dy- namic programming is used to align anchors, and then dynamic programming is used again to align the text between anchors. The Gale algorithm is similar to the Brown al- gorithm except that instead of basing alignment on the number of words in sentences, alignment is based on the number of characters in sentences. Dynamic programming is also used to search for the best …

Content truncated to 500 words