Browse Prior Art Database

New Heuristics to Reduce Search Effort in a Speech Decoder

IP.com Disclosure Number: IPCOM000113865D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 64K

Publishing Venue

IBM

Related People

Gopalakrishnan, PS: AUTHOR [+4]

Abstract

This invention presents new heuristic algorithms for the stack search which reduce the computation time in the decoder.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

New Heuristics to Reduce Search Effort in a Speech Decoder

      This invention presents new heuristic algorithms for the stack
search which reduce the computation time in the decoder.

      In the Tangora speech recognition system the computation of the
maximum likelihood sentence is carried out using a stack search
algorithm.  Each iteration of this algorithm begins with the
selection of the next path to be extended.  For this path a fast
match calculation is done to obtain a list of candidate words and
then these candidate words are passed to the detailed match module to
compute the detailed acoustic score.  The fast match and detailed
acoustic match scores are then combined with the language model score
to obtain the final score which is used to rank the paths for further
processing.  For large vocabulary systems, a major part of the
computation effort is in the fast match and a comparable effort is
required to compute the detailed match score for all the words.  This
invention describes a heuristic for reducing the computation effort
in the detailed match by using the information available from the
fast match computation.

      Select a path for expansion using the usual method for
selecting the best path lbracket 1 rbracket .  Expand the path using
the following algorithm:
  1.  Call the fast match to get a list of candidate words.  Let
      this list be W sub 1, W sub 2, ellipsis, W sub C.  Moreover,
      let this list be sorted in descending order of combined
      acoustic fast match and language model scores.
  2.  Initialize counts L and G to zero.
  3.  Do the following steps for i = 1 to C
      a.  Compute the detailed match score for word W sub i.
          After the detailed acoustic match,  compute the
          combined score S sub i for word W sub i by combining
        ...