Generalized Biwords for Bitext Compression and Translation Spotting: Extended Abstract

1 Introduction

The increasing availability of large collections of bilingual parallel corpora has fostered the development of naturallanguage processing applications that address bilingual tasks, such as corpus-based machine translation, the automatic extraction of bilingual lexicons, and translation spotting [Simard, 2003]. A bilingual parallel corpus, or bitext, is a textual collection that contains pairs of documents which are translations of one another. In the words of Melamed [2001, p. 1], "bitexts are one of the richest sources of linguistic knowledge because the translation of a text into another language can be viewed as a detailed annotation of what that text means".

Large bitexts are usually available in a compressed form

times [Ziviani et al., 2000], and to increase the efficiency of transmissions. However, the independent compression of the two texts of a bitext is clearly far from efficient because the information contained in both texts is redundant. Previous work [Nevill-Manning and Bell, 1992; Conley and Klein, 2008; Mart´ınez-Prieto et al., 2009; Adiego et al., 2009; 2010] has shown that bitexts can be more efficiently compressed if the fact that the two texts are mutual translations is exploited.

Mart´ınez-Prieto et al. [2009], and Adiego and his colleagues [2009; 2010] propose the use of biwords -pairs of words, each one from a different text, with a high probability of co-occurrence- as input units for the compression of bitexts. This means that a biword-based intermediate representation of the bitext is obtained by exploiting alignments, and unaligned words are encoded as pairs in which one component is the empty string. Significant spatial savings are achieved with this technique [Mart´ınez-Prieto et al., 2009], although the compression of biword sequences requires larger dictionaries than the traditional text compression methods.

The biword-based compression approach works as a simple processing pipeline consisting of two stages (see Figure 1). After a text alignment has been obtained without pre-existing linguistic resources, the first stage transforms the bitext into a biword sequence. The second stage then compresses this sequence. Decompression works in reverse order: the biword sequence representing the bitext is first generated We also show that this generalization of biwords allows for the implementation of an efficient translation spotting [Simard, 2003] algorithm on the compressed bitext; a task that consists of identifying the words (or text segments) in the other text that are the translation of the words in the query. Indeed, generalized biword sequences contain all the information needed in order to retrieve connected passages.

∗This paper is an extended abstract of the JAIR publication [S´anchez-Mart´ınez et al., 2012].

Generalized biwords can also be used as an ingredient in the bilingual language model employed in some statistical machine translation systems [Koehn, 2010]. For instance, Mari˜no et al. [2006] use bilingual n-grams and consider the translation as a bilingual decoding process. Casacuberta and Vidal [2004] also exploit bilingual n-grams but apply stochastic finite-state transducers to this task. In both cases, the local reordering of words is addressed by considering multiword segments of source and target words as the fundamental translation units. Some alternative approaches [Niehues et al., 2011; Hasan et al., 2008] integrate bilingual language models as an additional feature in the decoding function that drives the statistical translation process. However, none of the approaches mentioned includes the structural information provided by the aligners as part of the bilingual language model.

In addition, the improvement in compression performance obtained when taking advantage of the fact that the two texts in a bitext are mutual translations may be regarded as an indication of the quality of word alignments [Och and Ney, 2003]. This indicator, which bounds the mutual information [Cover and Thomas, 1991] in the two texts of a bitext, does not require a manually-annotated corpus to evaluate the automatic alignment.

3 Extraction of Biword Sequences

Before extracting the sequence of biwords representing a bitext, the alignments between the words in the left text L = l1l2 · · · lM and the words in the right text R = r1r2 · · · rN

must be established. For this purpose we have used the opensource GIZA++ toolkit 1 [Och and Ney, 2003].

The result of word alignment is a bigraph G = {L,R,A} in which an edge {li, rj} ∈ A between word li ∈ L and word rj ∈ R signifies that they are mutual translations according to the translation model used by the aligner. These complex structures are processed by splitting the bigraph into connected components: each connected component is either an unpaired (right or left) word, or a left word σ aligned with a sequence ρ of (one or more) right words. A connected component including the structural information needed to place all the words in their original positions in the bitext is what we term as a generalized biword.

In order to build a sequence B of generalized biwords, biwords are sorted primarily according to their left component σ and, secondarily, by the head of their right component ρ.

Every generalized biword β = (σ, ρ, ω) in the sequence B consists of:

• a string σ in ΣL (the set of different words in the left text L enhanced with the empty word ϵ),
• an array of strings ρ in ΣR (the set of subsequences in the right text R plus the empty subsequence), and
• an integer array ω, with one offset per string in ρ, that stores the structural information needed to place each word in ρ in its original position.

Figure 3 shows the sequence of generalized biwords generated from the word-aligned sentence shown in Figure 2. The offset in the biword (casa, (house),(1)) signifies that there is a one-word gap between house and the which is occupied by the word green with offset 0 in (verde,(green),(0)). The offsets in (vivimos, (we,live), (0,0)) indicate that we comes directly after the word house and live comes immediately after we.

Henceforth, we shall call biwords with shifts those biwords with at least one non-null offset (biwords without shifts, otherwise). We shall further differentiate between biwords with simple shifts, where only the first offset is non-null, and biwords with complex shifts, with non-consecutive words in R.

4 Compression of Biword Sequences

We evaluate two different methods, namely TRE and 2LCAB, to compress the intermediate representation introduced in the previous section.

1 http://code.google.com/p/giza-pp/

The Translation Relationship-based Encoder (TRE) assigns codewords to the left word and to the sequences of right words in the biword through the use of two independent methods. The left text is encoded using word-based Huffman coding [Moffat, 1989], whereas the right text is encoded by using the left text as its context. To do this, TRE uses three dictionaries: one, ΣL, with the left words, a second one, ΣR, with the sequences of right words, and a third one, τB, which maps each word σ ∈ ΣL onto the subset of entries in ΣR with which it has been aligned in the corpus.

In contrast to TRE, the 2-Level Compressor for Aligned Bitexts (2LCAB; [Adiego et al., 2009]) encodes every biword with a single codeword based on a two-level dictionary. The first level consists of two dictionaries, ΣL and ΣR, containing the left words and the sequences of right words, respectively, that appear in the biword sequence B. The second level dictionary ΣB stores the different biwords in B as an integer sequence of alternating references to the entries in ΣL and ΣR. The text in the sequence B can then be mapped onto a sequence of references to entries in ΣB.

Both methods use prediction by partial matching (PPM; [Cleary and Witten, 1984]) to encode the dictionaries ΣL and ΣR, and encode the offsets as two streams of integer values: one with the relative positions P of the biwords with shifts in the sequence B, and another with the offset values O for the biwords with shifts. Both streams are therefore encoded by using two independent sets of Huffman codewords.

5 Compression Results

We evaluate the performance of the bitext compressors based on generalized biwords with nine different language pairs (Spanish-Catalan, es-ca; WelshEnglish, cy-en; German-English, de-en; SpanishEnglish, es-en; Spanish-French, es-fr; Spanish-Italian, es-it; Spanish-Portuguese, es-pt; French-English, fr-en; and Finnish-English, fi-en) when they are used in combination with four different methods to extract a sequence of biwords:

• 1:N Complex: the one-to-many word alignments generated by GIZA++ are used to generate a sequence of generalized biwords.
• 1:N Simple: the biwords with complex shifts generated by the one-to-many alignments provided by

GIZA++ are split into biwords with simple shifts plus unpaired words; the result is a sequence of biwords with simple shifts or without shifts.

• 1:1 Non-monotonic: one-to-one word alignments are obtained by computing the intersection of the alignments produced by GIZA++ when the left and the right text are exchanged; the result is a sequence of biwords whose right component contains, at most, one word (and these biwords cannot, therefore, have complex shifts).
• 1:1 Monotonic: the 1:1 non-monotonic sequence is transformed into a sequence of biwords without shifts by splitting biwords with shifts into unpaired words.

The last method, 1:1 Monotonic, does not use the enhancement provided by the generalization of biwords (i.e., the structural information), and is therefore equivalent to the basic procedures described earlier [Mart´ınez-Prieto et al., 2009; Adiego et al., 2009; 2010].

Both TRE and 2LCAB outperform general-purpose compressors in all cases but that of the en-fi pair. This suggests that TRE and 2LCAB take advantage of the fact that the texts contain the same information but "encoded" in different languages, particularly in the case of highly parallel bitexts (en-cy) and languages with a high syntactic correlation (es-ca). The low performance for en-fi is the consequence of the larger translation dictionaries (τB) used by TRE, and the larger bilingual dictionary (ΣB) used by 2LCAB, in comparison to the other language pairs. Furthermore, the percentage of unpaired words is also higher than that of the other language pairs.

The best results are obtained in most of the cases when one-to-one alignments are used with both techniques. This is due to the fact that the use of one-to-many alignments causes the size of the dictionary to grow considerably, particularly in the case of the biword dictionary used by 2LCAB. This side effect can be alleviated by discarding very infrequent biwords by splitting them into smaller, more frequent, biwords.

Discarding the most infrequent biwords (about two thirds of them) usually leads to an improvement in the compression ratios, except in the case of very similar languages, such as Catalan and Spanish, in which the translation is highly parallel. This effect is more important in the case of 2LCAB because the pruning leads to a large reduction in the size of the biword dictionary and this compensates the small increment in the total number of biwords needed to represent the bitext (between 5% and 10% of increment depending on the method used for its generation). With this filtering, 2LCAB and TRE obtain the best results when extracting the biword sequence with method 1:N Simple.

6 Translation Spotting with Compressed Bitexts

The exploitation of bitexts by computer-aided translation tools has evolved from simple bilingual concordancers [Bowker and Barlow, 2004] that can only provide a whole sentence as the result of a translation query, to advanced translation search engines [Callison-Burch et al., 2005a;

Bourdaillet et al., 2010] with translation spotting capabilities, i.e. they can retrieve parallel text segments in bitexts.

It would seem that existing translation search engines [Callison-Burch et al., 2005a; Bourdaillet et al., 2010] do not access bitexts in their compressed forms because storing the correspondences between the translated segments requires additional data structures such as word indexes or suffix arrays [Lopez, 2007; Callison-Burch et al., 2005b]; suffix arrays typically require four times the size of the text [Manber and Myers, 1993]. In contrast, the generalized biwords require much less space, they integrate the alignment information into the compressed bitext, and this information can be exploited to retrieve translation examples.

We apply the 2LCAB compression technique to the translation spotting task after replacing the use of Huffman codewords and PPM compression by the use of End-Tagged Dense Code (ETDC; [Brisaboa et al., 2007]), succinct data structures [Navarro and M¨akinen, 2007, Sec. 6], and directly addressable variable-length codes (DAC, [Brisaboa et al., 2009]). These changes need to be introduced to allow both direct searching and random access to the compressed text.

6.1 Translation Spotting

The searchable 2LCAB summarized above is complemented with a search algorithm which, given a single word w in the left text, proceeds as follows:

1. The word w is looked for in ΣL and its ETDC codeword c is obtained.
2. An exact pattern-matching algorithm identifies all the occurrences of the codeword c in the biword dictionary ΣB, and the codeword of the biwords where c happens to refer to the left word being looked for are added to the search set Z.
3. The multi-pattern matching algorithm SET-HORSPOOL [Horspool, 1980; Navarro and Raffinot, 2002] locates all the codewords in the sequence of biwords B that match one of those contained in Z, and the matching positions are added to a new set M.
4. For every match m ∈ M, the adjacent right component is read from B and the offsets, if any, are recovered from O and used to place the right words in the original order.

In case the query consists of a sequence of words, the SETHORSPOOL algorithm is executed only for the word in the sequence generating the smallest set of codewords to locate Z, and the remaining words are then used to filter the results once the biword context has been retrieved.

Table 1 shows an actual example of the output obtained for a multiple word query and a compressed biword sequence obtained with the 1:N Complex method. Note that the third match shows a non-contiguous translation, a case which cannot be retrieved with the original 2LCAB implementation [Adiego et al., 2009].

6.2 Experimental Evaluation

The compression ratios obtained with the searchable 2LCAB method are worse tan those obtained with the original 2LCAB

method summarized in Section 4: it achieves compression ratios which are slightly worse than those obtained with general purpose and word-based compressors. However, these compressed files include the information concerning the alignments between the words, information that is not included in the files compressed with the standard compressors but is necessary to perform translation spotting.

We have studied how the time needed to process a query depends on the language pair and also on the number and frequencies of the words in the query. The results show that the time required to process a query depends on the quality of the alignments and on the degree of parallelism of the bitexts. Poor quality alignments makes words participate in a large number of different biwords, and bitexts with a highly parallel structure make words participate only in a small number of biwords. The larger the number of biwords in which a word participates, the lower the performance of the SETHORSPOOL algorithm.

Acknowledgments

This work has been supported by the Spanish Government through projects TIN2009-14009-C02-01 and TIN200914009-C02-02.