A tree-trellis based fast search for finding the N-best sentence hypotheses in continuous speech recognition

A novel tree-trellis based fast search for finding the N-best sentence hypotheses in continuous speech recognition is presented. The search consists of a forward time-synchronous trellis search and a backward time-asynchronous tree search. The Viterbi algorithm is used for recording the scores of all partial paths in a trellis time synchronously. Then a backward A* algorithm based tree search is used to extend partial paths time asynchronously. Extended partial paths in the backward tree search are rank ordered in a stack by their corresponding best possible scores of the remaining paths which are prerecorded in the forward trellis path map. In each path growing cycle, the current best partial path, which is at the top of the stack, is extended by the best possible one arc (word) extension. The tree-trellis search is different from the traditional time synchronous Viterbi search in its ability to find not just the best but the N best paths of different word content