@article{chang-collins-2017-polynomial,
    title = "A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit",
    author = "Chang, Yin-Wen  and
      Collins, Michael",
    editor = "Lee, Lillian  and
      Johnson, Mark  and
      Toutanova, Kristina",
    journal = "Transactions of the Association for Computational Linguistics",
    volume = "5",
    year = "2017",
    address = "Cambridge, MA",
    publisher = "MIT Press",
    url = "https://preview.aclanthology.org/fix-sig-urls/Q17-1005/",
    doi = "10.1162/tacl_a_00046",
    pages = "59--71",
    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(nd!lhd+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."
}