A scalable decoder for parsing-based machine translation with equivalent language model state maintenance

We describe a scalable decoder for parsing-based machine translation. The decoder is written in JAVA and implements all the es-sential algorithms described in Chiang (2007): chart-parsing, m-gram language model inte-gration, beam- and cube-pruning, and unique k-best extraction. Additionally, parallel and distributed computing techniques are ex-ploited to make it scalable. We also propose an algorithm to maintain equivalent language model states that exploits the back-off prop-erty of m-gram language models: instead of maintaining a separate state for each distin-guished sequence of “state ” words, we merge multiple states that can be made equivalent for language model probability calculations due to back-off. We demonstrate experimentally that our decoder is more than 30 times faster than a baseline decoder written in PYTHON. We propose to release our decoder as an open-source toolkit.