Greedy Decoding for Statistical Machine Translation in Almost Linear Time

We present improvements to a greedy decoding algorithm for statistical machine translation that reduce its time complexity from at least cubic (O(n6) when applied naively) to practically linear time1 without sacrificing translation quality. We achieve this by integrating hypothesis evaluation into hypothesis creation, 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.