Compact easily parseable binary format for a context-free grammer

• US 7,024,350 B2
• Filed: 02/07/2001
• Issued: 04/04/2006
• 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): Dorvil, Richemond
• Assistant Examiner(s): SHORTLEDGE, THOMAS E
• Application Number:
  US09/778,479
• Publication Number:
  US 20020123881A1
• Time in Patent Office: 1,882 Days
• Field of Search: 704/9, 704/257, 704/4, 704/236, 704/1, 704/10
• US Class Current: 704/9
• 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 indicating that the second transition is the last transition from the first state in the data structure. A method is also provided for retrieving information from a binary grammar. The method includes receiving an index into a set of transition entries and converting the index into a memory offset relative to the beginning of the binary grammar, where the offset is based on a memory offset to the beginning of the set of transition entries, the fixed size of each transition entry and the index.

Claims

1. A computer-readable medium providing a computer-loadable data structure representing a state-and-transition-based description of a speech grammar, the data structure comprising:

rule entries, each rule entry representing a group of transitions;

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

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,

wherein at least one transition entry has a content index value that is an index to a rule entry in the rule entries.

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

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

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

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

6. The computer-readable medium of claim 5 wherein each transition entry further comprises a rule reference flag field that indicates whether the content index value is an index into the word string or an index to a rule entry.

7. The computer-readable medium of claim 1 wherein each rule entry is a fixed size as all other rule entries.

8. The computer-readable medium of claim 7 wherein each rule entry comprises a starting transition value that provides an index to a transition entry that represents the first transition for the rule.

9. A computer-readable medium that provides a computer-loadable data structure representing a speech grammar, the data structure comprising:

a string of words containing words in the speech grammar; and

a set of fixed size transition entries, each transition entry representing a transition in a structure that describes the speech grammar and each transition entry having a same fixed size as all other transition entries in the set of transition entries, at least one transition entry making reference to a word in the string of words.

10. The computer-readable medium of claim 9 wherein the data structure further comprises:

a set of fixed size rule entries, each rule entry representing a collection of transitions in the structure, each rule entry having the same fixed size as other rule entries and each entry including an index to a transition entry that represents the first transition in the collection of transitions.

11. The computer-readable medium of claim 9 wherein each transition entry comprises a last transition flag that indicates whether the transition for the transition entry is the last transition from a state in the structure.

12. The computer-readable medium of claim 9 wherein each transition entry comprises a semantic tag flag that indicates whether semantic information is associated with the transition for the transition entry.

13. The computer-readable medium of claim 12 wherein the data structure further comprises:

a string of symbols comprising text representing semantic tags and semantic values; and

a set of fixed size semantic entries, at least one semantic entry making reference to a semantic tag in the string of symbols.

14. The computer-readable medium of claim 9 wherein each transition entry comprises a next transition field that provides an index to a transition entry that represents a next transition in the structure.

15. A computer-readable medium providing a computer loadable 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;

a symbol string formed of a sequence of symbols; and

a set of semantic entries, each semantic entry representing semantic information associated with a transition in the grammar and each semantic entry comprising a name offset that provides an offset to a symbol in the symbol string, the symbol identified by the offset representing a semantic tag.

16. The computer-readable medium of claim 15 wherein each semantic entry further comprises a transition index value that provides an index to a transition entry that represents the transition associated with the semantic information of the semantic entry.