Paper: Greedy Decoding For Statistical Machine Translation In Almost Linear Time

ACL ID N03-1010
Title Greedy Decoding For Statistical Machine Translation In Almost Linear Time
Venue Human Language Technologies
Session Main Conference
Year 2003
Authors
  • Ulrich Germann (University of Southern California, Marina del Rey CA)

We present improvements to a greedy decod- ing algorithm for statistical machine translation that reduce its time complexity from at least cubic (a0a2a1a4a3a6a5a8a7 when applied na¨ıvely) to prac- tically linear time1 without sacrificing trans- lation quality. We achieve this by integrat- ing hypothesis evaluation into hypothesis cre- ation, tiling improvements over the translation hypothesis at the end of each search iteration, and by imposing restrictions on the amount of word reordering during decoding.