Method and apparatus for expanding dictionaries during parsing

• US 7,158,930 B2
• Filed: 08/15/2002
• Issued: 01/02/2007
• Est. Priority Date: 08/15/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wu, Andi, Pentheroudakis, Joseph E.
• Primary Examiner(s): {hacek over (S)}mits; Talivaldis Ivars
• Assistant Examiner(s): SAINT CYR, LEONARD
• Application Number:
  US10/219,752
• Publication Number:
  US 20040034525A1
• Time in Patent Office: 1,601 Days
• Field of Search: 704/9, 704/10
• US Class Current: 704/10
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/242 Dictionaries

Abstract

A method is provided for parsing text in a corpus. The method includes hypothesizing a possible new entry for a dictionary based on a first segment of text. A successful parse is then formed for the first segment of text using the possible new entry. Based on the successful parse, the dictionary is changed to include the new entry. The new entry in the dictionary is then used to parse a second segment of text.

Claims

1. A method of parsing text in a corpus, the method comprising:

hypothesizing a possible new entry for a dictionary based on a first segment of a text;

forming a successful parse of the first segment of said text using the possible new entry;

changing the dictionary to include the new entry based on the successful parse by making an existing entry in the dictionary active; and

using the new entry in the dictionary to parse a second segment of said text.

2. The method of claim 1 wherein hypothesizing a possible new entry comprises proposing a new word for a dictionary.

3. The method of claim 1 wherein hypothesizing a possible new entry comprises proposing a new attribute for an existing word in the dictionary.

4. The method of claim 1 wherein making an existing entry active comprises:

increasing a count associated with the entry based on the successful parse;

determining that the count exceeds a threshold; and

making the existing entry active based on the count exceeding the threshold.

5. The method of claim 4 wherein determining that the count exceeds a threshold comprises selecting a threshold from a plurality of possible thresholds based on the entry.

6. The method of claim 1 wherein changing the dictionary comprises changing a domain-specific dictionary.

7. The method of claim 6 wherein using the new entry in the dictionary to parse the second segment comprises:

merging the domain-specific dictionary with a general dictionary to form a merged dictionary; and

using the merged dictionary to parse the second segment.

8. The method of claim 7 wherein merging the domain-specific dictionary and the general dictionary comprises designating attributes for a word in the merged dictionary such that some of the attributes come from the domain-specific dictionary and some of the attributes come from the general dictionary.

9. The method of claim 1 wherein using the new entry comprises:

hypothesizing a second possible new entry based on the second segment of text;

forming a successful parse with the new entry and the second possible new entry;

changing the dictionary to include the second possible new entry.

10. A computer-readable medium having computer-executable instructions for performing steps comprising:

hypothesizing a possible attribute for a word in a text segment, the possible attribute not being listed for the word in a dictionary used to form parse structures from text segments;

creating a parse token based on the possible attribute for the word;

using the parse token to form a parse structure for the text segment through steps comprising;

creating a second parse token for the same word as the parse token;

assigning a low score to the parse token relative to a score for the second parse token;

making the parse token and the second parse token available for forming the parse structure;

selecting the parse token instead of the second parse token when forming the parse structure;

based on the parse token appearing in the parse structure, adding the possible attribute for the word to a dictionary used to form parse structures; and

accessing the dictionary to retrieve the possible attribute for the word in the dictionary as part of forming a parse structure for second segment of said text.

11. The computer-readable medium of claim 10 wherein hypothesizing a possible attribute for a word comprises hypothesizing a part of speech for the word.

12. The computer-readable medium of claim 10 wherein adding the possible attribute to a dictionary comprises adding the possible attribute to a domain-specific dictionary.

13. The computer-readable medium of claim 12 wherein accessing the dictionary comprises accessing a merged dictionary formed by merging the domain-specific dictionary with a general dictionary.

14. The computer-readable medium of claim 10 wherein forming a parse structure for a second text segment comprises:

hypothesizing a possible attribute for a second word, the possible attribute not being listed for the second word in a dictionary used to form parse structures;

creating a parse token using the retrieved attribute;

creating a second parse token based on the possible attribute for the second word;

forming a parse structure that includes the parse token and the second parse token; and

based on the second parse token appearing in the parse structure, adding the possible attribute for the second word to a dictionary.

15. A method of parsing a text having at least two sentences, the method comprising:

parsing a first sentence of the text to form a first parse structure by using a dictionary to retrieve an attribute of a word in the first sentence;

based on the first parse structure, dynamically modifying the dictionary to form a modified dictionary before parsing another sentence of the text; and

using the modified dictionary to parse a second sentence of the text to form a second parse structure.

16. The method of claim 15 further comprising modifying the dictionary based on the second parse structure.

17. The method of claim 15 wherein modifying the dictionary comprises adding an entry to the dictionary based on an attribute of a token in the parse structure.

18. The method of claim 17 wherein the attribute is a part of speech.

19. A dictionary formed through a dynamic process that utilizes a corpus of text comprising at least two sentences, the process comprising:

forming an initial dictionary;

using the initial dictionary to parse a sentence in the corpus to form a first parse structure;

modifying the initial dictionary based on the first parse structure before parsing another sentence from the corpus to form the dictionary.

20. The dictionary of claim 19 wherein the dictionary is used to parse a second sentence in the corpus to form a second parse structure.

21. The dictionary of claim 20 wherein the dictionary is formed through a further process of modifying the dictionary based on the second parse structure before parsing another sentence from the corpus.