Method and apparatus for universal parsing of language

• US 5,878,385 A
• Filed: 09/16/1996
• Issued: 03/02/1999
• Est. Priority Date: 09/16/1996
• Status: Expired due to Fees

• Current Assignee: Ergo Linguistic Technologies, Inc.
• Original Assignee: ERGO Linguistic Technologies
• Inventors: Bralich, Phillip A., Bickerton, Derek
• Primary Examiner(s): Thomas, Joseph
• Application Number:
  US08/715,313
• Time in Patent Office: 897 Days
• Field of Search: 704/9, 704/8, 704/10, 704/1, 707/531, 707/532, 707/536, 707/533, 707/534
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

A method and apparatus for natural language parsing are described. The invention includes the steps of retrieving an input string, and performing a dictionary look-up for each word in the input string to form a correspondence between each word and a dictionary entry. The dictionary entry provides lexical features of the word. The invention includes the additional step of processing the words in the input string beginning with a last word in the input string and continuing toward the first word in the input string. This step includes the step of associating a selected word in the input string with a word located to the left of the selected word in the input string to form a word phrase. The associating step is performed according to predetermined selection restriction rules. The steps of processing the words and associating a selected word are repeated until all words of the input string have been processed.

Claims

1. A computer implemented method for parsing words of an input string, the method comprising the steps of:

a) retrieving the input string;

b) performing a dictionary look-up for each word in the input string to form a correspondence between each word and a dictionary entry in the dictionary, said dictionary entry providing lexical features of the word;

c) processing the words in the input string beginning with a last word in the input string and continuing toward the first word in the input string;

d) said processing of the words in the input string including the steps of associating a selected word in the input string with a word located to the left of the selected word in the input string to form a word phrase, said associating performed according to predetermined selection restriction rules; and

e) repeating steps (c) and (d), processing the words in the input string, until all words of the input string have been processed.

2. A computer implemented method for parsing words of an input string, the method comprising the steps of:

a) retrieving the input string;

b) performing a dictionary look-up for each word in the input string to form a correspondence between each word and a dictionary entry in the dictionary, said dictionary entry providing lexical features of the word;

c) processing the words in the input string beginning with a last word in the input string and continuing toward the first word in the input string;

said processing of the words in the input string including the steps of

e) attaching a selected word in the input string to a preceding word in the input string, said attachment performed if permitted by at least one predetermined selection restriction rule and not performed if not permitted by at least one predetermined selection restriction rule, said attachment of the selected word to the preceding word forming a word phrase, said selection restriction rules based upon predetermined lexical features of the words in the input string;

f) promoting at least one of the selected word and the word phrase in the input string to a next higher lexical value if permitted by at least one promotion restriction rule; and

g) repeating the steps (c) through (f), including attaching and promoting, until all words of the input string have been processed.

3. A computer implemented method for parsing words of an input string, the method comprising the steps of:

a) inputting the input string;

b) performing a dictionary look-up for each word in the input string to form a correspondence between each word and a dictionary entry in the dictionary, said dictionary entries providing lexical features of the word;

c) assigning a first level of strength to each word in the input string, said first level of strength defined by the dictionary entry corresponding the word and identifying a basic grammatical category associated with the word;

d) selecting a word in the input string to process, said selected word corresponding to a last word of the input string;

e) determining if the selected word attaches to an immediately preceding word in the input string, said determination performed according to predetermined selection restriction rules and resulting in one of a successful attachment and an attachment failure;

f) said successful attachment resulting in formation of a word group linking the attached words, said word group assigned one of the first level of strength, a second level of strength, and a third level of strength, said levels of strength defined by the predetermined selection restriction rules;

g) said attachment failure resulting in an attempt to promote the word group to a next higher level of strength, until the word group attains the third level of strength; and

h) selecting the next word in the input string located to the left of the selected word and performing steps (e) through (g) until all words in the input string have been processed.