A Breadth-First Representation for Tree Matching in Large Scale Forest-Based Translation

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 785–793, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP A Breadth-First Representation for Tree Matching in Large Scale Forest-Based Translation Sumukh Ghodke Steven Bird Rui Zhang Department of Computer Science and Software Engineering University of Melbourne, Victoria 3010, Australia {sghodke,sb,rui}@csse.unimelb.edu.au Abstract Efficient data structures are necessary for searching large translation rule dictionar- ies in forest-based machine translation. We propose a breadth-first representation of tree structures that allows trees to be stored and accessed efficiently. We de- scribe an algorithm that allows incremen- tal search for trees in a forest and show that its performance is orders of magni- tude faster than iterative search. A B-tree index is used to store the rule dictionar- ies. Prefix-compressed indexes with a large page size are found to provide a bal- ance of fast search and disk space utilisa- tion. 1 Introduction Statistical machine translation (SMT) uses ma- chine learning and parallel corpora to perform translations automatically. Syntax based SMT systems can be broadly classified into two types based on the input to the system: tree-based and string-based (Mi et al., 2008). In a tree-based sys- tem, the input is a parse tree of the source lan- guage, whereas in the latter, the input is a sequence of words that is simultaneously parsed and trans- lated. Forest-based translation employs multiple parse trees for each source language sentence. Forest-based translation can be performed in three main steps. First, the input sentence is parsed into a packed forest, which is then pruned. Next, for each tree in the packed forest, all matching translation rules are found. These translation rules are then combined to form a translation forest. The translation forest is finally decoded to produce a sentence in the target language. The second step – finding all matching trans- lation rules for each tree in the source sentence forest – is a complex task in itself. It could be performed by enumerating all trees in the forest and then searching for those trees in the transla- tion rule dictionary. Of the enumerated trees, those that are present in the rule dictionary produce the translation forest. However, enumerating all pos- sible trees from a forest incurs an exponential cost and many or most of those generated trees may not exist in the rule dictionary. Hence, a com- mon approach in MT research is to perform the inverse task, and iterate over all the rules to check whether each rule matches anywhere in the source forest. This is a relatively easy task, especially if the rule dictionary is not large. In experimen- tal setups a subset of rules may be used based on the prior knowledge of the rules required for the given test sentences. While that method works for research experiments on translation methods, no prior knowledge is available for online MT sys- tems, and iterating over all rules will not be effi- cient for large rule dictionaries. Another method used to quicken …

Content truncated to 500 words