Efficient search strategies in hierarchical pattern recognition systems
N. Deshmukh, J. Picone, Yu‐Hung Kao · 2002
We describe the generalized N-best search algorithm as applied to hierarchical pattern recognition, and discuss its limitations for a broad class of problems. We then introduce a new algorithm, called the Frame-Synchronous Viterbi Search, that prunes hypotheses by actively organizing system memory after each step in the search. This algorithm is shown to save memory and computation for a specific class of problems involving large search spaces and small memory resources. We also discuss generalizations of this algorithm to provide true N-best scoring and intelligent pruning while preserving the hierarchical structure of the hypotheses. An example of a practical speech recognition system using this algorithm is given.>