Using wildcards in semantic parsing

• US 7,464,032 B2
• Filed: 06/14/2005
• Issued: 12/09/2008
• Est. Priority Date: 08/21/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, YeYi
• Primary Examiner(s): Han; Qi
• Application Number:
  US11/152,717
• Publication Number:
  US 20050234704A1
• Time in Patent Office: 1,274 Days
• Field of Search: 704/251, 704 1- 10
• US Class Current: 704/251
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method and apparatus perform semantic parsing by designating one or more words in an input text stream as wildcards. Under some embodiments, partially constructed parses formed from other words in the text stream are used to control when a later word will be identified as a wildcard. In particular, if a partial parse is expecting a semantic token that begins with a wildcard, the next word in the input text segment is designated as a wildcard term. If none of the existing partial parses are expecting a semantic token that begins with a wildcard, the next word is not designated as a wildcard

Claims

1. A method of generating a semantic representation of a string of words from a language, the method comprising:

identifying at least one semantic token activated by a word;

placing the identified semantic token in a list of potential semantic tokens for the semantic representation of the string of words;

placing a wildcard semantic token in the list of potential semantic tokens for the word, the wildcard semantic token being activated by every word in the language; and

building the semantic representation in part by utilizing one of the semantic tokens in the list of potential semantic tokens by generating a semantic token that has a wildcard semantic token as a child node based on the generation of the wildcard semantic token by identifying a rule for the semantic token in a rule set where the rule indicates that the wildcard semantic token is the left-most child node of the semantic token.

2. The method of claim 1 wherein placing semantic tokens in the list comprises placing partial parses of semantic tokens in a chart and full parses of semantic tokens in a candidate list.

3. The method of claim 2 wherein placing partial parses of semantic tokens in the chart comprises providing an indication of the identity of an item needed to extend the partial parse.

4. The method of claim 3 wherein the item needed to extend a partial parse comprises a semantic token.

5. The method of claim 4 wherein the item needed to extend a partial parse comprises a wildcard semantic token.

6. The method of claim 3 wherein placing the wildcard semantic token in the list of potential semantic tokens comprises only placing the wildcard semantic token in the list under two alternative conditions.

7. A method of parsing text to form a semantic structure, the semantic structure formed of terminal nodes and non-terminal nodes, each non-terminal node being represented by a semantic token that is defined by child nodes beneath the semantic token, the method comprising:

generating a semantic token that has a word in the text as a child node;

generating a wildcard semantic token that has a word in the text as a child node, the wildcard semantic token having any word as a child node;

generating a semantic token that has a wildcard semantic token as a child node based on the generation of the wildcard semantic token by identifying a rule for the semantic token in a rule set where the rule indicates that the wildcard semantic token is the left-most child node of the semantic token; and

utilizing at least one of the generated semantic tokens in the semantic structure representing the semantic meaning of the text.

8. The method of claim 7 further comprising associating a wildcard semantic token with a previously generated semantic token that is expecting a wildcard semantic token.