Speech recognition using a state-and-transition based binary speech grammar with a last transition value

• US 7,571,096 B2
• Filed: 09/18/2007
• Issued: 08/04/2009
• Est. Priority Date: 07/20/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schmid, Philipp H., Lipe, Ralph
• Primary Examiner(s): Smits; Talivaldis Ivars
• Application Number:
  US11/857,018
• Publication Number:
  US 20080046242A1
• Time in Patent Office: 686 Days
• Field of Search: 704/9, 704/252, 704/255
• US Class Current: 704/255
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 15/28 Constructional details of speech recognition systems
• CPC Class Codes: H04L 65/1101 Session protocols

Abstract

A computer-loadable data structure is provided that represents a state-and-transition-based description of a speech grammar. The data structure includes first and second transition entries that both represent transitions from a first state. The second transition entry is contiguous with the first transition entry in the data structure and includes a last-transition value. The last-transition value indicates that the second transition is the last transition from the first state in the data structure.

Claims

1. A computer-readable storage medium having encoded thereon computer-executable instructions that cause a processor to perform steps comprising:

receiving a speech signal;

accessing a data structure stored in memory to identify possible transitions from a state, the data structure representing a state-and-transition-based description of a speech grammar, the data structure comprising;

a first transition entry representing a transition from a first state;

a second transition entry representing a second transition from the first state, the second transition entry being contiguous with the first transition entry and having a last-transition value set to indicate that the second transition is the last transition from the first state;

using the possible transitions from a state stored in the data structure to identify sequences of phonetic units represented by the speech signal.

2. The computer-readable storage medium of claim 1 wherein each transition entry has a fixed size.

3. The computer-readable storage medium of claim 2 wherein the data structure further comprises a word string comprising words found in the speech grammar.

4. The computer-readable storage medium of claim 3 wherein each transition entry has a content index value that designates content associated with the transition.

5. The computer-readable storage medium of claim 4 wherein at least one transition entry has a content index value that is an index into the word string.

6. A method comprising:

providing a speech signal to a speech recognition engine executed by a processor;

reading a next transition index from a transition entry in a state-and-transition-based binary grammar stored in a system memory accessible by the processor;

reading information from each transition entry from the transition entry indexed by the next transition index to a transition entry that includes a last field flag that indicates that it is the last transition entry for a state, to obtain information for each transition that extends from the state; and

using the information read from the transition entries to decode the speech signal into text.

7. The method of claim 6 wherein reading information from a transition entry comprises reading a content index value.

8. The method of claim 6 wherein reading information from a transition entry further comprises reading a rule ref field that indicates whether the content index value is an index to a word or an index to a rule.

9. The method of claim 8 wherein the content index value is an index to a word in a word string.

10. The method of claim 8 wherein the content index value is an index to a rule in a set of rule entries.

11. The method of claim 6 wherein each transition entry has a fixed size.