A Portable Algorithm for Mapping Bitext Correspondence

A Portable Algorithm for Mapping Bitext Correspondence I. Dan Melamed Dept. of Computer and Information Science University of Pennsylvania Philadelphia, PA, 19104, U.S.A. melamed@unagi, cis. upenn, edu Abstract The first step in most empirical work in multilingual NLP is to construct maps of the correspondence between texts and their translations (bitext maps). The Smooth Injective Map Recognizer (SIMR) algo- rithm presented here is a generic pattern recognition algorithm that is particularly well-suited to mapping bitext correspon- dence. SIMR is faster and significantly more accurate than other algorithms in the literature. The algorithm is robust enough to use on noisy texts, such as those result- ing from OCR input, and on translations that are not very literal. SIMR encap- sulates its language-specific heuristics, so that it can be ported to any language pair with a minimal effort. 1 Introduction Texts that are available in two languages (bitexts) are immensely valuable for many natural language processing applications z. Bitexts are the raw ma- terial from which translation models are built. In addition to their use in machine translation (Sato & Nagao, 1990; Brown et al., 1993; Melamed, 1997), translation models can be applied to machine- assisted translation (Sato, 1992; Foster et al., 1996), cross-lingual information retrieval (SIGIR, 1996), and gisting of World Wide Web pages (Resnik, 1997). Bitexts also play a role in less auto- mated applications such as concordancing for bilin- gual lexicography (Catizone et al., 1993; Gale & Church, 1991b), computer-assisted language learn- ing, and tools for translators (e.g. (Macklovitch, 1 "Multitexts" in more than two languages are even more valuable, but they are much more rare. 1995; Melamed, 1996b). However, bitexts are of lit- tle use without an automatic method for construct- ing bitext maps. Bitext maps identify corresponding text units be- tween the two halves of a bitext. The ideal bitext mapping algorithm should be fast and accurate, use little memory and degrade gracefully when faced with translation irregularities like omissions and in. versions. It should be applicable to any text genre in any pair of languages. The Smooth Injective Map Recognizer (SIMR) al- gorithm presented in this paper is a bitext mapping algorithm that advances the state of the art on these criteria. The evaluation in Section 5 shows that SIMR's error rates are lower than those of other bitext mapping algorithms by an order of magni- tude. At the same time, its expected running time and memory requirements are linear in the size of the input, better than any other published algorithm. The paper begins by laying down SIMR's geomet- ric foundations and describing the algorithm. Then, Section 4 explains how to port SIMR to arbitrary language pairs with minimal effort, without rely- ing on genre-specific information such as sentence boundaries. The last section offers some insights about the optimal level of text analysis for mapping bitext correspondence. 2 Bitext Geometry A bitext (Harris, 1988) comprises two versions of a text, such as a text in two different languages. Translators create a bitext each time they …

Content truncated to 500 words