{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:61621"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:61621","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Word re-ordering and dynamic programming based search algorithm for statistical machine translation","abstract":"In this work, a new search procedure for statistical machine translation (SMT) is proposed that is based on dynamic programming (DP). The starting point is a DP solution to the traveling salesman problem that works by jointly processing tours that visit the same subset of cities. For SMT, the cities correspond to source sentence positions to be translated. Imposing restrictions on the order in which the source positions are translated yields a DP algorithm for carrying out the word re-ordering in SMT efficiently. A simple data-driven search organization allows the algorithm to prune unlikely translation hypotheses. Search restrictions especially useful for the translation directions German-to-English and English-to-German are presented. A generalization of these re-ordering restrictions is given that is applicable to several different translation directions. Translation results are reported with a widely used SMT model.","abstract_html":"In this work, a new search procedure for statistical machine translation (SMT) is proposed that is based on dynamic programming (DP). The starting point is a DP solution to the traveling salesman problem that works by jointly processing tours that visit the same subset of cities. For SMT, the cities correspond to source sentence positions to be translated. Imposing restrictions on the order in which the source positions are translated yields a DP algorithm for carrying out the word re-ordering in SMT efficiently. A simple data-driven search organization allows the algorithm to prune unlikely translation hypotheses. Search restrictions especially useful for the translation directions German-to-English and English-to-German are presented. A generalization of these re-ordering restrictions is given that is applicable to several different translation directions. Translation results are reported with a widely used SMT model.","abstract_has_math":false,"creators":["Tillmann, Christoph"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Ney, Hermann"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2001,"date_issued":"2001","date_published":"2001","updated_at":"2026-07-30T19:43:10Z","subjects":["info:eu-repo/classification/ddc/004","Informatik","Automatische Übersetzung","Wortproblem","Dynamische Optimierung"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123264%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123264%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123264%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/61621","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ney, Hermann"]},{"key":"dc:creator","label":"Author","values":["Tillmann, Christoph"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2001"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-3134"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/004","Informatik","Automatische Übersetzung","Wortproblem","Dynamische Optimierung"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/61621","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123264%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this work, a new search procedure for statistical machine translation (SMT) is proposed that is based on dynamic programming (DP). The starting point is a DP solution to the traveling salesman problem that works by jointly processing tours that visit the same subset of cities. For SMT, the cities correspond to source sentence positions to be translated. Imposing restrictions on the order in which the source positions are translated yields a DP algorithm for carrying out the word re-ordering in SMT efficiently. A simple data-driven search organization allows the algorithm to prune unlikely translation hypotheses. Search restrictions especially useful for the translation directions German-to-English and English-to-German are presented. A generalization of these re-ordering restrictions is given that is applicable to several different translation directions. Translation results are reported with a widely used SMT model."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University VIII, 134 S. : graph. Darst. (2001). = Aachen, Techn. Hochsch., Diss., 2001"]},{"key":"dc:title","label":"Title","values":["Word re-ordering and dynamic programming based search algorithm for statistical machine translation"]}]}],"canonical_facts":{"dc:contributor":["Ney, Hermann"],"dc:coverage":["DE"],"dc:creator":["Tillmann, Christoph"],"dc:date":["2001"],"dc:description":["In this work, a new search procedure for statistical machine translation (SMT) is proposed that is based on dynamic programming (DP). The starting point is a DP solution to the traveling salesman problem that works by jointly processing tours that visit the same subset of cities. For SMT, the cities correspond to source sentence positions to be translated. Imposing restrictions on the order in which the source positions are translated yields a DP algorithm for carrying out the word re-ordering in SMT efficiently. A simple data-driven search organization allows the algorithm to prune unlikely translation hypotheses. Search restrictions especially useful for the translation directions German-to-English and English-to-German are presented. A generalization of these re-ordering restrictions is given that is applicable to several different translation directions. Translation results are reported with a widely used SMT model."],"dc:identifier":["https://publications.rwth-aachen.de/record/61621","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123264%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-3134"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University VIII, 134 S. : graph. Darst. (2001). = Aachen, Techn. Hochsch., Diss., 2001"],"dc:subject":["info:eu-repo/classification/ddc/004","Informatik","Automatische Übersetzung","Wortproblem","Dynamische Optimierung"],"dc:title":["Word re-ordering and dynamic programming based search algorithm for statistical machine translation"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:43:10Z"}