Efficient Phrase-Table Representation for Machine Translation with Applications to Online MT and Speech Translation

Proceedings of NAACL HLT 2007, pages 492–499, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Efficient Phrase-table Representation for Machine Translation with Applications to Online MT and Speech Translation Richard Zens and Hermann Ney Human Language Technology and Pattern Recognition Lehrstuhl f¨ur Informatik 6 – Computer Science Department RWTH Aachen University, D-52056 Aachen, Germany {zens,ney}@cs.rwth-aachen.de Abstract In phrase-based statistical machine transla- tion, the phrase-table requires a large amount of memory. We will present an efficient repre- sentation with two key properties: on-demand loading and a prefix tree structure for the source phrases. We will show that this representation scales well to large data tasks and that we are able to store hundreds of millions of phrase pairs in the phrase-table. For the large Chinese– English NIST task, the memory requirements of the phrase-table are reduced to less than 20 MB using the new representation with no loss in translation quality and speed. Addi- tionally, the new representation is not limited to a specific test set, which is important for online or real-time machine translation. One problem in speech translation is the matching of phrases in the input word graph and the phrase-table. We will describe a novel algorithm that effectively solves this com- binatorial problem exploiting the prefix tree data structure of the phrase-table. This algo- rithm enables the use of significantly larger input word graphs in a more efficient way re- sulting in improved translation quality. 1 Introduction In phrase-based statistical machine translation, a huge number of source and target phrase pairs is memorized in the so-called phrase-table. For medium sized tasks and phrase lengths, these phrase-tables already require several GBs of mem- ory or even do not fit at all. If the source text, which is to be translated, is known in advance, a common trick is to filter the phrase-table and keep a phrase pair only if the source phrase occurs in the text. This filtering is a time-consuming task, as we have to go over the whole phrase-table. Furthermore, we have to repeat this filtering step whenever we want to translate a new source text. To address these problems, we will use an ef- ficient representation of the phrase-table with two key properties: on-demand loading and a prefix tree structure for the source phrases. The prefix tree structure exploits the redundancy among the source phrases. Using on-demand loading, we will load only a small fraction of the overall phrase-table into memory. The majority will remain on disk. The on-demand loading is employed on a per sen- tence basis, i.e. we load only the phrase pairs that are required for one sentence into memory. There- fore, the memory requirements are low, e.g. less than 20 MB for the Chin.-Eng. NIST task. Another ad- vantage of the on-demand loading is that we are able to translate new source sentences without filtering. A potential problem is that this on-demand load- ing might be too slow. To overcome this, we use a binary format which is a memory map …

Content truncated to 500 words