Systems and methods for determining the N-best strings

A method for identifying the N-best distinct strings of an automaton, the method comprising:

• partially determinizing, via a speech recognition system, the automaton during a search for the N-best distinct strings, wherein the N-best distinct strings comprise more than one best distinct string, by creating a partially determinized automaton while searching for the N-best distinct strings by:
• creating an initial state of in the partially determinized automaton, wherein the initial state corresponds to a state pair;
• creating a transition leaving the initial state, wherein the transition has a label and a weight;
• creating a destination state for that transition, wherein the destination state corresponds to a subset of state pairs;
• creating additional states in the partially determinized automaton, wherein each additional state corresponds to a different subset of state pairs and wherein the additional states in the partially determinized automaton are connected by transitions that have labels and weights;
• and
• propagating a potential from a state of the automaton to each state in the partially determinized automaton;
• removing redundant paths;
• and
• identifying the N-best distinct strings of the automaton from the partially determinized automaton using an N-best paths process, wherein the identifying the N-best paths comprises:
• adding an initial state to the partially determinized automaton;
• creating an initialized first queue pair comprising the initial state and an initial cost element;
• placing the first queue pair in a queue;
• creating a plurality of new states from the first queue pair;
• applying a shortest path algorithm to each of the new states to calculate a shortest path of each of the new states;
• creating new queue pairs using the new states and cost elements of each new queue pair calculated via the shortest path algorithm;
• adding the new queue pairs to the queue;
• prioritizing the queue based upon a cost element of each queue pair relative to each other queue pair in the queue, wherein element a queue pair in the queue with a lower cost element is given a higher priority than a queue pair in the queue with a higher cost element;
• selecting a queue pair 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.

A method of partially determinizing an input weighted automaton to identify the N-best strings of the input weighted automaton where the input weighted automaton comprises input states and input transitions, wherein the input transitions interconnect the input states to form a plurality of complete paths from any one member of a set of beginning input states to any one member of a set of final input states, wherein each of the input transitions comprises a label and a weight, the method comprising:

• creating a deterministic automaton, via a speech recognition system, by:
• forming determinized states and determinized transitions in an order dictated by an N-shortest paths algorithm to create N complete paths using only a part of the input weighted automaton;
• and
• interconnecting the determinized states and determinized transitions to form complete paths;
• removing redundant paths;
• and
• identifying the N-best strings of the input weighted automaton by searching for the N-best complete paths of the deterministic automaton, wherein the N-best complete paths comprise more than one best complete path, wherein the identifying the N-best strings comprises:
• adding an initial state to the deterministic automaton;
• creating an initialized first queue pair comprising the initial state and an initial cost element;
• placing the first queue pair in a queue;
• creating a plurality of new states from the first queue pair;
• applying a shortest path algorithm to each of the new states to calculate a shortest path of each of the new states;
• creating new queue pairs using the new states and cost elements of each new queue pair calculated via the shortest path algorithm;
• adding the new queue pairs to the queue;
• prioritizing the queue based upon a cost element of each queue pair relative to each other queue pair in the queue, wherein a queue pair in the queue with a lower cost element is given a higher priority than a queue pair in the queue with a higher cost element;
• selecting a queue pair 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.