Method and system to generate finite state grammars using sample phrases

• US 8,712,775 B1
• Filed: 01/31/2013
• Issued: 04/29/2014
• Est. Priority Date: 08/26/2004
• Status: Active Grant

• Current Assignee: Intrado Interactive Services Corp.
• Original Assignee: West Interactive Corporation (West Corporation)
• Inventors: Khosla, Ashok Mitter
• Primary Examiner(s): Armstrong, Angela A
• Application Number:
  US13/755,016
• Time in Patent Office: 453 Days
• Field of Search: 704/9, 704/236, 704/251, 704/257, 704/270
• US Class Current: 704/257
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A method and system for generating a finite state grammar is provided. The method comprises receiving user input of at least two sample phrases; analyzing the sample phrases to determine common words that occur in each of the sample phrases and optional words that occur in only some of the sample phrases; creating a mathematical expression representing the sample phrases, the expression including each word found in the sample phrases and an indication of whether a word is a common word or an optional word; displaying the mathematical expression to a user; allowing the user to alter the mathematical expression; generating a finite state grammar corresponding to the altered mathematical expression; and displaying the finite state grammar to the user.

Claims

1. A method, comprising:

receiving input of a plurality of sample phrases each comprising a plurality of words;

representing each sample phrase as a node in a tree;

forming a mathematical expression for each pair of nodes in the tree, the mathematical expression comprising a plurality of words found in the sample phrases of a pair of nodes and an indication of whether a word is a common word that occurs in each of the plurality of phrases or an optional word that occurs in some of the plurality of phrases for the pair of nodes; and

generating a compact mathematical expression by comparing mathematical expressions, wherein the compact mathematical expression includes each of the plurality of words found in the sample phrases and an indication of whether each of the plurality of words is a common word or an optional word.

2. The method of claim 1 comprising allowing the compact mathematical expression to be altered.

3. The method of claim 2 comprising generating a finite state grammar corresponding to the altered compact mathematical expression.

4. The method of claim 2, wherein allowing the compact mathematical expression to be altered comprises receiving inputs from at least one of:

adding a word to the mathematical expression, deleting a word from the mathematical expression, making a common word in the mathematical expression optional; and

making an optional word in the mathematical expression common.

5. The method of claim 1 comprising receiving input of further sample phrases.

6. The method of claim 1 comprising forming the mathematical expression for each pair of nodes in the tree to represent the sample phrases associated with the pair of nodes.

7. A non-transitory computer-readable storage medium comprising instructions for:

receiving input of a plurality of sample phrases each comprising a plurality of words;

representing each sample phrase as a node in a tree;

forming a mathematical expression for each pair of nodes in the tree, the mathematical expression comprising a plurality of words found in the sample phrases of the pair of nodes and an indication of whether a word is a common word that occurs in each of the plurality of phrases or an optional word that occurs in some of the plurality of phrases for the pair of nodes; and

generating a compact mathematical expression by comparing mathematical expressions, wherein the compact mathematical expression includes each of the plurality of words found in the sample phrases and an indication of whether each of the plurality of words is a common word or an optional word.

8. The non-transitory computer-readable storage medium of claim 7 comprising instructions for allowing the compact mathematical expression to be altered.

9. The non-transitory computer-readable storage medium of claim 8 comprising instructions for generating a finite state grammar corresponding to the altered compact mathematical expression.

10. The non-transitory computer-readable storage medium of claim 8, wherein allowing the compact mathematical expression to be altered comprises instructions for receiving inputs from at least one of:

adding a word to the mathematical expression, deleting a word from the mathematical expression, making a common word in the mathematical expression optional; and

making an optional word in the mathematical expression common.

11. The non-transitory computer-readable storage medium of claim 7 comprising instructions for receiving input of further sample phrases.

12. The non-transitory computer-readable storage medium of claim 7, wherein the forming of the mathematical expression for each pair of nodes in the tree represents the sample phrases associated with the pair of nodes.

13. A system, comprising:

a processor; and

a memory coupled to the processor;

wherein the processor is configured to;

receive input of a plurality of sample phrases each comprising a plurality of words;

represent each sample phrase as a node in a tree;

form a mathematical expression for each pair of nodes in the tree, the mathematical expression comprising a plurality of words found in the sample phrases of the pair of nodes and an indication of whether a word is a common word that occurs in each of the plurality of phrases or an optional word that occurs in some of the plurality of phrases for the pair of nodes; and

generate a compact mathematical expression by comparing mathematical expressions, wherein the compact mathematical expression includes each of the plurality of words found in the sample phrases and an indication of whether each of the plurality of words is a common word or an optional word.

14. The system of claim 13, wherein the processor is configured to allow the compact mathematical expression to be altered.

15. The system of claim 14, wherein the processor is configured to generate a finite state grammar corresponding to the altered compact mathematical expression.

16. The system of claim 14, wherein the processor is configured to allow the compact mathematical expression to be altered comprises receipt of an input from at least one of:

a word added to the mathematical expression, a word deleted from the mathematical expression, a common word made in the mathematical expression optional; and

an optional word made in the mathematical expression common.

17. The system of claim 13, wherein the processor is configured to receive input of further sample phrases.

18. The system of claim 13, wherein the mathematical expression for each pair of nodes in the tree is formed to represent the sample phrases associated with the pair of nodes.