Parsing method and system for natural language processing

• US 5,761,631 A
• Filed: 07/12/1995
• Issued: 06/02/1998
• Est. Priority Date: 11/17/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nasukawa, Tetsuya
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US08/501,749
• Time in Patent Office: 1,056 Days
• Field of Search: 395/751, 395/752, 395/754, 395/755, 395/759, 395/760, 704/1, 704/2, 704/4, 704/5, 704/9, 704/10
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/226 Validation
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

The present invention provides a method and system to improve the accuracy of natural language processing systems by enabling them to acquire a parsing output that is accurate to a degree for any type of sentence. The feature of the present invention is that a sentence (a non-grammatical, ill-formed sentence) that cannot be parsed when using a conventional parsing process, which relies on grammatical knowledge, is re-analyzed by using the parsing results for an identical word row in a sentence (a well-formed sentence) in the same context that could be parsed. More specifically, the processing below is performed: (1) a well-formed sentence in a context that includes a word row that is identical to a word row in an ill-formed sentence is searched for, and a dependency structure for that word row is extracted from the parsing results for the well-formed sentence; and (2) the dependency structures of the phrases obtained in (1) are linked by referring to linking information for the well-formed sentence and a grammar, and the dependency structure of the entire sentence is introduced.

Claims

1. A computer implemented natural language analysis method, comprising the steps of:

(a) inputting a plurality of sentences described in natural language;

(b) analyzing said plurality of sentences into morphemes;

(c) parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) when those results that are obtained by said parsing are well-formed sentences, storing said parsing analysis results as well-formed context information;

(e) when those results that are obtained by said parsing are ill-formed sentences, storing said parsing analysis results as ill-formed sentence information;

(f) upon completion of said parsing of said plurality of sentences, retrieving, from said well-formed context information, partial parsing information for sentences having parsing analysis results that were stored as said ill-formed sentence information; and

(g) parsing once more said sentences having parsing analysis results that were stored as said ill-formed sentence information by using said information retrieved from said well-formed context information.

2. A natural language analysis method according to claim 1, wherein said well-formed context information that is stored includes context information for each sentence and context information for each word.

3. A natural language analysis method according to claim 2, wherein said context information for each sentence includes a sentence number, input character rows, and information about a sentence parsing result.

4. A natural language analysis method according to claim 2, wherein said context information that is stored for each word includes a character row of a surface structure, a word by which one word is modified and a connection relationship, and a word that said one word modifies and a connection relationship.

5. A natural language analysis method according to claim 1, wherein said ill-formed sentence information that is stored includes morphological analysis results and context information for each sentence, and context information for each word.

6. A computer implemented natural language analysis system, comprising:

(a) means for inputting a plurality of sentences described in natural language;

(b) means for analyzing said plurality of sentences into morphemes;

(c) means for parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) means for, when those results that are obtained by said parsing are well-formed sentences, storing said parsing analysis results as well-formed context information;

(e) means for, when those results that are obtained by said parsing are ill-formed sentences, storing said parsing analysis results as ill-formed sentence information;

(f) means for, upon completion of said parsing of said plurality of sentences, retrieving, from said well-formed context information, partial parsing information for sentences having parsing analysis results that were stored as said ill-formed sentence information; and

(g) means for parsing once more said sentences having parsing analysis results that were stored as said ill-formed sentence information by using said information retrieved from said well-formed context information.

7. A natural language analysis system according to claim 6, wherein said well-formed context information that is stored includes context information for each sentence and context information for each word.

8. A natural language analysis system according to claim 6, wherein said ill-formed sentence information that is stored includes morphological analysis results and context information for each sentence, and context information for each word.

9. A computer implemented natural language analysis method, comprising the steps of:

(a) inputting a plurality of sentences described in natural language;

(b) analyzing said plurality of sentences into morphemes;

(c) parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) when the results of said parsing are well-formed sentences, storing, as well-formed context information, parsing information that includes information about word connections;

(e) when the results of said parsing are ill-formed sentences, storing, as ill-formed sentence information, parsing information that includes information about word rows;

(f) upon the completion of said parsing of said plurality of sentences, retrieving, from said well-formed context information, information about a word row connection that is the same as each sentence having parsing information that was stored as said ill-formed sentence information; and

(g) assembling phrase structure trees based on said information that is retrieved from said well-formed context information.

10. A computer implemented natural language analysis method, comprising the steps of:

(a) inputting a plurality of sentences described in natural language;

(b) analyzing said plurality of sentences into morphemes;

(c) parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) when said results of said parsing are well-formed sentences, storing, as well-formed context information, parsing information that includes information about word connections;

(e) when the results of said parsing are ill-formed sentences, storing, as ill-formed sentence information, parsing information that includes information about word rows;

(f) upon completion of said parsing of said plurality of sentences, retrieving, from said well-formed context information, information about a word row connection that is the same as each sentence having parsing information that was stored as said ill-formed sentence information;

(g) determining whether or not all words in a sentence having parsing information that was stored as said ill-formed sentence information are dominated by information that is retrieved from said well-formed context information, and if there are words that are not so dominated, extracting information for said words from said ill-formed sentence information; and

(h) connecting phrase structure trees by applying said context information and grammar information to information that is obtained at said steps (f) and (g).

11. A natural language processing method according to claim 10, further comprising a step of determining whether or not said phrase structure trees are united for each sentence, and if not, selecting a less strict connection rule that is included in said grammar information to reconnect said phrase structure trees.

12. A computer implemented natural language analysis system, comprising:

(a) means for inputting a plurality of sentences described in natural language;

(b) means for analyzing said plurality of sentences into morphemes;

(c) means for parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) means for, when the results of said parsing are well-formed sentences, storing, as well-formed context information, parsing information that includes information about word connections;

(e) means for, when the results of parsing are ill-formed sentences, storing, as ill-formed sentence information, parsing information that includes information about word rows;

(f) means for, upon completion of said parsing of said plurality of sentences, retrieving, from said well-formed context information, information about a word row connection that is the same as each sentence having parsing information that was stored as said ill-formed sentence information;

(g) means for assembling phrase structure trees based on said information that is retrieved from said well-formed context information.

13. A computer implemented natural language analysis system, comprising:

(a) means for inputting a plurality of sentences described in natural language;

(b) means for analyzing said plurality of sentences into morphemes;

(c) means for parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) means for, when said results of said parsing are well-formed sentences, storing, as well-formed context information, parsing information that includes information about word connections;

(e) means for, when the results of said parsing are ill-formed sentences, storing, as ill-formed sentence information, parsing information that includes information about word rows;

(f) means for, upon completion of said parsing of said plurality of sentences, retrieving, from said well-formed context information, information about a word row connection that is the same as each sentence having parsing information that was stored as said ill-formed sentence information;

(g) means for determining whether or not all words in a sentence having parsing information that was stored as said ill-formed sentence information are dominated by information that is retrieved from said well-formed context information, and if there are words that are not so dominated, extracting information for said words from said ill-formed sentence information;

(h) means for storing grammar information includes word connection rule; and

(i) means for connecting phrase structure trees by applying said context information and grammar information stored in said storing means to information that is obtained from said retrieving means and said determining means.

14. A natural language processing system according to claim 13, further comprising means for determining whether or not said phrase structure trees are united for each sentence, and if not, selecting a less strict connection rule that is included in said grammar information to reconnect said phrase structure trees, wherein said means (h) possesses a plurality of connection rules that consist of a more strict connection rule and a less strict connection rule.

15. A computer implemented natural language analysis method, comprising the steps of:

(a) inputting a plurality of sentences described in natural language;

(b) analyzing said plurality of sentences into morphemes;

(c) parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) when the results of said parsing present a single analysis choice, storing said parsing result as context information;

(e) when the results of said parsing present a plurality of analysis choices, storing said parsing result as sentence information for multiple analysis choices;

(f) upon completion of said parsing of said plurality of sentences, comparing said sentence information for multiple analysis choices with information from among said well-formed context information, and determining an evaluation value for said analysis choice; and

(g) selecting, as said sentence parsing information from among said multiple analysis choices, an analysis choice that has a maximum evaluation value.

16. A natural language processing method according to claim 15, wherein said step of determining said evaluation value includes a process for calculating the ratio of the presence in a context of a word that has the same linking relationship as an identical word to a total amount of said plurality of sentences inputted.

17. A natural language processing method according to claim 15, wherein said step of determining said evaluation value includes a process for calculating the ratio of the presence in a context of words having the same parts of speech to a total amount of instances of said context of words.

18. A natural language processing method according to claim 15, wherein said step of determining said evaluation value includes a process for calculating a correspondence of a sentence type with an adjacent sentence.

19. A computer implemented natural language analysis system, comprising:

(a) means for inputting a plurality of sentences described in natural language;

(b) means for analyzing said plurality of sentences into morphemes;

(c) means for parsing said plurality of sentences based on those results that are obtained by said morphological analysis;

(d) means for, when the results of said parsing present a single analysis choice, storing said parsing result as context information;

(e) means for, when the results of said parsing present a plurality of analysis choices, storing said parsing result as sentence information for multiple analysis choices;

(f) means for, upon completion of said parsing of said plurality of sentences, comparing said sentence information for multiple analysis choices with information from among said well-formed context information, and determining an evaluation value for said analysis choice; and

(g) means for selecting, as said sentence parsing information from among said multiple analysis choices, an analysis choice that has a maximum evaluation value.

20. A natural language processing system according to claim 19, wherein said means for determining said evaluation value includes a process for calculating the ratio of the presence in a context of a word that has the same linking relationship as an identical word to a total amount of said plurality of sentences inputted.

21. A natural language processing system according to claim 19, wherein said means for determining said evaluation value includes a process for calculating the ratio of the presence in a context of words having the same parts of speech to a total amount of instances of said context of words.

22. A natural language processing system according to claim 19, wherein said means for determining said evaluation value includes a process for calculating a correspondence of a sentence type with an adjacent sentence.