We use a variant of the DAG-SHORTEST-PATH algorithm [18]. This algorithm finds shortest paths for uniformly weighted directed acyclic graphs. The first step of the algorithm is a topological sort of the vertices of the graph. It turns out that the state names of the word-graph that we obtain from the speech recogniser are already topologically sorted: state names are integers, and edges always connect to larger integers. The second step of the algorithm maintains an array A which records for each state v_{k} the weight associated with the best path known from v_{0} to v_{k}. A similar array, P, is used to represent for each state the history of this best path, as a sequence of QLFs (since that is what we want to obtain eventually).
The first step of the algorithm initialises these arrays such that
for each state
, and
. For v_{0} we specify
and
. After this initialisation phase the algorithm
treats each edge of the graph in topologically sorted order of the
source vertex, as follows:
(34) |
The function relax is defined on edges and updates the arrays if
a better path to a vertex has been found:
(35) |
A simple generalisation of the algorithm has been implemented in order to obtain the N best solutions. In this case we maintain in the algorithm for each vertex the N best paths found so far. Such a generalisation increases the worst-case complexity by only a constant factor, and is very useful for development work.