Beam search is employed to decrease the computational
cost[5]. In Viterbi search, at each time
, we compute the probability of all possible
combinations. In comparison, with the beam search
algorithm, we only compute the probability of the most
likely word combinations within a beam width
.
Assuming a large enough beam width, the globally optimal
Viterbi path will exist within that beam width. The
complexity of the beam search algorithm is
. So the memory requirement and the calculation
cost are reduced by
.