Method for Natural Language Data Processing Using Morphological and Part-of-Speech Information

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright fights whatsoever.

The invention disclosed herein relates generally to natural language data processing and, more particularly, to a computer based method for enhancing natural language data for subsequent processing, and for retrieving natural language data from the enhanced natural language data using morphological and part-of-speech information.

Sophisticated techniques for archival of electrical signals representative of natural language data allow most business organizations and libraries to store vast mounts of information in their computer systems. However, regardless of how sophisticated the archival techniques become, the stored information is virtually worthless unless such information can be retrieved when requested by an individual user.

Typical techniques for retrieving a desired text use "keyword" and "contextual" searches. Each of these techniques requires the user to provide a fairly precise query or else retrieval of the desired text can be greatly compromised. As an example, a user may attempt to retrieve information on "heat seeking missiles", and request every textual fragment containing the word "seeking". Unfortunately, this technique would fail to retrieve fragments such as "successful missiles sought heat sources" or "smart missile seeks heat".

Alternatives have been suggested wherein a predetermined root of the keyword to be searched and a truncation mask are combined to increase the probability of matching various word endings or inflections. For example, if the exclamation point symbol "!" represents the truncation mask, then "seek!" would match "seeks" or "seeking" but still would fail to match "sought" and thus this approach does not fully resolve problems created by differences in word inflection.

A method for using morphological information to cross reference keywords used for information retrieval is disclosed in U.S. Pat. No. 5,099,426. The method described therein is primarily concerned with generating a compressed text and then searching for information in the compressed text using intermediate indexes and a compiled cross reference table. Although the method of the present invention also uses morphological information, the present invention has no requirements either for text compression or any such intermediate indexes and cross reference table. Further, the method described in the foregoing patent does not employ word sense disambiguation or part-of-speech (POS) information to refine the search. Accordingly, if the method described therein was utilized to search a text for "recording", it would likely find occurrences such as "record" "records", "recorded", "recording"and possibly "prerecorded" and "rerecorded"; however, such method offers no provisions to refine the search to retrieve those occurrences only where "recording" is used as a noun, for example. Thus, it is desirable for the retrieval method to allow the user to specify word usage as part of the search strategy. In this manner, the user may request that occurrences of a predetermined word be retrieved only when the predetermined word is specifically used, for example, either as a verb, adjective, or noun.

It is therefore an object of the invention to provide an improved natural language data retrieval method which is not subject to the foregoing disadvantages of existing information retrieval methods.

It is a further object of the invention to provide a method for enhancement of natural language data such that the enhanced data may be conveniently used in a subsequent natural language processing scheme such as natural language data retrieval.

It is yet a further object of the invention to provide a natural language data retrieval method which uses morphological and part-of-speech information to increase the probability of retrieving selected textual information.

The foregoing and further objects of the invention will become apparent as the description proceeds. In accordance with the present invention an enhancement and retrieval method for natural language data using a computer is provided. The enhancement aspect of the method includes the steps of providing to the computer a text corpus file which comprises respective electrical signals representative of the natural language data. The electrical signals are processed to parse the text corpus file into a plurality of sentences each constituted of a respective stream of corpus words. Linguistic analysis, such as morphological, lexical, syntactic as well as semantic analysis, is executed upon each stream of corpus words to derive morphological roots, part-of-speech and lexical information corresponding to respective ones of the corpus words. The foregoing linguistic analysis allows for generation of an enhanced text corpus file, i.e., a linguistically enriched text corpus file which includes enhanced words tagged with a respective morphological root, part-of-speech information as well as lexical variants corresponding to respective ones of the corpus words. Each enhanced corpus word can further include a corresponding affix such as a prefix, or suffix, or both.

The retrieval aspect of the method includes the steps of providing to the computer a query text file which comprises respective electrical signals representative of predetermined inquiry data. The electrical signals representative of the predetermined query data are processed to parse the query text file into respective query items each constituted of a respective stream of query words. Morphological, semantic as well as domain specific synonym analysis is executed upon each stream of query words to generate a plurality of trigger token morphemes corresponding to respective ones of the query items. Part-of-speech information and collocation information associated with respective ones of the query words can be provided to further enhance each trigger token morpheme. A search mask stream based upon the plurality of trigger token morphemes is then generated. The enhanced text is scanned so as to correlate the search mask stream with the enhanced text corpus for retrieving a selected portion of the enhanced text based upon a match between the search mask stream and the enhanced text corpus.

The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself, however, both as to organization and method of operation, together with further advantages thereof, may best be understood by reference to the following description in conjunction with the accompanying drawings in which like numerals represent like steps throughout the drawings, and in which:

FIG. 1 is a flowchart illustrating a sequence of steps for constructing an enhanced text corpus file in accordance with the present invention;

FIG. 2 is a flowchart illustrating a sequence of steps for constructing trigger token morphemes in accordance with the present invention; and

FIG. 3 is a flowchart illustrating a sequence of steps for retrieving a selected text using the trigger token morphemes upon the enhanced text corpus file.

FIG. 1 illustrates a sequence of method steps which can be advantageously implemented in a general purpose or special purpose computer. In either case, the computer can be part of a natural language data processing system which can be conveniently used to generate an enhanced text corpus in accordance with the present invention. Subsequent to start of operations, as indicated in step 10, a text corpus file made up of respective electrical signals representative of natural language data is provided to the computer in scanning step 15 from a bulk storage device such as a disk or tape device; or from a keyboard entry device; or from a communications link such as modem and the like. As used herein, natural language refers to a language, such as English, Spanish and the like, which human beings speak and write, as distinguished from artificial languages in which computer programs are written.

The electrical signals making-up the text corpus file which is provided to the computer are processed in step 20 by a processing module which operates in a manner well understood by those skilled in the art to parse the text corpus file into a plurality of individual sentences each constituted of a respective stream of corpus words, that is, the processing module is designed to extract individual sentences from the text corpus file.

Linguistic analysis is then performed by respective modules upon each stream of corpus words to derive respective part-of-speech information and morphological roots corresponding to respective ones of the corpus words. Specifically, morphological analysis is performed in step 25 by a morphological analyzer module upon each corpus word to derive a morphological root corresponding to a respective corpus word.

The morphological analysis may be performed by a method similar to that disclosed by Paul S. Jacobs et al in allowed U.S. patent application entitled "Method for Automated Morphological Analysis of Word Structure", Ser. No. 07/570,583, assigned to the assignee of the present invention and incorporated herein by reference. Briefly, a lexicon which can be stored in a memory unit such as a read-only-memory (ROM) or other suitable storage unit must be accessed to retrieve a lexical entry corresponding to a respective corpus word. The lexicon preferably contains a genetic list of electrically encoded lexical entries representative of natural language words. Additionally, the lexicon may contain a domain specific list of electrically encoded lexical entries representative of natural language words which are likely to be used in a predetermined manner in a specific application domain, for example, the lexicon may be adapted to the domain of government specifications, or medicine, or environmental legislation. In any case, for each lexical entry the lexicon can provide a morphological root, and applicable affixes such as prefixes or suffixes. Additionally, or alternatively, the lexicon can provide suitable rules for forming such affixes.

Further, the lexicon can be utilized to execute lexical analysis upon each word in a respective sentence, as indicated in step 27, to acquire predetermined lexical information such as word usage information, including but not limited to eligible part-of-speech usage information corresponding to a respective lexical entry. Thus, the lexicon, like an ordinary English language dictionary, can offer one or more lexical entries corresponding to a particular corpus word; however, unlike such ordinary dictionary the lexicon does not need to offer actual definitions. For example, in the case of the word "book", the task required to derive the morphological root is simply a look-up operation. However, in some other cases the root itself could be a derivative of some other word, and thus the morphological analysis in cooperation with the lexical analysis must be capable to recursively derive the entries for this root. For example, the word "acquisitions" has an immediate root "acquisition", which is in turn derived of the word "acquire". In either case, it should be appreciated that a morphological root may have multiple lexical entries representing different parts-of-speech. For example, the word "chip" may have one lexical entry as a noun and represent an integrated electronic circuit; or the word "chip" may have another lexical entry as a verb and represent the action of cutting a small piece of material.

Syntactic analysis is performed in step 30 by a syntactic analyzer module upon each corpus word to derive respective part-of-speech information and to resolve grammatical ambiguity associated with such part-of-speech information. By way of illustration, eligible part-of-speech information can be determined and resolved depending on the suffix of the corpus word being analyzed. For example, the suffix "s" can only transform a verb into the third person, singular, present tense form; or a noun into the plural form. Thus, the only eligible part-of-speech for a corpus word ending in the "s" suffix is either a noun or a verb. The syntactic analyzer "knows" this about the suffix "s", for example, and therefore will not access (or derive) lexical entries which are not nouns or verbs. For example, using this technique there would not be a need to consider the preposition lexical entry for the word "down" if the word under consideration is "downs". Another useful technique which can help to resolve part-of-speech ambiguity is local context analysis. For example, in the phrases "the preferred stock" and "he preferred coffee" the words "the" and "he" dictate that "preferred" is used in these phrases as adjective and verb respectively.

The syntactic analysis executed in step 30 is advantageously used to resolve part-of-speech ambiguity by identifying the subject, main verb, direct and indirect objects (if any), prepositional phrases, relative clauses, adverbial clauses, etc. for each sentence which constitutes the text corpus file. In particular, during this step of the linguistic analysis, groups of text corpus words, such as phrases, are defined and tagged in terms of an estimated grammatical function. For example, during this phrase-tagging step and depending on the particular context, a phrase can be tagged as a verb-phrase or a noun-phrase based on the estimated grammatical function assigned to this phrase.

In addition, recurring word relationships can be advantageously used to resolve part-of-speech ambiguity. By way of example, U.S. patent application of U. Zernik, entitled "A Method for Tagging Collocations in Text", Ser. No. 07/844,026, assigned to the assignee of the present invention and incorporated herein by reference, discloses a technique which can be conveniently used for performing part-of-speech tagging in the syntactic analysis step of the present invention. Briefly, the foregoing Zenik patent application discloses a technique which uses a calculated variability factor using statistics to measure the variability of a predetermined form that a particular construct takes in the text corpus file under analysis. For example, the construct "expressed concern" can behave as a verb-phrase in "she expressed concern about the issue" or as noun-phrase in "that issue is her expressed concern". Similarly, in "the preferred stock for long term investment" the construct "preferred stock" is a verb phrase, whereas the same construct is a noun-phrase in "GE preferred stock continued to perform well". Therefore, as illustrated in the foregoing exemplary cases, such constructs must be appropriately tagged in the enhanced text corpus to facilitate subsequent processing.

Semantic analysis is performed in step 35 upon each corpus word to allow the computer to better "understand" the meaning of each corpus word. Application domain specific information and semantic knowledge embodied in the lexicon can also be used to disambiguate phrases which exhibit a deep semantic ambiguity such as "get down from the elephant" versus "get down from the goose". Further, semantic analysis step 35 in cooperation with lexical analysis step 27 can be used to access lexical variations corresponding to a single corpus word so as to permit conceptual searches. In this manner "purchase/purchases/ purchasing/purchased" and "buy/buys/buying/bought" each can be traced to a common conceptual root such as "buy", even though the words "purchase" and "buy" do not trace linguistically to a common morphological root.

As indicated in step 40, the foregoing linguistic analysis is repeated until each sentence comprising the text corpus file is respectively analyzed as previously described, to generate an enhanced text corpus file in step 45 using the derived part-of-speech information, morphological roots and lexical variants. The enhanced text corpus file generated in step 45 is made up of a plurality of enhanced sentences each constituted of a respective stream of enhanced words. In particular, each corpus word in the text corpus file is replaced with an enhanced word which includes specific linguistic information pertaining to the corresponding corpus word. It will be appreciated by those skilled in the art that any of a number of representation techniques for the enhanced corpus words may be used and thus any such representation may be selected to facilitate a particular implementation. By way of illustration and not of limitation, an enhanced corpus word may be represented as follows:

For an abbreviated example in accordance with the foregoing representation, the enhanced word "seeking" may be represented as:

where "seeking" is the original corpus word, "seek" is the morphological root, for simplicity of illustration the list of prefixes is empty while the list of suffixes is limited to the suffix "ing" only. The part-of-speech information represented by the letter "x" is not specifically listed in this example, since it is dependent upon the specific word usage in the sentence. For instance "seeking" could have been part of a verb phrase ("seeking new discoveries"), or, alternatively, part of a noun phrase acting as an adjective ("heat seeking missile"). "Find" is a possible lexical variant in the foregoing example. Once all the sentences in the text corpus file have been enhanced, the enhanced text corpus can be stored as indicated in step 50, in a bulk storage device or transmitted via a communications link to a remote storage device for subsequent use or processing. Step 55 indicates end of operations for constructing the enhanced text corpus which can be conveniently utilized in subsequent natural language information processing such as natural language retrieval or extraction of requirement data, or other line textual information extraction.

FIG. 2 illustrates a sequence of method steps used to construct a plurality of trigger token morphemes in accordance with the present invention. As used herein, a trigger token morpheme refers to a linguistic unit representation which is constituted of one or more words and which uses at least morphological and part-of-speech information for the purpose of increasing the probability of triggering a match or "hit" during a textual search. Subsequent to start of operations, as indicated in step 60, a query text file made up of respective electrical signals representative of predetermined inquiry data is provided to the computer as indicated in step 65. The electrical signals making-up the query text file are processed as indicated in step 70 to parse the query text file into respective query items. Collocation as well as part-of-speech information can be conveniently provided as part of a query item to perform specific searches. For example, logical connector strings built in accordance with well understood techniques to those skilled in the art can be used to define a predetermined collocation of query words within a respective query item. A user may desire, for example, to retrieve information on boxing matches having terminated by knockout in the first round. Thus, a possible representation of a query item may be as follows:

wherein label NN represents noun part-of-speech information for the word "round", while (2W) indicates collocation information for query words therein, specifically (2W) can represent that the word "knockout" be collocated within 2 words of the construct "first round". A key feature of the trigger token morpheme representation is for the user to have the capability of providing part-of-speech information within a respective query item. This feature is particularly advantageous to narrow the search since as can be appreciated in the foregoing exemplary query item, the word "round" in addition to being a name could also be an adjective (the round table); a verb (she rounded her lips); a preposition (Ali danced round the ring); and an adverb (the airplane circled round at sunset).

Morphological analysis is performed at step 75 upon each word in the query item to derive morphological roots for each word in query item. This morphological analysis is essentially identical to the morphological analysis described in the context of FIG. 1. Similarly, semantic analysis is performed at step 80 upon each word in query item to derive lexical variants corresponding to a query word. Domain specific synonym analysis can be further executed as indicated in step 82 upon each query word to derive predetermined synonyms likely to correspond to respective ones of the query words, and thus increase the probability of matching a desired textual search. For example, the word "gate" in the domain of electrical engineering may be associated with a switching circuit whereas the word "gate" in the domain of civil engineering may be associated with a barrier or wall. It should be appreciated by those skilled in the art, that the sequence of steps required to generate the trigger token morphemes can be performed independent of the enhanced text corpus and therefore such sequence of steps could be performed prior to generating the enhanced text corpus information. Further, assuming enough computational power was available, such steps could be perforated simultaneously, that is, the generation of the enhanced text corpus and the generation of the trigger token morphemes could be performed in a parallel mode of operation.

As indicated in step 85, the foregoing linguistic analysis is repeated until each query item comprising the query text file is respectively analyzed to generate a respective plurality of trigger token morphemes as indicated in step 90 . The representation of the query words in a trigger token morpheme can be substantially similar to the exemplary representation of the enhanced words in the text corpus file described in the context of FIG. 1 with the proviso that, as is well understood by those skilled in the art, logical connectors and Boolean operators, like "and" or "or", can be used to indicate collocation of respective query words within a query item. As indicated in step 95, the plurality of trigger token morphemes can be stored in an appropriate bulk storage device prior to end of operations indicated in step 100. The trigger token morphemes, alternatively, can be transmitted to a remote location via a communications link for subsequent use at such remote location.

FIG. 3 illustrates a sequence of steps which can be used to retrieve a selected text from the enhanced text corpus file. After start of operations in step 105, each trigger token morpheme is used to generate in step 110 a search mask stream based upon the plurality of such trigger token morphemes. The search mask stream is an appropriate internal representation which can be used in a conventional search engine module for pattern-matching selected portions of the enhanced text corpus file with the search mask stream. Typical digital search techniques applicable to English are disclosed, for example, by Donald E. Knuth in "The Art of Computer Programming, Vol. 3, Sorting and Searching", pp., 481-499, Addison-Wesley, 1973.

As indicated in step 120, a scanning device can be used to scan the enhanced text corpus to correlate in step 125 the search mask stream with the enhanced text corpus. In essence, the search mask stream and the enhanced text corpus are superposed, starting at the beginning of one another. If no match is detected, the search mask stream is shifted to the right (or to the left depending on the specific natural language under analysis) and the comparison is repeated. If no match is detected, a message such as "no match detected" can be provided to the user for suitable action. In operation, when there is a match between the search mask stream and the enhanced text corpus, a respective selected text is retrieved in step 130 and made available to the user. The retrieved selected text can be displayed or stored for subsequent use prior to end of operations indicated in step 135.

Appendix I contains computer source code listings which may be utilized to control operation of a computer in accordance with the present natural language data processing method. The code as written may be executed by a Sun Workstation, for example.

While only certain features of the invention have been illustrated and described herein, many modifications and changes will occur to those skilled in the art. It is therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the spirit of the invention. ##SPC1##