An approximation algorithm for word-replacement using a bi-gram language model

This paper presents an approximation algorithm for word-replacement under a bi-gram language model. Words replacement is an key step in the decoding part of statistical machine translation. However, the word or phrase replacement step is often done at the same time with the target language generating process in machine translation while our algorithm focus on the special replacement model without the target language generating process. We firstly make a reduction from the famous NP-Complete problem Hamiltonian Path Problem to the word-replacement problem. Then we apply the approximation algorithm for Hamiltonian Path on the word-replacement problem, which gives us a good performance in the designed experiment.