There are two methods to prune the beam width.
In most case, a method that selects the beam width with
some threshold is used. Such a method is computationally
cheap. But the threshold must be determined before
recognition[1]. Therefore, under some recognition
conditions, the output is faulty. A method that selects
a fixed beam width, on the other hand, requires
to be sorted for each frame. This
method requires a lot of computation. However,
need not be fully sorted, if only the
values of the best
likelihoods are calculated, and
the other likelihood values are subsequently pruned.
Concretely, if the maximum beam width is
, this
calculation is only of order
, which is
not too costly.