An efficient A* search algorithm for statistical machine translation
Franz Josef Och, Nicola Ueffing, Hermann Ney · 2001
In this paper, we describe an efficient A* search algorithm for statistical machine translation. In contrary to beam-search or greedy approaches it is possible to guarantee the avoidance of search errors with A*. We develop various so-phisticated admissible and almost admissible heuristic functions. Especially our newly developped method to perform a multi-pass A* search with an iteratively improved heuristic function allows us to translate even long sentences. We compare the A* search algorithm with a beam-search approach on the Hansards task.