Patent ID: 7711561

Claim:
A decoder for an automatic speech recognition system for determining one or more candidate text unit concatenations according to a predetermined criterion and which correspond to a speech segment, the decoder comprising: a processor arranged to receive a sequence of feature vectors corresponding to the speech segment; the processor arranged to map with different likelihood values the feature vectors to sequences of nodes in a decoding network, every sequence representing a concatenation of text units; the processor arranged to determine one or more candidate node sequences in the decoding network corresponding to the candidate text unit concatenations by implementing a dynamic programming token passing algorithm in which each token corresponds to a node and is associated with a number of text unit concatenations and likelihood values for these concatenations, wherein the plurality of candidate text unit concatenations in a token are the text unit concatenations with N-best likelihood values; tokens from different nodes that are to be passed to a common node are combined to generate a new token corresponding to the common node, said new token including a pointer to a word history structure that includes pointers to text unit concatenations from previous tokens of different nodes, and offsets indicating a difference in maximum likelihood scores between the text unit concatenations from the previous tokens; and the processor is further configured to delay a merging of the text unit concatenations in the new token to determine the N-best likelihood values until an end of the speech segment and output the one or more candidate text unit concatenations corresponding to the speech segment.