Patent ID: 8234115

Claim:
A method for finding N-best distinct hypotheses of an input automaton, the method comprising: computing, via a speech recognition system, an input potential for each state of the input automaton to a set of final states, wherein the input potential is used to determine a determinized potential of each state in a result of determinization and wherein the determinized potential of a particular state in the result of determinization is determined without fully determinizing the input automaton; removing redundant paths; and identifying N-best distinct paths in the result of determinization of the input automaton, by computing the result of determinization using the determinized potential of the states in the result of determinization, wherein the N-best distinct paths of the result of determinization comprise more than one best path and are labeled with the N-best hypotheses of the input automaton, wherein the computing the result of determinization comprises: creating a new state in the result of determinization; creating a new transition from a previous state to the new state in the result of determinization, wherein the new transition has a label that is the same as a label from a transition of the input automaton; creating a subset of state pairs that correspond to the new state, wherein each pair includes a state from the input automaton and a remainder weight, wherein creating a subset of state pairs further comprises constructing a pair for each destination state of the transition in the input automaton, wherein each pair includes a state of the input automaton and a remainder weight; and determining a determinized potential for the new state using an input potential from a state of the input automaton; wherein the identifying the N-best distinct paths comprises: adding an initial state to the determinized input automaton; creating an initialized first queue pair comprising a state and an initial cost element; placing the first queue pair in a queue; creating one or more new states from the first queue pair; applying a shortest path algorithm to each of the one or more new states to calculate a shortest path of each of the one or more new states; creating new queue pairs using the one or more new states and cost elements calculated via the shortest path algorithm; adding the new queue pairs to the queue; prioritizing all elements in the queue based upon a cost element of each queue pair relative to each other queue pair in the queue, wherein an element in the queue with a lower cost element is given a higher priority than another element in the queue with a higher cost element, wherein the cost element of each queue pair is associated with a path; selecting queue pairs from the queue with a highest priority; incrementing a pair counter; and determining whether a value of the pair counter is equal to a desired number of best paths.