{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T14:02:29Z","timestamp":1769090549155,"version":"3.49.0"},"reference-count":1,"publisher":"MIT Press - Journals","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["TACL"],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p> 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( nd! lh<jats:sup> d+1<\/jats:sup>) 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. <\/jats:p>","DOI":"10.1162\/tacl_a_00046","type":"journal-article","created":{"date-parts":[[2018,12,28]],"date-time":"2018-12-28T15:42:50Z","timestamp":1546011770000},"page":"59-71","source":"Crossref","is-referenced-by-count":2,"title":["A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based                     Decoding with a Fixed Distortion Limit"],"prefix":"10.1162","volume":"5","author":[{"given":"Yin-Wen","family":"Chang","sequence":"first","affiliation":[{"name":"Google Research, New York,"}]},{"given":"Michael","family":"Collins","sequence":"additional","affiliation":[{"name":"Google Research, New York,"}]}],"member":"281","reference":[{"issue":"3","key":"p_17","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1287\/opre.31.3.507","volume":"31","author":"Donald Ratliff H","year":"1983","journal-title":"Operations Research"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:38:06Z","timestamp":1615585086000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/43391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":1,"alternative-id":["10.1162\/tacl_a_00046"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00046","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}