Processing natural language grammar

• US 8,666,729 B1
• Filed: 02/10/2010
• Issued: 03/04/2014
• Est. Priority Date: 02/10/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: West Corporation
• Inventors: Schanbacher, Steven John
• Primary Examiner(s): GUERRA-ERAZO, EDGAR X
• Application Number:
  US12/703,435
• Time in Patent Office: 1,483 Days
• Field of Search: 704/9, 704/10, 704/270, 704/270.1, 704/275, 704/4, 704/5, 704/6, 704/251, 704/252, 704/253, 704/254
• US Class Current: 704/9
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence

Abstract

Creating and processing a natural language grammar set of data based on an input text string are disclosed. The method may include tagging the input text string, and examining, via a processor, the input text string for at least one first set of substitutions based on content of the input text string. The method may also include determining whether the input text string is a substring of a previously tagged input text string by comparing the input text string to a previously tagged input text string, such that the substring determination operation determines whether the input text string is wholly included in the previously tagged input text string.

Claims

1. A method of creating a natural language grammar set of data based on an input text string, the method comprising:

tagging the input text string;

examining, via a processor, the input text string for at least one first set of substitutions based on content of the input text string; and

determining whether the input text string is a substring of a previously tagged input text string by comparing the input text string to a previously tagged input text string, wherein the substring determination operation determines whether the input text string is wholly included in the previously tagged input text string, wherein if the input text string is determined to be a substring of a previously tagged input text string, then

determining whether the input text string and the at least one additional input text string share a common pre-assigned tag identifier stored in a memory location, and

wherein if the input text string and the at least one additional input text string share the common pre-assigned tag identifier stored in the memory location, then

eliminating at least one of the input text string and the at least one additional input text string from the natural language grammar.

2. The method of claim 1, further comprising:

performing the at least one first set of substitutions by expanding the input text string to create at least one additional input text string that includes at least one portion of the input text string and at least one additional portion not previously part of the input text string.

3. The method of claim 2, wherein each of the at least one additional input text string contains words that are the same as the input text string except at least one word has been removed from the input text string and has been replaced by a different word in the at least one additional input text string.

4. The method of claim 1, wherein eliminating at least one of the input text string and the at least one additional input text string from the natural language grammar comprises determining which comprises a longer input text string and eliminating that which is a longer input text string among the input text string and the at least one additional input text string.

5. The method of claim 1, wherein if the input text string and the at least one additional input text string do not share a common pre-assigned tag identifier stored in the memory location, then maintaining the input text string and the at least one additional input text string in the natural language grammar by writing both the input text string and at least one additional input text string to a source code stored in the memory location.

6. The method of claim 1, wherein the input text string is a plurality of text strings each of which are examined, via the processor for the at least one first set of substitutions based on content of the additional input text strings, and wherein at least one of the plurality of input text strings are used to generate a grammar source code file.

7. An apparatus configured to create a natural language grammar set of data based on an input text string, the apparatus comprising:

a processor configured to

tag the input text string,

examine the input text string for at least one first set of substitutions based on content of the input text string, and

determine whether the input text string is a substring of a previously tagged input text string by comparing the input text string to a previously tagged input text string, wherein the substring determination operation determines whether the input text string is wholly included in the previously tagged input text string,

wherein if the input text string is determined to be a substring of a previously tagged input text string, then

determine whether the input text string and the at least one additional input text string share a common pre-assigned tag identifier stored in a memory location, and

wherein if the input text string and the at least one additional input text string share the common pre-assigned tag identifier stored in the memory location, then

eliminate at least one of the input text string and the at least one additional input text string from the natural language grammar.

8. The apparatus of claim 7, wherein the processor is further configured to perform the at least one first set of substitutions by expanding the input text string to create at least one additional input text string that includes at least one portion of the input text string and at least one additional portion not previously part of the input text string.

9. The apparatus of claim 8, wherein each of the at least one additional input text string contains words that are the same as the input text string except at least one word has been removed from the input text string and has been replaced by a different word in the at least one additional input text string.

10. The apparatus of claim 7, further comprising:

a memory location configured to store a pre-assigned tag identifier.

11. The apparatus of claim 10, wherein eliminating at least one of the input text string and the at least one additional input text string from the natural language grammar comprises determining which is a longer input text string and eliminating that which is a longer input text string among the input text string and the at least one additional input text string.

12. The apparatus of claim 10, wherein if the input text string and the at least one additional input text string do not share a common pre-assigned tag identifier stored in the memory location, then maintaining the input text string and the at least one additional input text string in the natural language grammar by writing both the input text string and at least one additional input text string to a source code stored in the memory location.

13. The apparatus of claim 7, wherein the input text string is a plurality of text strings each of which are examined, via the processor for the at least one first set of substitutions based on content of the additional input text strings, and wherein at least one of the plurality of input text strings are used to generate a grammar source code file.

14. A non-transitory computer readable storage medium configured to store a set of instructions that when executed causes a processor to perform:

tagging the input text string;

examining, via a processor, the input text string for at least one first set of substitutions based on content of the input text string; and

determining whether the input text string is a substring of a previously tagged input text string by comparing the input text string to a previously tagged input text string, wherein the substring determination operation determines whether the input text string is wholly included in the previously tagged input text string, wherein if the input text string is determined to be a substring of a previously tagged input text string, then

determining whether the input text string and the at least one additional input text string share the common pre-assigned tag identifier stored in a memory location, and

wherein if the input text string and the at least one additional input text string share a common pre-assigned tag identifier stored in the memory location, then eliminating at least one of the input text string and the at least one additional input text string from the natural language grammar.

15. The non-transitory computer readable storage medium of claim 14, wherein the processor is further configured to perform:

the at least one first set of substitutions by expanding the input text string to create at least one additional input text string that includes at least one portion of the input text string and at least one additional portion not previously part of the input text string.

16. The non-transitory computer readable storage medium of claim 15, wherein each of the at least one additional input text string contains words that are the same as the input text string except at least one word has been removed from the input text string and has been replaced by a different word in the at least one additional input text string.

17. The non-transitory computer readable storage medium of claim 14, wherein eliminating at least one of the input text string and the at least one additional input text string comprises determining which is a longer input text string and eliminating that which is a longer input text string among the input text string and the at least one additional input text string.

18. The non-transitory computer readable storage medium of claim 14, wherein if the input text string and the at least one additional input text string do not share a common pre-assigned tag identifier stored in the memory location, then maintaining the input text string and the at least one additional input text string in the natural language grammar by writing both the input text string and at least one additional input text string to a source code stored in the memory location.