# A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit

### Venue

Transactions of the Association for Computational Linguistics (TACL), vol. 5 (2017), pp. 59-71

### Publication Year

2017

### Authors

Yin-Wen Chang, Michael Collins

### BibTeX

## Abstract

Decoding of phrase-based translation models in the general case is known to be NP
complete, by a reduction from the traveling salesman problem (Knight, 1999). In
practice, phrase-based systems often impose a hard distortion limit that limits the
movement of phrases during translation. However, the impact on complexity after
imposing such a constraint is not well studied. In this paper, we describe a
dynamic programming algorithm for phrase-based decoding with a fixed distortion
limit. The runtime of the algorithm is O(n d! l h^{d+1}) where n is the sentence
length, d is the distortion limit, l is a bound on the number of phrases starting
at any position in the sentence, and h is related to the maximum number of target
language translations for any source word. The algorithm makes use of a novel
representation that gives a new perspective on decoding of phrase-based models.