US 5,475,587 AGrant
Method and Apparatus for Efficient Morphological Text Analysis Using a High-Level Language for Compact Specification of Inflectional Paradigms
Issue Date:1995-12-12
•4 Claims
•38 Drawing Sheets
Abstract
A language syntax defines statement forms for statements that describe the inflectional morphology of the natural language. A set of language statements that follow a language syntax to describe the inflectional morphology of the natural language is accepted as input into to a computer. Rule statements define a set of morpho-syntactic features corresponding to grammatical distinctions within the parts of speech categories in the natural language and define a set of inflectional morphological paradigms. The inflectional morphological paradigms include form rule statements to describe the construction of word forms and associate with each construction pre-selected morpho-syntactic features.
Metadata
Assignee
- Digital Equipment Corporation
Inventors
- Peter G. Anick
- Suzanne O. Artemieff
Application Information
Application Number:US 729445&
Filing Date:1991-07-12
Priority Date:1991-06-28
Art Unit:231
Classifications
IPC:
G06F 1538
Field of Search:
364419;419.04;419.08;419.19;419.13;419.11
Patent Drawings (38 sheets)
Description
FIELD OF THE INVENTION
This invention relates generally to the fields of information management and data processing and, more particularly, to the field of natural language processing, applied in information management and data processing systems.
BACKGROUND OF THE INVENTION
There is great interest in applying the principles of morphology to problems in natural language processing in the fields of information management and data processing. Morphology is that part of linguistic study which is concerned with the formation of words in a natural language (such as English, French, German or Russian). It is the study of what people do everyday to form words in speech and writing. Of interest is how words are formed to provide meaning in different grammatical contexts.
People communicate by organizing words into larger structures like phrases, clauses, sentences and paragraphs, according to the accepted grammatical, syntactic and spelling conventions of a given natural language. The grammar of a language, groups words into categories that denote the principal parts of the language (or parts of speech), such as nouns, verbs, adjectives and adverbs. Within each part of speech category, a word can have one of several possible inflections, each marking distinctions in use such as gender, number, tense, person, mood or voice. A word, of course, can be used in more than one part of speech. When a word is used in a sentence, it appears in an inflected form that evokes the general meaning of the word and also marks some of the grammatical distinctions in use. For example, the idea of existence or "being" is conveyed in the different forms of the verb "to be". In these sentences:
I am tall.
She is taller.
We are the tallest people in the room. the different inflicted forms of the verb "to be" convey the idea of "being", tailored to the different subjects (e.g., first-person singular, second-person singular, first-person plural) and a tense (e.g., present tense) of the verb. Thus, a word is represented in a language through the collection of inflections, used to denote meaning as applied in a particular grammatical context. Some languages are more highly inflected than others. In English for example, word order (i.e., syntax) is a dominant factor in determining meaning, and, correspondingly, English words appear in only a relatively few number of inflected forms. In comparison, languages such as German place less importance on word order and, correspondingly, rely more on word form. Words in those languages have many more inflections. Inflectional morphology is the study of the different ways in which word forms are constructed in each language.
Morphology employs terms to formally describe the systems of construction that people use to form words in a natural language. Each construction of a given word is called a form, and a form encountered in a passage of text is called a surface form. The entire set or family of forms for a given word is called a lemma. Each lemma is identified by one form from its family (such as the form commonly found in a dictionary) called a citation form (and sometimes called a canonical form).
The words in any language are formed according to an inflectional morphology, which is defined to be the alteration of a basic word form to express the grammatical distinctions of a word within its part of speech category. Alteration is generally defined to mean the concatenation of one or-more affixes to a primary or base word form called a stem. A stem is a group of characters, which roughly corresponds to the citation form of a lemma and evokes the primary meaning of the word. Affixes are a small, closed class of character strings, which are added to a stem either as a prefix or a suffix. Affixes have a systematic grammatical effect, when combined with a stem, that provides an indication of that word form's part of speech category and inflectional characteristics. The indications that denote part of speech and specific inflectional characteristics are called the morpho-syntactic properties of a word.
When people speak or write in a natural language, they instantly form words for a given grammatical context, because they have learned (usually as children in grammar school) that most words inflect according to a number of grammatical construction and spelling rules. The rules for constructing word inflections are systematic and generally apply to a large number of words within a grammatical category. Commonly available grammar books tend to group the words which inflect by the same rules, such as noun declension and verb conjugation groups, often illustrating the rule with examples of a typical word, such as this exemplary description of the rule for French second conjugation verbs:
Rule:
To write the present tense of French verbs whose infinitive form ends in "ir" (such as the verb reussir), take the stem (reuss) and add the following endings:
See, e.g., Nebelad and Frederich, French Grammar, Monarch Press, (New York, 1971). A grammar book table, such that above, includes the construction of an intermediate form stem from the infinitive form of the verb (reuss), a set of suffixes to add to this intermediate stem, and a set of grammatical features (morpho-syntactic properties) that correspond to the resulting word forms. A system of grammatical construction rules that apply to a number of words, such as the group of French second conjugation verbs, is called an inflectional paradigm. By associating a word with an inflectional paradigm, people can create inflected forms for that word, using its construction rules.
In addition to inflectional paradigms, word formation in any language is also governed by a number of orthographic rules. These spelling rules differ from the inflectional paradigms for grammatical construction, because their application is not based on any grammatical purpose. Grammatical construction rules, such as the paradigm to conjugate the present tense forms of the French verb reussir shown above, aid in forming inflections with distinct morpho-syntactic properties. Orthographic rules, on the other hand, are used to make a word conform to certain phonetic or other conventions, apart from grammatical considerations. Moreover, orthographic rules may apply across different grammatical paradigms.
For example, when adding an "s" to a word ending in "y" in the English language (e.g., "fly" or "army"), there is a spelling rule to follow: change the "y" to "i" and add "es" (e.g., "flies" or "armies"). That rule generally applies in both pluralizing nouns and conjugating verbs. In the French language, an orthographic rule governs the phonetic softening of the letter "c" as it appears in words, at times replacing the "c " with a cedilla "c". If the "c" "n" appears in a French word form and is followed by the letter "a", "o" or "u", a cedilla must be used, as in the noun form le garcon and the present tense first person plural form of the verb nous placons. In such cases, both the inflectional paradigm form construction rule and the orthographic rule govern the formation of the inflected form.
In any language, some word forms are exceptional and do not inflect according to any paradigm. People simply learn these irregular inflections, as for example, the conjugations of the present tense forms of the French language verb etre:
In English, everyone knows that nouns are pluralized by adding an "s", but there are many fish, many sheep and many other groups of words to which neither a grammatical paradigm nor an orthographic rule applies.
People who are familiar with a natural language are generally skilled in using the inflectional paradigms and spelling rules (usually learned in grammar school). They are quick to recognize and form words within a grammatical context by manipulating inflectional paradigms and spelling rules and, when necessary, remembering the exception forms. For example, when a person comes upon a word in a book that she does not know, she must manipulate the word form found in the text, and determine a corresponding citation form, in order to look up the word in a dictionary. Even an unabridged dictionary for a given language does not list and define every inflection of every word. Rather, dictionaries generally provide a single entry for each word, identifying each entry with only the citation form. For example, the citation form for English verbs is the infinitive form; for English nouns, it is the singular form. With each citation, the dictionary provides, in addition to the citation form, information on a word, such as its part of speech characteristics, a definition, and some inflectional variants of the word. Thus, a dictionary is a source for all basic forms of a word, but only the basic forms. Morphologists define a lexicon to be a source of basic word forms, such as an unabridged dictionary. With a lexicon and a set of paradigms a person can inflect all of the possible word forms. People can inflect forms for even unfamiliar words, if they know that the unfamiliar word inflects according to a known paradigm.
Moreover, people easily remember and use the grammatical construction and orthographic rules, because the construction rules they have learned capture the linguistic generalities of a natural language. Orthographic rules are not specific to inflectional paradigms, but, rather, apply across paradigm boundaries. In some cases, a given orthographic rule applies only to a subset of all the words which otherwise fit the context specified by the orthographic rule. In such cases, information on whether particular inflections adhere to an orthographic rule must be remembered (or looked up in a dictionary). Additionally, the concept of word formation using inflectional paradigms, based on the taking of a base form of a word (such as a citation form) and creating an intermediate stem form to which affixes are added, applies across all paradigms. Those rules for constructing forms can be reused, as a general matter, to generate forms within the same paradigm, and sometimes in different paradigms. Thus, by reducing the myriad of inflected forms down to a relatively small number of form construction techniques, applicable across different paradigms and orthographic rules, the linguistic generalities inherent in any natural language may be captured in a way that helps people master the language.
In the fields of information management and data processing, applications have been developed to perform morphological analysis on natural language text, attempting to replicate the functions that people do every day. There are many applications where the ability to manipulate word forms while maintaining data on the morpho-syntactic properties as people do is important and useful. For example, morphological analysis has been used in information retrieval systems, where the words of a text file are indexed by the citation form of a word or some partial stem. In those systems, a text file search is performed by deriving a citation form or stem form of the word, and searching for entries under that citation form index. Manipulation of word forms is also important in on-line dictionary and thesaurus systems, where a word form is provided and a dictionary entry is retrieved by generating an associated citation form or other lemma indicator. In other systems, tracking the morpho-syntactic properties of a word is also important. For example, in database systems that permit queries in a natural language (where the meaning of the words in a query is important), morphological text analysis has been used to process them by taking each surface form found and generating a citation form or lemma identification for the word and the corresponding morpho-syntactic properties. Maintenance of morpho-syntactic information is also important in machine translation systems (in which text passages are translated from one natural language to another), where a surface form in one language is found in a passage and translated to another language in a form having the same morpho-syntactic properties.
Generally, a computer-based system for morphological analysis of text begins with a lexicon (i.e., a set of base word forms) associated with a set of form construction rules. The hope is to build a system to do some of the things people do almost automatically: inflectional recognition and inflectional generation. Inflectional analysis is the process of taking a word form as it appears in text (i.e., a surface form), recognizing or deriving the morpho-syntactic properties of that form, and locating its family of word forms (i.e., lemma). Inflectional generation is the process of generating a particular surface form with specific morpho-syntactic properties, given a citation form in a lexicon and a set of construction rules. Additionally, there has been effort to design in an elegant way the system for morphological analysis. If possible, the design of the morphological system should support multiple natural languages. Additionally, the programming or specification of the inflectional language should be easily accomplished. If possible, the specification should follow as closely as possible the easily understood system of using grammatical rules and spelling rules, (found commonly in grammar books) and applying them to basic forms found in a lexicon source (usually the dictionary). That way anyone familiar with a natural language, not exclusively those versed in computer programming techniques, could specify a description of a language's inflectional morphology and build a system. Additionally, if the method for specifying a description of the inflectional morphology and the lexicon of a natural language permitted a compact description, there would be no maintenance problem in adding new words to the lexicon and associating them with appropriate grammatical and spelling rules. However, the currently available systems for morphological analysis present incomplete and non-elegant solutions to the problem of providing morphological text analysis in information management and data processing systems.
In terms of functionality, some of the currently available systems cannot be used for both inflectional recognition and inflectional generation. And in terms of system design, the currently available systems generally use non-intuitive, highly contrived formalisms to describe the inflectional morphology of a given natural language, that often fail to take advantage of the linguistic generalities that are inherent in the language, resulting in systems that map poorly to the morphological specifications found in grammar books. Such systems can have serious practical drawbacks. For example, some of the currently available systems for morphological analysis incorporate a design that does not use paradigms. Without explicit paradigms, some valuable linguistic generalizations are lost and updating the lexicon with additional words may become a burdensome process. Other systems employ paradigms which consist of highly artificial or limited construction rules. These systems have serious practical drawbacks in that they do not incorporate features to take advantage of linguistic generalizations inherent in the language.
As discussed above, people remember paradigms for grammatical construction separate from orthographic rules that sometimes apply across paradigms. Moreover, because many paradigms differ in construction rules for only a few forms, paradigms can be arranged in hierarchies where the form construction rules of a "general" paradigm can be reapplied in other paradigms with certain exceptions. Thus, paradigms could be specified to inherit form rules of other paradigms. The use of features such as the specification of Orthographic rules, separate from the paradigm, and paradigm inheritance of form construction rules, would enable a system to be created that would map well to grammar books, and would permit compact and easy specification and updating by anyone familiar with the language. However, to date the presently available systems have yet to provide an elegant solution. For example, even in those currently available systems where orthographic rules are separated from form construction rules, the user must either explicitly specify links to the orthographical rules or transform each lexical entry into some equivalent, but highly artificial, lexical representation to provide a link to an orthographic or spelling rule--both non-trivial burdens on users who maintain the system and populate it with new words.
Moreover, some of the design choices used in presently available systems prevent them from being used with multiple languages. In some systems, an approach is taken for a specific language like English (which is not highly inflected) that is useless in creating a system for languages like Russian or German (which are both highly inflected). In other systems, the syntactic and grammatical features are hard-coded so that the system must be reprogrammed using a computer programming language each time that system is argumented to process words in a different natural language.
Thus, there is a need for a system to perform morphological text analysis which provides the functionality of both inflectional recognition and inflectional generation and also incorporates design features that would take advantage of the linguistic generalities found in many languages. The creation of such a system would be a useful advance to the field of information management and data processing.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus to perform morphological text analysis functions, including inflectional generation and inflectional recognition, by incorporating a design that supports multiple natural languages and enables users to specify the language description in compact terms that map well to grammar book descriptions. The invention comprises a number of components, including an M language syntax, used in specifying a description of the inflectional morphology of a natural language, a compiler module, used by a computer processor to transform the user-specified language description into a data structure that is used by the computer to perform the functions of morphological analysis, and a pair of generation and recognition modules, used to perform the functions of morphological analysis, using the compiled data structures and lexicon of the natural language. The present invention can be arranged to perform the functions of morphological analysis as part of a larger information management or data processing system such as, for example, in a text retrieval system or machine translation application.
In a rule specification phase, the present invention provides the user with the ability to specify a description of a natural language, using the syntax of the M language. The syntax of the M language takes advantage of the linguistic generalities inherent in a natural language, permitting the user to express rule-sharing relationships between inflectional paradigms, express generalizations over word forms, as well as share separately declared orthographic rules between paradigms. The rule statements can be specified by the user in a compact way that maps well to the language descriptions commonly found in grammar books. With the present invention, maintaining the lexicon and the language description is not a burdensome process, and can be performed easily by one who is acquainted with language. In a compilation phase, the compiler module, comprising executable program statements and data structures, enables a computer processor to read the compact, textbook-like language description and produce from it a data structure that can be used for computer-based morphological processing. In a process that is invisible to the user, the compiler module integrates the language constructs by arranging the form rules of each paradigm into a hierarchical transition network through the processes of "disambiguation," and "form rule inheritance" which expands form sets into equivalent sets of rules, making entry points into the corresponding lexicon from lexical stem references in the form rules and "conflating" possible spelling form variations into the form rules after matching the form rules to the orthographic rules based on operator affix and context. The process of "conflating" involves the automatic creation of additional variant form rules to map the application of a spelling rule to a given form construction rule. Additionally, the compiler module enables the computer processor to construct a discrimination net which is used in the process of morphological recognition.
The functions of inflectional recognition and generation are performed by the recognition and generation modules of the present invention: each is comprised to use the data structure of the described rules and the lexicon. All aspects of the present invention will be described in detail below.
BRIEF DESCRIPTION OF THE FIGURES AND APPENDICES
FIG. 1 Depicts an exemplary embodiment of the data structures and computer program modules of the present invention as used in conjunction with a text retrieval system;
FIG. 2A Depicts an overview of an exemplary process flow for the compiler module of the present invention;
FIG. 2B Depicts an exemplary process flow for the right-hand-side "disambiguation" and chaining functions of the compiler module of the present invention;
FIG. 2C Depicts an exemplary process flow for a form rule inheritance feature of the compiler module of the present invention;
FIG. 2D Depicts an exemplary process flow for a form rule inheritance processing feature of the compiler module of the present invention;
FIG. 2E Depicts an exemplary process flow for a form rule divergence check feature of the compiler module of the present invention;
FIG. 2F Depicts an exemplary process flow of a cycle check and feature propagation function of the compiler module of the present invention;
FIG. 2G Depicts an exemplary process flow of an orthographic rule "conflation" function of the compiler module of the present invention;
FIG. 2H Depicts an exemplary process flow of a discrimination net building function of the compiler module of the present invention;
FIG. 2I Depicts an exemplary process for the addition of an affix string into a discrimination net according to the present invention;
FIG. 2J Depicts an exemplary process flow of a discrimination net terminal node addition function of the compiler module of the present invention;
FIG. 2K Depicts an exemplary process flow for a procedure for the addition of form rule variant into a discrimination net according to the method of the present invention;
FIG. 2L Depicts an exemplary process plan for a process to add a string element of an affix sequence variable into a discrimination net according to the method of the present invention.
FIG. 3A Depicts an exemplary overall process flow of a morphological recognizer module of the present invention;
FIG. 3B Depicts an exemplary process flow for the discrimination net processing function of the morphological recognizer module of the present invention;
FIG. 3C Depicts an exemplary process flow for a stem rule application function of the morphological recognizer module of the present invention;
FIG. 3D Depicts an exemplary process flow for a form rule application function of the morphological recognizer module of the present invention;
FIG. 3E Depicts an exemplary process flow of an affix application function of the morphological recognizer module of the present invention;
FIG. 3F Depicts an exemplary process flow of the affix variable application function of the morphological recognizer module of the present invention;
FIG. 3G Depicts an exemplary process flow for an affix sequence application procedure of the morphological recognizer module of the present invention;
FIG. 3H Depicts an exemplary process flow for an affix sequence matching procedure of the morphological recognizer module of the present invention;
FIG. 3I Depicts an exemplary process flow for an affix sequence variable matching procedure of the morphological recognizer module of the present invention.
FIG. 4A Depicts an exemplary overview process flow of the form rule generation process of the morphological generator module of the present invention;
FIG. 4B Depicts an exemplary process flow of the procedure for stem string generation of the morphological generator module of the present invention;
FIG. 4C Depicts an exemplary process flow for the process of variant form rule string generation of the morphological generator module of the present invention;
FIG. 4D Depicts an exemplary process flow for the process of affix application to stem strings of the morphological generator module of the present invention;
FIG. 4E Depicts an exemplary process flow for the process of affix string generation of the morphological generator module of the present invention;
FIG. 4F Depicts an exemplary process flow for the process of surface string generation of the morphological generator module of the present invention;
FIG. 4G Depicts an exemplary process flow for the process of affix sequence generation of the morphological generator module of the present invention; and
APPENDIX I Lists an exemplary formal syntax for the M language of the present invention;
APPENDIX II Lists an exemplary set of user prepared declarative rules for the German language;
APPENDIX III Lists an exemplary set of user prepared declarative rules for the French language;
APPENDIX IV Lists an exemplary algorithm for the compilation module of the present invention;
APPENDIX V Lists an exemplary algorithm for the morphological recognizer module of the present invention; and
APPENDIX VI Lists an exemplary algorithm for the morphological generator module of the present invention.
DETAILED DESCRIPTION
FIG. 1 depicts an exemplary embodiment of the data structures and computer program modules of the present invention. A computer system is provided comprising a computer 2 coupled to an input device 4, such as a keyboard, and a display device, such as a screen monitor 5. The computer 2 comprises a processor 6 that is coupled to the input device 4, the screen monitor 5, and two storage devices, a main computer memory 8 and a secondary storage device 10. The processor 6 is configured to accept input from the input device 4, store input in either computer memory (8 or 10), and create and execute morphological analysis programming, using the data structures and program modules provided by the present invention. Although the present invention can be implemented on any computer system, in an exemplary embodiment of the present invention, a VAX 6000-410, manufactured by the Digital Equipment Corporation, configured to process using the VMS operating system, also manufactured by the Digital Equipment Corporation, provides the platform for the morphological text analyzer of the present invention. For more information on the 6004-010 and the VMS operating system, the reader is referred to the following publications: VMS User's Manual, Order Number: AA-6A 98B-TE, VMS Media and Extended Documentation Kit, Order Number: QA-001AA-H5, Digital Equipment Corp., Maynard, Mass.
Although the data structures and computer program modules of the present invention will be described in detail below, a brief overview of the system can be described as illustrated by FIG. 1. The present invention provides three operation phases: a rule specification phase, a compilation phase, and a run-time phase. In the rule specification phase, a user 14 employs the syntax of an M language 12 to specify, using the input device 4, the description of the inflectional morphology of a natural language, such as German or French. Additionally, the user stores in a database the word information entries that comprise a lexicon 22 that will be used in conjunction with the description of the inflectional morphology. The features of the M language 12 and the lexicon 22 are described in detail below. As input comprising statements of the M language 12 is accepted by the processor 6, it is first stored as a set of user prepared declarative rules 16 in the main computer memory 8 (while the user completes or edits his or her specification) and then stored in the secondary storage area 10 (until the compilation phase). The word forms and accompanying information contained in the lexicon 22 are also stored in the main computer memory 8 (during the specification phase) and then moved to secondary storage 22 (until the run-time phase).
In the compilation phase, a compiler module 18, comprising executable program statements and data structures, is used by the processor 6 to read the set of user prepared declarative rules 16 and produce from it a data structure comprising a compiled rule set 20. This data structure is used by the processor 6 in the run-time phase to perform the functions of morphological generation and recognition.
The result of the compilation process is the creation of a computer-manipulatable data structure that can be used, with the lexicon 22 to perform morphological processing. The data structure includes chains of form rules indexed by paradigms. As the form rules of one paradigm can be inherited by another, the present invention provides that associated with each form rule is the list of paradigms that "share" the form rule. Also associated with each form rule is a list of the morpho-syntactic properties of the form. Further, should an orthographical rule apply to a particular form rule, the present invention provides that "variant" form rules be associated with each form rule in the data structure, to enable the application of the orthographic rules in specific circumstances. The distinctive aspects of the compiler module 18 and the compiled rule set 20 are described more fully below.
In the run-time phase, the executable program statements comprising a morphological generator module 24 are used by the processor 6 to perform the function of morphological word form generation. As stated above, morphological generation involves the process of generating word forms, given a lexicon and a compile, d rule set to guide the generation of word forms. The computer program statements of the morphological recognizer module 26 are used by the processor 6 to perform the functions of morphological recognition. As stated above, morphological recognition entails the function of identifying one or more instances of a set comprising the word form, a paradigm identifier, a set of morphosyntactic properties, and a corresponding lemma (i.e., lexical entry) for a given surface form. The statements of the morphological recognizer module 26 enable the processor 6 to identify the lemma and the morpho-syntactic properties indicated by the surface form.
As stated above, the method and apparatus for morphological text analysis of the present invention has wide application in devices for information management and data processing fields, such as in machine translation systems, natural language processing systems, as well as on-line dictionary, grammar checking, and thesaurus systems. In an exemplary embodiment, FIG. 1 depicts the data structures and computer program modules of the present invention, used in conjunction with a run-time text retrieval module 28. In the exemplary embodiment, the processor 6 is connected to the run-time text retrieval module 28 and a plurality of database text files 29, comprising natural language text. Each surface form in the text is indexed according to its citation form. In such a system, the processor 6 prompts the user for a query, using the executable program statements comprising the text retrieval system and generates calls to either the morphological generator module 24 or the morphological recognizer module 26. For additional information on aspects of an indexed database retrieval system, the reader is referred to pending U.S. application, Ser. no. 07/723,229, issued as U.S. Pat. No. 5,251,316 entitled "Method and Apparatus for Integrating a Dynamic Lexicon into a Full-Text Information Retrieval System", filed on Jun. 28, 1991 and U.S. application, Ser. No. 07/472,245, entitled "A Direct Manipulation Interface for Boolean Information Retrieval", filed on Jan. 30, 1990, now U.S. Pat. No. 5,175,814 which are expressly incorporated herein by reference. The description now to follow will describe in detail ,the features of the present invention as outlined above.
Morphological Rule Specification
The M language 12, as stated above, enables the user 14 to specify a set of declarative rules 16 that describe the inflectional morphology of a given natural language. To write the description, the user 14 is provided with a syntax that will dictate the form and sequences of a set of declarative statements to describe the inflectional morphology of a natural language. APPENDIX I lists the formal syntax for the M language 12. This syntax enables a user to capture the linguistic generalities inherent in natural languages, because it permits: 1) the specification of a hierarchy of paradigms, where each sub- paradigm inherits the features and form construction rules of its parent; 2) the separate specification of orthographic rules, which include sets and variables, that apply across inflectional paradigms; 3) the use of intermediate and surface form rules; 4) the specification of features which describe the morpho-syntactic properties associated with a form construction; 5) the ability to override intermediate form rules (as well as surface forms) in certain exceptional cases with entries in the lexicon; 6) the ability to declare affix variables (which will be described below); and 7) the ability to use form sets (also described below) in presenting a declaration. With the M language 12, the user 14 can specify a compact morphological description that maps well to a description found in grammar books, and thus mastery of the M language 12 syntax does not require a degree in computer science, only mastering of the basic grammatical and orthographical rules of a natural language. The user 14 who builds the description can be any person well-versed in natural language, such as a professor or a writer, APPENDICES II and III list partial descriptions of a set of user declared rules 16 for the German and French languages, respectively. Various aspects of the M language 12 syntax will now be discussed with reference to examples appearing in those appendices.
The user 14 specifies a set of prepared declarative rules 16 that provide a morphological description of a natural language, using the set of M language 12 statements, organized into a set of input data called a rule set. A rule set includes a declaration of a rule set name and a set of elements including paradigms and orthographic rules as follows. An M language 12 paradigm declaration has the following exemplary form:
Each paradigm is identified by a name and contains a number of sub-declarations.
The basic components of the paradigm declaration are the form construction rules. The present invention provides for surface form rules (which describe the construction of forms that appear in text) and intermediate forms rules (which describe the construction of forms which may never appear in text, but which are useful, because they are basic forms used as steps in the construction of surface forms. In addition, the present invention provides for the declaration of a lexical form, which is stored directly in the lexicon, but which is referenced in the paradigmatic form construction rules by the "LEX" identifier, as will be described below.
A form rule in the M language 12 declaration comprises a left-hand-side (LHS) <form-name> which can be any indicator of a particular inflection, such as "pres-1s," or a simple identifier such as "X", and a number of right-hand-side (RHS) components. The right-hand-side <form-body> may assume one of several formats, as follows:
Where <form-op > is either a plus (+) or minus (-), indicating whether the affix is being added or removed; <affix> is either a string (enclosed in quotes) or the name of an affix.sub.-- var (to be described below); and <stem > is the name of a form.sub.-- set or form that resolves in one or more steps into a stem in the lexicon (i.e., a form that was generated from a form the <form-body> of which comprises LEX). NIL, used only in paradigms that inherit forms from a parent paradigm, indicates that the given form does not exist in the current paradigm. An example use would be for the French verb pleuvoir, which exists only in the third person singular. Its other forms would have a NIL value. Thus, the form construction rules of both surface and intermediate forms distinguish between two major categories of strings: stems, which are any forms which include the primary lexical base of the word, and affixes, which comprise the prefixes and suffixes which can be appended to a stem in the process of word formation. Once an affix is appended to a stem, however, the result is also a stem, since the result also includes the primary lexical base.
Examples of surface and intermediate form rule declarations for the French language in APPENDIX III are found in the paradigm named "verb.sub.-- root":
Notice that the surface form rule (pres.sub.-- 1s) is formed by taking a stem (BASE) and concatenating it with the affix ("E"). The present invention provides for the chaining of form rules: the stem (BASE) in the form rule is the identifier of an intermediate form rule (BASE), which is formed by taking a stem (inf) and stripping the affix ("ir") from it. The stem (inf) also identifies a surface form rule (inf). The right-hand-side (RHS) of the infinitive form is a (LEX) indicator which indicates that the form (inf) is constructed by accessing the lexicon 22 (FIG. 1) and locating a citation form. Thus, in the construction of the form (pres-1s) there is a chain (pres-1s) to (BASE) to (inf) to (LEX). This chaining of form rules from right-hand-side stem to left-hand-side form name permits a compact description of the language that maps well to grammar book descriptions.
Associated with each surface form is a set of one or more features that provide a description of the morpho-syntactic properties of that surface form. The M language 12 permits the specification of features with the <feat-spec> declaration as follows:
The <feat-spec > declaration comprises a number of feature-value pair specifications, where <feat > is an identifier of the feature and the <value > is the value for the feature. An example of a set of feature value pairs for the form rule (pres.sub.-- 1s) appears in the paradigm (verb.sub.-- root) in the French language user prepared declarative rules 16 listed in APPENDIX III:
The example contains a set of three form/feature pairs that are associated with the form rule (pres.sub.-- 1s). Each feature identifier (temps), (personne) and (nombre) describes the category of morpho-syntactic properties used by the associated form. The value declarations (e.g., present) provide specific morpho-syntactic properties for the form within the feature category. The feature/value pairs are associated with a form construction rule through the shared use of the same left-hand-side identifier (e.g., pres .sub.-- 1s).
As can be seen from the example above, the M language 12 syntax provides for form-features to be declared apart from the form rule in a form-feature declaration. To link the form-feature to a form rule, in such a case, form/feature pairs can be declared, as in the example using the form name with which it is to be associated. However, it is also possible that the form features be declared in the form rule itself as in the example found in the user prepared declarative rules 16 for the German language in APPENDIX II. The paradigm verb.sub.-- strong.sub.-- pref has the following declaration:
where unattached=true is the feature-value pair. The two declaration areas in the paradigm are provided merely for convenience, as sometimes it is more convenient (and more readable) to list the sets of feature-value pairs associated with a form in a separate section when there are many feature-value pairs. The format of the <feat-spec> is identical, regardless of whether it is placed within the form rule or in the form.sub.-- features section.
Additionally, multiple sets of feature-value pairs may be used for those cases where there is a single surface form for multiple "paradigm locations," e.g., in English we might have the following forms:
where the infinitive form (inf) is used in the right-hand-side of many different form rule constructions. In the exemplary embodiment of the present invention, form features used in a given rule set are specifically declared and a range of values must be assigned to each form-feature. Thus, in the paradigm, <feat> must have been previously declared in a separate feature values section and <value > must be one of the previously declared values for the given feature. Feature values are declared separately from paradigms as follows:
Where <value-list> represents a value followed by zero or more occurrences of a comma followed by another value. One or more features may be declared in this manner. An example in the English language is: tense=(present, past, future). In APPENDIX II there appears the following feature value set declaration from the user prepared declarative rules 16 of the German language:
The left-hand-side of each declaration identifies the category of morpho-syntactic property with which a word form can be identified (e.g., tense) The right-hand-side provides a set of possible values over which the feature identifier may range (e.g., the person category can be either first person, second person or third person.
Referring again to the declarations of surface and intermediate form rules, the <form.sub.-- body> and <feature-spec> declarations, a RHS argument of a form rule may in addition, contain one or more qualifiers. Qualifiers are used at run-time to indicate that a given lemma may override the given (intermediate) form rule with a string stored in the lexicon. The present invention provides an exemplary override statement:
This is used to indicate that the given form may be overridden by a stem in the lexicon; in the exemplary embodiment, it is used only for intermediate forms, as any surface form may be overridden by a lexical entry. For example, in APPENDIX III there appear the following forms in the paradigm verb.sub.-- root:
In constructing the form (FUT) for a given lemma, the syntax of the M language 12 dictates that the lexicon 22 first be searched to determine if there is a (FUT) entry for that lemma before the form rule (inf) is accessed to construct the form. If there is a form FUT in the lexicon 22 for a given lemma, that form will be used instead of following the inf construction chain, thus, allowing the lexicon form in that case to "override" the normal construction rule. If no FUT form appears in the lexicon 22 for the given lemma, the processing will continue using the form rule (inf).
As mentioned above, the present invention provides for a hierarchical organization of paradigms, whereby one paradigm may inherit some or all of the form construction rules of another paradigm. The "based-on" declaration (shown in the general paradigm declaration above) indicates the name of the paradigm from which the given paradigm inherits its rules. If the current paradigm is not based on any other paradigm, then that line is omitted. In the compilation phase, the processor 6 (FIG. 1) uses the compiler module 20 (FIG. 1) to process the statement based-on as a signal to incorporate form rules from the parent paradigm into the current paradigm according to the method of the present invention.
It is the left-hand-side of the form rule, i.e. the form-name, which governs which rules are inherited from a parent paradigm. Only those rules with form names that do not exist in the child paradigm are inherited from the parent. One can think of the rules in the child paradigm as overriding rules with the same form name from the parent paradigm. The ability to inherit and override not only surface forms but also intermediate forms (without requiring the restatement in the child paradigm of rules that use an overridden intermediate form but otherwise behave just like the parent rules) can greatly simplify and condense the rule set that a user need develop to describe a natural language such as French or German.
In addition, the present invention provides in a paradigm declaration two additional features for a compact description of an inflectional morphology: form sets and affix variable sets. Form sets represent a short-hand notation that sometimes can be used to declare a set of similar forms. Within a paradigm declaration, the M language 12 syntax provides that the form sets be declared as follows:
where the <form-set-name> identifies the form set specified on the right-hand-side. The <form-list> is a list of one or more of the form-names declared in the following sections or inherited from the parent paradigm, each separated by a comma. A typical declaration appears in the paradigm provided in the user prepared declarative rules 16 for the German language in APPENDIX II.
There are cases in which a'set of forms (instantiated by different strings and referring to different values of the same set of features) exhibit the same behavior with respect to form construction rules that use them to create new forms. In such cases, it may be useful to define a form set name to serve in form construction rules as a placeholder for any one of a set forms. The present invention allows one to define such a form set and use it wherever a stem can appear in the right-hand-side of a form rule, such as, for example, the declaration using the form set FINITE in the German language paradigm verb.sub.-- strong.sub.-- pref of APPENDIX II:
In the compilation phase, the processor 6 will take each form rule accessing a form set and "conflate" it with the members of the form set to create a new set of form rules, each having as features the union of features associated with the original form rule and the form set member. For example, the form finite-unattached.pres.sub.-- 1s, as described above, has the associated feature/value pair, personne=1, whereas the finite-unattached.pres.sub.-- 25 has associated with it the feature value pair personne=2. Representationally, the conflating process would yield:
A form whose derivation includes no form sets will be referred to as a "ground" form, since it always corresponds to a precise string with associated set (or sets) of feature values. A form constructed using a form set is known as a "variable form", since different instantiations of the form may correspond to different strings with different feature-value sets. Whenever a form set, or a variable form, is used in the right-hand-side of a form construction rule, the resulting left-hand-side form must be a variable form.
Form sets are a useful way of generalizing behaviors, since rules can be written which act on any of a set of forms, rather than requiring a separate rule to be written for each member of the set. However, it can also be useful to refer by name to the "ground" forms implied by a variable form. For this reason, the present invention permits a naming convention by which ground form names can be generated. It works as follows: the first time a form set is used to construct a variable form, the ground form names are the concatenation of the strings <variable form name>"."<form set member name>.
Affix variables (affix.sub.-- vars) are similar to form sets in that the variable represents a part of the form that varies in a generalizable way. Declarations of affix variables are permitted in the M language 12 to handle special cases when there are a small, fixed class of affixes whose value must unify with a value stored in the lexicon, such as for words with separable prefixes in German. However, in contrast to the form set whose scope is the part of the form that contains the lexical "stem", the affix variable ranges over a set of affixes. In APPENDIX II, an example of a declaration appears in the verb.sub.-- strong.sub.-- pref paradigm of the user prepared declarative rules for the German language:
As used in a form rule, the affix variable can be used where an affix might appear in the right-hand-side, as for example in the German language paradigm verb.sub.-- strong.sub.-- pref of APPENDIX II where the surface form past.sub.-- part is specified:
The affix variable sep.sub.-- prefix specifies a range of values that can be used in constructing the form past.sub.-- part. The affix.sub.-- var name (e.g., sep.sub.-- prefix) is treated as a feature which can be turned on or off using a lexicon reference, while the <affix-list>, which represents a list of all the possible affix strings, is treated as the range of all affix values. A feature/value pair consisting of an affix variable name and value may be used as a constraint by requiring it to unify with equivalent information stored in a lexical entry.
Referring again to the paradigm declaration above, the paradigm declaration also includes a use.sub.--`for.sub.-- instances field, which takes the value of "true" (or "yes") or "false" (or "no"). If the value is false or no, then the paradigm is used solely as a source for inheriting rules, i.e., there are no lemmas in the lexicon that are associated with the paradigm.
In addition to the declaration of paradigms, the present invention provides separate declaration syntax for orthographic rules. Orthographic rules are used to specify spelling changes that occur across paradigms and that are dependent on the orthographic or phonetic context, such as a silent "e" or accented final syllable, rather than on the specific grammatical construction patterns of a paradigm. Orthographic rules are declared as follows:
Where <rule-type> is either SUFFIX or PREFIX; <parameter> is the name of an orthographic feature, which may be prefixed by a tilde () to indicate negation; <lhs> is the left-hand-side of the rule; and <result> is the construction result that will occur when the rule applies. The form of the left-hand-side <lhs> of the orthographic rule is dependent on <rule-type>. In the case of a SUFFIX, the form of the rule is as follows:
Where <rule-op> is either a plus (+) or minus (-), to indicate whether the suffix is being added or removed; <affix> describes the orthographic constraints on any suffix satisfying the rule; and <context> describes the orthographic constraints on any stem satisfying the rule. The <affix>, <context> and <result> components each comprise a sequence (called an affix variable sequence) comprising any combination of literal strings (enclosed in quotes) and/or any variables declared in a VARS section, as is described below. The context and result sequences then become affix sequences in the form rule variants created during rule conflation. It is assumed that strings which match the <context>, <affix> and <result> components may extend beyond the specified segments, except in those cases of an affix literal value (i.e., a character or string of characters) that ends or begins in a pound sign (#), which indicates end of word for a suffix, or beginning of word for a prefix. For example, +["e"] [<context>] is interpreted as the addition of any prefix that ends with the letter e, whereas +["#ge"] [<context>] is interpreted as the addition of the prefix "ge."
As described above, the <context>, <affix> and <result> components in an orthographic rule declaration can contain character strings and/or variables. The M language 12 syntax provides that all variables used in the orthographic rules be previously declared in a separate declaration as follows:
Where <set-name> must be the name of a previously declared set (to be described below) and <var-list> represents the name of a variable followed by zero or more occurrences of a comma followed by the name of another variable. One or more var-lists may be declared in this manner. An example is:
where VOWEL identifies sets of characters or strings which must also be separately declared as follows. As used in the orthographic rule as an element in a <context>, <affix> or <result> sequence, the variables (vow1), (a.sub.-- or.sub.-- o), and (vow2) would be references to specific instances of members of the set VOWEL, i.e., variables which may be bound at run-time to one value of the VOWEL set. In the French language, for example, the user prepared declarative rules 16 in APPENDIX III, contain the following variable declarations:
As mentioned above the set names in the variable declaration are the identifiers of previously declared sets comprising characters and/or strings of characters. A set is specified in a declaration separate from the variable declaration and the orthographic rule declaration. Sets for use within orthographic rules are declared as follows:
where <member-list> represents a letter followed by zero or more occurrences of a comma followed by a letter. One or more sets may be declared in this manner. An example is: VOWEL=(A,E,I,O,U). In the user prepared declarative rules 16 for the French language, in APPENDIX III, the following sets are declared:
The set declaration provides a range of values over which the variables used in orthographic rules may range.
Referring again to the declarative form for an orthographic rule, if a given variable appears more than once within the orthographic rule, then the same value must be substituted for each occurrence. For example, the rule: PREFIX (GEM)+[vow1] [cons vow2].fwdarw.[vow1 cons cons vow2] means that when any prefix that ends in a vowel is added to a stem which has a positive value for the GEM parameter and begins with a consonant followed by a vowel, the consonant is doubled. Note also the use of vow1 and vow2 within the rule. The use of different variable names for the set of vowels indicates that they are independent of each other, i.e., the values need not be identical; although they may happen to be identical.
In the user prepared declarative rules 16 for the French language in APPENDIX III, there are many examples of suffix rules which use variables as affix and context components including:
This orthographic rule provides for geminating certain consonants that precede a mute e where the word ends in the affix "e" and is preceded by a vowel and one member from the set of geminating consonants (GEM.sub.-- CONS). The rule specifies that the geminating consonant is doubled where the context and affix of the left-hand-side occur. The variable (vowel) can range over the entire set of characters in the VOW set, and the variable (gcons) ranges over the values L,N,S,T in the set (GEM.sub.-- CONS).
If the orthographic rule applies to a PREFIX, the rule takes the form as follows:
where everything is as defined in the SUFFIX rule except that the context and affix components are reversed, as is the pound sign that indicates the end of the word.
An example of a prefix orthographic rule is found in the German language description in APPENDIX II:
The left-hand side of the rule comprises the rule operator (+), the prefix ["GE"] and the context [char]. In the context, char is a variable name used to specify a set of characters, or character strings, that would serve as possible contexts for the orthographic rule. The variable (char) would be declared in a separate declaration and associated with a set of range values.
The rule states that if the prefix "GE", is to be added to a word beginning with any letter and the word has a positive value for the NO.sub.-- GE feature, then the GE is dropped. If this orthographic rule applied to every form rule, then the GE prefix would never be applied. Notice that this orthographic rule only applies to certain words, as limited by the use of the parameter NO.sub.-- GE. The present invention provides that application of the spelling rules may be controlled by orthographic parameter features associated with lemma entries in the lexicon 22. Where the lexicon entry contains information showing that the parameter of the orthographic rule applies, only then will the spelling rule apply. For example, a lexicon entry for the German word studieren might contain the following information:
citation: studieren
paradigm: verb.sub.-- weak
stems: inf=studieren
orth.sub.-- features: NO.sub.-- GE=yes
The orth.sub.-- features entry contains the parameter NO.sub.-- GE and an indicator stating that the orthographic rule should apply in forming inflections of studieren.
The description of the M language 12 syntax above outlines the general declarative features of the language. In declaring the set of rules according to the constructs above, an exemplary embodiment of the present invention provides for the following additional syntax requirements. A rule set must include a rule name, a set of declared features with their respective range of values, and a set of paradigms. The rule set may optionally contain a set of orthographic rules and accompanying sets of variables and sets of values over which the variables may range. Additionally, the declaration of a rule set must be arranged in the following order, the rule set name, the feature values, sets (used for orthographic rules) variables, (used for orthographic rules) orthographic rules and paradigms. In declaring paradigms, a parent paradigm must be declared before its children.
The Lexicon
In addition to the user prepared declarative rule set 16 to describe a natural language, the user 14 must also specify a lexicon 22. In an exemplary embodiment of the present invention, the lexicon 22 is a database of word entries that are each associated with some paradigm in the user specified rule set 16. In an exemplary embodiment, the information retrieval program AI-STARS manufactured by Digital Equipment Corporation can be used to create the database entries. The word entries in the lexicon 22 contain identifiers following the syntax of the M language 12. The syntax of the M language 12 provides a connection to associate the appropriate information stored in the lexicon 22 entries with appropriate form rules. For example, in APPENDIX III the user prepared declarative rules 16 (FIG. 1) for the French language list some typical lexical entries:
A citation form (indicated by the "citation" by word) is used to identify the lemma. This string (e.g., sentir or pouvoir) should correspond to the form of a word one would use to look up a word in a regular dictionary. A citation form need not be unique. A noun and a verb may well share the same citation form. The name of the paradigm which describes the morphological behavior of the lemma is also provided in each lexicon to link the lexicon citation to the appropriate form generating rules. The user can specify in some cases one or more stem forms, to be used as starting points to derive the various inflected forms. For example, a regular verb (such as sentir above) might only require the infinitive stem to be specified in the lexicon 22, whereas a highly irregular verb (such as pouvoir above) may require stems for a number of forms. The English verb "run," for example, might require both the present stem "run" and the past stem "ran" to be stored in the lexical entry. Each stem stored in the lexicon 22 must be associated with the name of a corresponding form in its paradigm. Thus, for each stem, the present invention provides that a form name (the LHS of a form rule) must be provided in the lexicon 22. In this way, the present invention can map lexical stems to their proper use in the paradigm.
In addition, the present invention provides that features and values which are sometimes required by the user declared paradigms can be specified in the lexicon 22. Lexical override, discussed above, is one such feature where information in the lexicon 22 (other than the paradigm name, form name, and stem) is necessary to constrain morphological processing.
Parameters are another type of feature, pertaining to the application of an orthographic rule, that can be specified in a lexical entry. For example, the lexicon entry for the German word studieren, described above, contains the parameter (NO-GE) corresponding to an orthographic rule parameter, thereby indicating that the orthographic rule should apply in forming inflections of studieren. When a parameter is declared in an orthographic rule, a lexical entry for a word must contain a corresponding parameter value in order for the spelling rule to apply. Using this feature, the user is able to easily control the application of the orthographic rule to only the appropriate words.
Optionally, a lexical item may contain other kinds of information. For example, a lexicon entry can contain features and values which are independent of the paradigm, For example, if the gender of a French noun is not altered or determined in a paradigm (via affixation), then the gender of the noun may be indicated via a feature/value pair stored directly in the lexicon, as for example: "chapeau"gender=masc. Additionally, a lexical entry may contain pointers to word senses. A lemma may have one or more word senses, which are stored in the lexicon 22 as independent objects, and other syntactic information, such as subcategorization classes.
Referring again to FIG. 1, the user 14 inputs both a set of prepared declarative rules 16 according to the syntax of the M language 12 and a set of lexicon entries 22 as described above. This input is stored in the secondary storage location 10 until the compilation phase processing begins.
Rule Set Compilation
a. Overview
In the compilation phase, the processor 6 (FIG. 1) uses the executable statements and data structures comprising the compiler module 18 to read the set of user prepared declarative rules 16 and create the compiled rule set 20, which can be used for all phases of run-time morphological processing. FIGS. 2A-2I depict exemplary process flows for the various steps of compiling the set of user prepared declarative rules 16, such as those for the German language in APPENDIX II or those for the French language in APPENDIX III. Moreover, FIGS. 2A-2I depict the flow of control that the processor 6 follows in using the compiler module 18 to create a computer-manipulatable data structure to perform morphological processing. Additionally, a high-level description of the compilation process is presented in the exemplary algorithm listed in APPENDIX IV.
When the compiler module 18 (FIG. 1) is invoked by a user command, the processor 6 retrieves the set of user prepared declarative rules 16 and processes them according to,the statements in the compiler module 18. FIG. 2A depicts an exemplary process flow for rule-set compilation and provides an overview of the entire compilation process, the flow of control dictated by the statements of the compiler module 18. In step 40, the processor 6 uses the statements of the compiler module 18 to create the compiled rule set 20, initially comprising a parse tree. A parse tree is a heirarchical representation of the data contained in the user prepared declarative rule set 16. The root of the tree represents the top of the hierarchy and the elements of the user prepared declarative rules 16 are represented as nodes of the tree in levels. In the first level down from the root, the primary elements of the user prepared declarative rules 16 are grouped into categories identified by the nodes: feature values, sets, set variables, orthographic rules and paradigms. Below each categorization node, is a node for each declared element (e.g., a node for each of the declared paradigms). In the level below each declared element, there is a node corresponding to each of the components of the element. For paradigms, there would be nodes, for example, identifying surface form rules and intermediate form rules. Attached at the lowest nodes are leaf nodes containing the most specific data. For example, under each form rule node is a leaf node containing the value of the form operator (i.e., + or -). The tree, during the compilation process, evolves into the data structure that is the compiled rule set 20 by the operations described below.
With the set of user prepared declarative rules 16 parsed in step 40, the processor 6, in step 42, begins a loop to further process each declared paradigm identified in the tree data structure. In step 44, the semantic type of each component in the right-hand-side (RHS) of every form rule is "disambiguated" and, where appropriate, "chained" by a procedure that is described in detail below in FIG. 2B. As mentioned above, a form rule comprises a left-hand-side identifier of the form (the form name) and a set of right-hand-side construction components, i.e., a stem and, optionally, an affix and, if the affix is present, an operator. The right-hand-side stem can be an identifier, i.e., the left-hand-side (LHS) name of another form rule or a form set, and the RHS affix can be an identifier of an affix variable (affix.sub.-- var). This is illustrated by the chain of references from (pres.sub.-- 1s) to (BASE) to (inf) to (LEX) in:
Disambiguation is the process of taking the identifiers of other form rules or form sets or affix variables (affix.sub.-- vars) and creating actual references or links to the appropriate data structures. The disambiguation process creates a chain of references between form rules, representing the steps of its construction. The chain must terminate with a lexical form indicator "LEX" to signal that a character string is stored in the lexicon. Disambiguation replaces the stem form names with links to the actual form rule data structures that represent the different form rules. Also, in the case of affix variables, a feature comprising the affix variable name gets associated with the form rule. The syntax of the M language 12 treats the affix variable name as a feature and the set of associated affix strings is treated as the range of that feature's value. This feature must be associated with each form that references the affix variable. The syntax is necessary because the value of the affix is dependent on the lemma. Therefore, the value must be obtained during generation so that the appropriate affix is used during form construction; during recognition, the value is obtained by matching the surface string against each value of the affix variable. Then that value must match the value associated with the lemma in the lexicon, i.e., that value is a feature constraint that must unify with the features of the lemma found in the lexicon. The disambiguation process is described in detail below in the discussion pertaining to FIG. 2B.
Referring again to FIG. 2A, after the form rules have been "disambiguated" (in step 44) the paradigm processing loop (step 42) continues in steps 46 and 48 to process any paradigms containing the statement "based-on" for form rule inheritance. In addition to form rule chaining, the present invention presents a method and apparatus for paradigm inheritance, in which one paradigm (a sub-paradigm) inherits the form rules contained in another paradigm (a super-paradigm). In step 46, the processor 6 determines whether the currently examined paradigm is "based-on" another paradigm by searching for a (based-on) declaration in a leaf node of the tree branch (in the data structure that is evolving into the compiled rule set 20) of that particular paradigm. If, in step 46, a (based-on) declaration is found, then in step 48, a form inheritance procedure is invoked. The inheritance procedure, which is explained in detail below with reference to FIGS. 2C-2E, creates references to the appropriate data structures that will allow the current paradigm (sub-paradigm) to "share" the form rules of its super-paradigm. Upon completion of the form rule inheritance process, each "shared" form rule node in the tree data structure contains a list of all the paradigms that share it.
Referring again to FIG. 2A, the paradigm processing loop (begun in step 42) continues after the form rule inheritance procedure (steps 46 and 48) with the expansion or "conflation", in step 50, of any form set that is referenced by any form rule. In step 50, form set conflation comprises the process of expanding or filling out the compact descriptions of the user declared form rules 16 by replacing each form rule that contains a RHS reference to a form set with a set of form rules, one form rule for each member of the form set. For example, the user 14 might declare the following form set, intermediate form rules and surface form rules in a paradigm:
The form set DEGREE is referenced in each of the three surface form rules: nom.sub.-- msing, gen.sub.-- msing and dat.sub.-- msing. The form set DEGREE includes references to three intermediate form rules POS, COM and SUP. The form set conflation process replaces the three surface form rules that reference the form set DEGREE with the following set of surface form rules:
For each surface form previously listed, there are now three surface forms--each corresponding to one of the references in the form sets. Each surface form is uniquely identified on the left-hand-side (LHS) by using the prior form name concatenated with a form set member identifier.
Referring again to FIG. 2A, after the form set conflation procedure of step 50, the paradigm processing loop (begun in step 42) continues in step 52 with the final step of checking all form rules of a paradigm for cycles. The cycle detection step comprises a process of taking each form rule and following the chain of form rule references to make sure that no reference to a form rule is repeated within the chain. As each form rule must eventually chain back to a LEX indicator that signals a string in the lexicon, a repeated reference to a form construction rule in the chain indicates that the form rule will cycle rather than map back to a string form. For example, the following declarations would be an incorrect declaration for verbs in the French language:
This example provides the following nonsensical chain of (pres.sub.-- 1p) to (inf) to (BASE) to (pres.sub.-- 1p) and is an illegal declaration according to the exemplary syntax of the M language 12. The process is to begin with the surface form rules for each paradigm and chain back through the form references, checking for repeated references.
During the cycle checking process, the present invention also provides a method and apparatus for propagating any morpho-syntactic features associated with intermediate forms up through the chain to the surface forms. When a surface form is constructed by a succession of form rules, it would be possible to simply associate all the grammatical features of the result with the surface form itself. However, it is sometimes the case that it is advantageous to associate some subset of the final set of features with one or more intermediate forms. For example, in German, a user might construct the imperfect tense surface forms in two steps, first constructing an imperfect stem, then appending suffixes to it to indicate person and number:
The task is to indicate that the surface forms imp.sub.-- 1s, imp.sub.-- 2s, and imp.sub.-- 3s also carry the imperfect tense as a feature value. The present invention provides a default mechanism to pass feature values from included stems to resulting forms. Any form constructed using the append operator (+) will, by default, also include the features of its stem form rule without the user having to explicitly include those features in the list of features associated with the resulting form. This process is called "feature propagation", because features from intermediate forms are propagated to any forms which utilize them in their construction. Feature propagation is a notational convenience, obviating the need to specify certain features many times in resulting forms when they can be specified once in an intermediate form and propagated automatically to the resulting forms. It also reflects well, from a linguistic standpoint, how the grammatical interpretation of a surface form is built up from its parts. Feature propagation does not occur across construction rules using the removal (-) operator. Typically, the removal operator is employed to create new base strings by removing affixes. Hence, it would be unusual to desire features to propagate across such operations.
Referring again to FIG. 2A, the processor 6 begins a process for cycle checking and feature propagation as follows. In step 52, the processor 6 searches for surface form rule nodes in the tree data structure (which is evolving into the compiled rule set 20) to determine if all the form rules for a given paradigm have been processed. If so, the processor 6 proceeds, in step 59, to a get next paradigm, and the flow of the process returns again to step 42, to begin processing another paradigm. If, in step 52, all the form rules for a given paradigm have not yet been checked, the processor 6, in step 57, will get another form rule from the tree data structure. Then, in step 58, the processor 6 will call a cycle check/feature propagation procedure to determine if the chain of form rule references is free of cycles and to propagate features (for form rules with a + operator) in a procedure described in detail below with reference to FIG. 2F. If the procedure invoked in step 58 encounters a cycle in the form rule in question, the processor 6 generates an error in step 60 and then returns to step 52 to process another form rule, until all form rules for a paradigm are processed.
After the cycle check and feature propagation procedures described in steps 52-60 in FIG. 2, processing of that paradigm is complete. The processor 6 then returns to step 42 to determine if there are other paradigms to process, and if so, the processor 6 will execute steps 44-60 described above.
When, in step 42, the processor 6 finds that all paradigm form rule processing is complete, the processor 6 will then proceed, in step 54, to "conflate" the orthographic rules with the form rules. A feature of the present invention is the fact that orthographic rules are described separately from the grammatical paradigms. The compiler plays a special role in permitting the user to freely declare orthographic rules apart from grammatical construction paradigms in that it automatically compares each orthographic rule with each form rule to determine to which form rules each orthographic rule might apply. To make this determination, the processor 6, in step 54, will compare the affix and operator in the left-hand-side of the orthographic rule with the operator and affix in the right-hand-side of the form rule. Once the processor 6 determines in step 54 that set of "matching" form rules, the processor 6 cycles through the set, conflating the orthographic rule with each form rule, in a process that will be described in detail below in FIG. 2G, creating an inner variant intermediate form rule and an outer variant form rule of the same type as that of the matching form rule to map the correct spelling of the word to the grammatical construction in a process as described below. If the orthographic rule contains a parameter, that parameter is associated with the newly created outer variant form rule.
After the processor 6 performs the steps of orthographic rule conflation in step 54, the process of compilation is completed, in step 56, by building a discrimination net that is incorporated as a branch of the tree structure of the compiled rule set 20. A discrimination net is a standard data structure used in artificial intelligence programming and is commonly used by systems for morphological recognition. The present invention creates a discrimination net to index the final suffixes of those surface form construction rules having a plus (+) operator in the right-hand-side, and additionally stores together references to those surface form rules having a minus (-) operator on the right-hand-side or a prefix in a "non-netted" form rule set that is also included in the data structure of the compiled rule set 20. Additionally, in step 56, the processor 6 provides references in the discrimination net to corresponding surface form rules, stem form rules and shared paradigms. The process of building the discrimination net is described more fully below with reference to FIGS. 2H-L.
Once the discrimination net is complete, the processor 6, in step 61, stores that discrimination net, along with the rest of the compiled rule set 20 (FIG. 1), in the secondary storage area 10 (FIG. 1). Compilation phase processing is now complete, and the processor 6, in step 62, will return and commence a run-time phase upon user command. However, the processes of disambiguation and chaining, form inheritance, cycle checking, orthographic rule conflation and discrimination network building are described in detail below.
a. Right Hand Side Disambiguation and Chaining of Form Rules
In FIG. 2A, step 44, the processor 6 invokes a procedure to "disambiguate" and create form rule "chains", using the right-hand-side (RHS) of each form rule in a paradigm. FIG. 2B depicts exemplary process flow for the right-hand-side form rule disambiguation and chaining process of step 44 in FIG. 2A. The process of disambiguation is to take each component of the RHS of a form rule, and if that component has as its value an identifier, find the corresponding structure (i.e., form rule, form set or affix variable (affix.sub.-- var)). In the case of a form or affix variable name, the processor 6 will replace the name with a reference to the actual form rule or affix variable data structure in the compiled rule set 20. As stated above, the syntax of the M language 12 (FIG. 1) treats the affix variable name as a feature and the set of associated affix strings are treated as the range of that feature's values. This is necessary because the value of the affix is dependent on the lemma.
Therefore, the value must be obtained during generation so that the appropriate affix is used during form construction; during recognition, the value is obtained by matching the surface string against each value of the affix variable. That value must unify with the features of the lemma.
In the case of a form set name, a reference to the form rule stem is stored for subsequent form set conflation. Referring to FIG. 2B, the processor 6 begins a loop to process the form rules of each paradigm on a paradigm by paradigm basis. In step 70, the processor 6 checks whether all form rules for a given paradigm in the processing loop of FIG. 2A have been processed. Referring to FIG. 2B, if in step 70, there is an unprocessed form rule, the processor 6, in step 72, will retrieve the form rule from the corresponding node in the tree data structure (which will become the compiled rule set 20). In step 74, the processor 6 begins a loop to process each RHS component of the form rule. If there is a component not yet processed, the processor 6, in step 76, will get the next component. In step 78, the processor 6 determines whether or not the RHS component is an identifier to be disambiguated. If the component is not an identifier (i.e., it is either a literal string, the special indicator NIL (meaning the form rule does not exist in the paradigm) or the special indicator LEX (meaning that the form is stored in the lexicon 22), the processor 6 will stop processing that current RHS component and return to step 74 to process another RHS component if there is one.
Referring again to step 78, if the current component is an identifier, the processor 6, proceeds to step 80 and makes a determination of whether the identifier is a form name. As described above, a form name is the left-hand-side identifier of a form rule (e.g., "pres.sub.-- 1s"). If so, the processor 6, in step 82, will replace the string of characters representing the stem in the form rule node of the tree data structure with a reference to the actual (stem) form rule. To find that form rule in step 82, the processor 6 will search the set of form rules of the current paradigm, and if it is not found, then proceeds to search hierarchically for "ancestor" paradigms of the current paradigm. An ancestor paradigm is the immediate super-paradigm of the current paradigm (as determined by the based-on statement) or an "ancestor" paradigm of that super-paradigm. Once the string identifier in the component is replaced in step 82 with an actual reference, the processor 6 will return to step 74 to process another RHS component.
Referring again to step 80, if the identifier is not a form name, the processor 6, in step 84, will next determine whether the identifier is a form set name. As described above, a form set can be used as the RHS stem to identify a group of form rules which represent a similar type of form construction. If, in step 84, the identifier is a form set name, the processor 6, in step 86, will place the reference to the component (i.e., form rule stem) in a special node of the tree data structure for subsequent processing. The form rule containing that form set identifier will be replaced later in step 50 (FIG. 2A) with a set of form rules, one for each member of the form set. Next, the processor 6, after completing step 86, proceeds to the beginning of the component processing loop, step 74, to process any remaining RHS components of the current form rule.
Referring again to step 84, if the identifier is not a form set name, the processor 6, in step 88, will determine whether or not the identifier is an affix variable name. As described above, an affix variable represents a set of possible affix strings that could be applied in a particular form rule construction. If in step 88 the identifier is an affix variable name, the processor 6 will replace, in step 90, the string in the stem of the form rule node with a reference to the actual location in the tree data structure of the compiled rule set 20 corresponding to the affix variable and associates with the form rule a feature comprising the affix variable name. After step 90, the processor 6 returns to the beginning of the component processing loop (step 74).
If in step 88 the processor 6 determines that the component is not an affix variable identifier, in step 92 the processor 6 will generate an error, because the component is not one of the legal forms as either a string, a NIL indicator or a LEX indicator, form rule identifier, form set identifier, or affix variable identifier.
Referring to step 74, when all form processing is complete, the processor 6 will return to the beginning of the form rule processing loop (step 70) to process the RHS components of the form rules as described above. When each form rule has been processed, the processor 6, returns to step 44 in FIG. 2A.
b. Form Rule Inheritance (With Cycle Checking)
Referring again to FIG. 2A, in step 48, the processor 6 performs the form rule inheritance procedure. FIGS. 2C-2F depict exemplary process flows for the form rule inheritance procedure. Form rule inheritance, as described, permits the form rules of the present invention to be re-used, or shared, by different paradigms. Where the processor 6 encounters the "based-on" declaration in a paradigm, the processor 6 will perform the process as follows.
In step 46, (FIG. 2A) the processor 6 will search the current paradigm branch of the tree data structure (which will become the compiled rule set 20 (FIG. 1)) to locate a "based.sub.-- on" declaration, i.e. "based.sub.-- on: <parent.sub.-- paradigm>". If one is found, the processor 6 will pass control to the process flow as depicted in FIG. 2C, to step 100, retrieve the form rules from the super-paradigm, and, in step 102, begin to process those form rules that have not been "superseded" by the sub-paradigm referenced in the "based.sub.-- on" declaration. A form rule (declared in the super-paradigm) is superseded when a form rule with an identical LHS is declared in a sub-paradigm. If the form rule has not been superseded, then it is checked for divergence. A divergence check takes the form rule to be inherited and goes back through the chain of stem form rule references to see whether any intermediate form rules in the chain have been superseded in the current paradigm. If so, then an additional branch (a reference to the divergent form rule) must be added to the reference chain in the inherited form rule. Both the form rule screening process and divergence check are described in detail below with reference to FIGS. 2D and 2E.
Referring again to step 102 in FIG. 2C, once the screening out of superseding form rules and the divergence check of inherited form rules is complete, the process, in step 102, will yield a set of form rules from the super-paradigm that will be "inherited" or "shared" by the sub-paradigm. In the tree data structure of the compiled rule set 20, each of the data structures for the inherited form rules of the super-paradigm will contain a "shared by" reference to the sub-paradigm. Those form rules may also contain "divergent path" references as appropriate, as will be described below. Further, a reference to each inherited form rule is stored in the subparadigm as an optimization for the run-time morphological generation function and to aid in divergence checking.
In step 104, the processor 6 will then set an "ancestor" variable to be equal to the super-paradigm of the current paradigm, and the processor 6 will investigate whether the super-paradigm "shares" any form rules with a paradigm super to it. In step 106, the processor 6 determines whether the ancestor paradigm shares any form rules by looking for the set of shared form rules in the tree data structure. If, in step 106, the ancestor is not based on another paradigm, the processor 6, in step 108, will terminate the procedure and return to the step where the form rule inheritance procedure was called (e.g., step 48 in FIG. 2A). Otherwise, in step 110, the processor 6 will retrieve the ancestor's set of shared form rules and, in step 102A, screen out superseded form rules and perform the divergence check on the inherited form rules mentioned above, and described in detail below.
In step 112, the processor 6 continues to check back through the paradigm heirarchy, by determining if the ancestor paradigm has its own ancestor. Again, this is performed by checking for the occurrence of a "based-on" statement in the ancestor paradigm and retrieving the superparadigm. If the ancestor is based on another, in step 116 the processor 6 sets the ancestor marker to equal the reference in the based-on declaration and returns to step 106 to perform the form rule screen and divergence check for any form rules shared by the ancestor. If, in step 112, the ancestor paradigm is not based on another, the processing will terminate and the processor 6 will return to step 48 in FIG. 2A.
c. Form Rule inheritance Processing--Form Rule Screening and Divergence Check
In step 102 of FIG. 2C, the processor 6 invokes a process to screen out those form rules that have been superseded and further check the rules that have not been superseded for path divergence. That process is now described with reference to FIGS. 2D-E. In FIG. 2D, the processor 6 begins with the set of form rules declared in the super-paradigm and it begins, in step 120, a loop to screen out those form rules that are: 1) superseded by the "current" (sub) paradigm, and 2) check the form rules to be inherited for divergent paths.
If, in step 120, there are unchecked form rules, the processor 6 proceeds in step 124 to get a form rule from the tree data structure of the compiled rule set 20. In step 126, the processor 6 checks the form rule against the form rules in the current paradigm branch of the tree to determine whether or not it has been superseded. Again, a form rule is superseded when a form rule with an identical left-hand-side is declared in a subparadigm. If the form rule has been superseded, the processor 6, in step 126, disregards the form rule (as it will not be shared) and proceeds, in step 120, to the beginning of the loop to process another form rule from the set of form rules of the superparadigm. And if all the form rules have been processed, the processor 6 will return to step 102 in FIG. 2C.
Referring again to step 126 in FIG. 2D, if the form rule currently being examined has not been superseded, the processor 6 will, in step 127, invoke a procedure to perform a divergence check on the form rule. FIG. 2E, described below, depicts an exemplary process flow for the divergence check process of step 127.
When a form rule is inherited, the super-paradigm form rule is "shared" by the sub-paradigms that inherit the rule. This is accomplished by: 1) associating with each shared form rule a list of the paradigms that share it; and 2) placing a reference to the shared form rule in each of the subparadigms that have inherited it. (The latter is an optimization for the function of morphological generation and aids in the divergence check). For example, associated with a super-paradigm form rule (pres.sub.-- 1s) that is inherited by a number of sub-paradigms, might be the following information:
where the "shared by" entry comprises a set of references to the paradigms that share this form rule. Referring to FIG. 2E, in step 130, the processor 6 adds the current paradigm to the list of sharing paradigms of the current form rule of the super-paradigm.
Next in step 132, of FIG. 2E, the processor 6 retrieves the stem of the ancestor form rule, and, in step 134, determines whether the stem value is a reference to another form rule. If not, no further divergence checking needs to be performed, and the processor 6 will, in step 136, return to where the divergence check was invoked (i.e., step 127 in FIG. 2D).
Referring again to step 134, if the stem is a reference to another form rule, the processor 6 proceeds to step 138 to determine if that stem form rule has been superseded anywhere between the original paradigm that is inheriting form rules, and the current ancestor. This determination is made by searching the original paradigm, and each one of its ancestors back to the current ancestor, for a form rule with an identical left-hand-side. If the form rule was not found in step 138, there is no divergence. The processor 6 then returns to step 130 to continue following the chain of form rules, processing the stem of that stem of the form rule. If a superseding form rule was found in step 138, the processor 6 proceeds to step 140 to determine if the original form rule being checked is a surface form rule. If so, then a cycle check procedure must be invoked.
As stated above (with reference to step 58 in FIG. 2A), a cycle check is a procedure to check the reference chain of the form rule, searching the form rules referenced in the right-hand-sides of the form rules, until a LEX indicator is found. In the present invention, a form rule cycle check could be performed at one of two different times.
Referring to FIG. 2A, in step 58, the processor 6 invokes the cycle check on the set of surface form rules declared in the "current paradigm". If the current paradigm is based on another paradigm, then that set of surface form rules represents a set of (surface) form rules that are superseding those with the same left-hand-side in the super-paradigm. Also, if the current paradigm is based on another paradigm, then prior to step 58 (FIG. 2A), that paradigm (in step 48, FIG. 2A) will have inherited form rules from its super-paradigm. In the course of inheriting form rules in step 48 (FIG. 2A), a check for divergence is performed as in step 58A (FIG. 2E). If divergence is in fact detected, as in step 138 (FIG. 2E) described above, then a cycle check must be performed on the path with the superseding intermediate form rule (if the original form rule is a surface form rule). If the processor 6 did not perform this cycle check, then there could be the situation in which, for example, the paradigm verb.sub.-- er shares (i.e., inherits) pres.sub.-- 1s, which is declared in the super-paradigm verb.sub.-- root (APPENDIX III) as follows:
where BASE is declared as:
Assuming that BASE was also declared in verb.sub.-- er (i.e. the latter paradigm), as follows:
that would constitute a cycle, or an illegal path. Therefore, all divergent paths must also be checked for cycles. When the processor 6 invokes the cycle checking procedure in step 58 (FIG. 2A), however, this same path will not be checked, because only paths (chains) originating at the current paradigm will be checked, whereas the paths checked in step 58A (FIG. 2E) originated in the super-paradigm, but then "diverged" to a form rule declared in the subparadigm.
Referring again to FIG. 2E, if, in step 140, the original form rule is not a surface form rule, the processor 6 proceeds to step 146, where it will add to the node corresponding to that stem in the tree data structure, a reference to the superseding form rule and subparadigm. Once the divergence is made in step 148, the processor 6 in step 148, returns to step 127 in FIG. 2D.
Referring again to step 140 in FIG. 2E, if the original form rule was a surface form rule, then a cycle check must be made in step 58A. As described above, the cycle check is a procedure to check the chain of form rule references in the form rule stems to determine whether each form rule chain of references resolves to a LEX indicator. The process for cycle checking is described in detail below with reference to FIG. 2G. Referring again to step 58A in FIG. 2E, if the cycle check procedure identifies a cycle, the processor 6, in step 144, will generate an error and proceed, in step 148, to return to step 127 in FIG. 2D.
Otherwise, if no cycle is found, the processor 6 will continue to step 146 and add to the stem's list of divergents, a reference to the superseding form rule and subparadigm. Like the form rule "sharing" information described above, diverging form rule information is also stored in the tree data structure as nodes associated with the relevant form rule stem. Where a stem form rule is superseded, the reference to the superseding form rule, and its paradigm, associated with the superseded stem of the super-paradigm form rule, provides a branch that will enable the processor 6, in the run-time phase, to follow the correct path for any given form rule in any paradigm. This maximizes the amount of form rule sharing, while allowing for branching at any point in the form rule reference chain.
Referring again to step 146, FIG. 2E, once the reference to the divergent form rule is placed in the stem, the processor 6 in step 148, returns to step 127 in FIG. 2D.
d. Cycle check and Feature Propagation
Cycle check processing, as described above, checks the chain of form rule references starting at each surface form rule to insure that each form rule chain eventually resolves to a LEX indicator, which signals that the form string is stored in the lexicon. In FIG. 2A, the cycle check process is invoked in step 52 during the processing of the form rules for each paradigm. The cycle check procedure is also invoked during the divergence checking process in step 52 at FIG. 2E to insure that where the path of an inherited form rule diverges, the path of divergence also does not contain a cycle.
FIG. 2F provides an exemplary process flow of the cycle check procedure of step 52. In addition to cycle checking, this procedure will also propagate features for all form rules having a + operator in the present invention. Processing begins in step 150 with the processor 6 taking a surface form rule as input and beginning to process each component of its right-hand-side (RHS). In step 150, if there is a RHS component to check, the processor 6, in step 154, will get the next component and proceed to step 156. In step 156, the processor 6 determines whether the component references a form rule. If so, the processor 6 next determines in step 158 whether or not the form rule reference has already been seen in this cycle check. To make this determination, the processor 6 will scan the entries in a form rule list 159: Initially, for each sail to the cycle propagation process, the form list will be empty. If, in step 158 the stem form rule reference has not been "seen", the processor 6, in step 162, will mark the rule as being seen by adding the reference to the form rule list 159. Proceeding to step 58B, the processor 6 will now follow the chain of form rule references in step 58B, recursively calling this cycle check procedure, passing the stem form rule as the form rule argument. If the recursive call in step 58B to the cycle check procedure discovers a cycle, the processor 6, in step 160, will end the cycle check and also return an error to step 52 in either FIG. 2A or 2D (depending on where the call was made).
Referring again to step 58B, in FIG. 2G, if the recursive cycle check returns no cycle error (i.e., the cycle check is false), the processor 6 proceeds to step 166 to determine whether the form rule operator occurring in the RHS of the surface form is a plus (+). If the operator is a plus, then the processor 6 will perform the function of feature propagation for the surface form being checked.
As stated above, the feature propagation process propagates features (corresponding to the morpho-syntactic properties of a word form) from the intermediate forms of a form and associates them with the surface form. This process gives the user of the M language syntax an added convenience because he or she need specify the grammatical features only once rather than over and over for each surface form rule that references a given intermediate rule. In step 168, the processor 6 propagates the form features associated with the intermediate form rule, adding them into the feature specification of the surface form rule.
Once the features of the component are propagated in step 168, the processor 6 returns to the beginning of the cycle check loop and step 150 to process another RHS component. If, in step 150, there is another component to process, the processor 6, in step 154, will retrieve that component and proceed to step 156. If the component is not a reference to a form rule, the processor 6 next proceeds to step 170, where it determines whether the component is a LEX indicator. When the processor 6 finds a LEX indicator, it has hit the end of the form rule reference chain and here the processor 6 takes the features associated with the form rule where the LEX indicator was encountered and passes them back to the caller of the cycle check procedure. Where the cycle check procedure was recursively invoked from step 58B (FIG. 2F), the form features will bubble back up the chain, each form rule adding its features into the feature specification that is being passed back up the chain, and which eventually gets passed to the original caller, which adds them to the feature specification of the surface form rule. If, in step 170, the processor 6 determines that the component is a LEX indicator, the processor 6 will proceed to propagate features associated with form rule, but only if the form rule operator is a plus. In step 166, the operator is checked, and in step 168, the processor 6 propagates these features by passing the feature specification back up to the caller.
From step 168, the processor 6 returns to step 150 to process another RHS component of the form rule if any remain. If none remain, the processor 6 returns, in step 152, to the calling step, setting a success flag to true, and cycle check processing is complete.
e. Orthographic Rule Conflation
Referring again to step 54 in FIG. 2A, an exemplary process flow for the process of orthographic rule "conflation" is depicted in FIG. 2G. The present invention provides a method by which a user can specify a description of a language allowing specification of orthographic rules separate from the specification of the grammatical paradigm. And in the compilation process, the present invention automatically applies the orthographic rules across the paradigms to the appropriate form rules, without the user having to specify the application.
Referring to FIG. 2G, the processor 6 in step 200, begins a loop to process each orthographic rule declared in the user prepared declarative rules 16 (FIG. 1). If there are orthographic rules to process, the processor 6, in step 204, attempts to locate a set of form rules which are described by or match the characteristics of the orthographic rule. To find a match, the processor 6 will compare the left-hand-side of the orthographic rule to the right-hand-side of the form rule attempting to match the affix type (i.e., prefix or suffix) operator (i.e., plus [+] or minus [-]) and affix string. For example, in step 204, assume that an orthographic rule has been declared:
In step 204 the processor 6, may arrive at the following form rule:
where:
and
It is possible that the orthographic rule might apply to the form rule imp.sub.-- 2s, because the affix in the form rule is a suffix, the operator is a plus and the first letter in the form rule affix is a "t", thus matching the "t" affix string in the orthographic rule. The processor 6 will attempt to match all form rules (both surface and intermediate) to the orthographic rule.
After the attempt to match all the form rules with the orthographic rule in step 204, the processor 6 next begins a loop in step 206 to "conflate" each of the matching form rules. If the processor 6 determines there are additional rules to conflate, it proceeds to step 208 and retrieves the form rule. To conflate the form rule, the processor 6 will first create an intermediate form rule called an inner variant form rule or "inner variant", that has the same stem as the matching form rule, but which uses as its affix the context of the orthographic rule and the minus operator. In the example above, the inner Variant form rule Created would be:
where [dent] is the context of the orthographic rule.
In step 212, the processor 6 next proceeds to create an additional form rule variant called an "outer variant". In the exemplary embodiment of the present invention, only the outer variant is associated with the matching form rule, as the inner variant is already associated with the outer variant via the form rule reference chain. The outer variant has RHS components comprising: as a stem the inner variant form rule just created, and as its affix the right-hand-side result of the orthographic rule as unified with the affix of the form rule. The operator for the outer variant is the plus operator. In the example above, the outer variant form rule will be:
From step 212, the processor 6 proceeds to step 214 where it determines whether the orthographic rule contains a parameter. As described above, parameters are used with orthographic rules to limit their application to a subset of all lemmas having the appropriate characteristics to which the orthographic rule could apply. Where an orthographic rule has a parameter, it is associated with the outer variant so that the variant form rule will match only those words whose lexicon entries also provide for the parameter. In step 214, the processor 6 determines whether the orthographic rule has a parameter. If so, in step 216, the processor 6 provides for control of orthographic rule application, through the lexicon entry, by copying the parameter to the outer variant form rule. If the orthographic rule does not have a parameter, it will always apply, so long as the conditions of the context are met. In the example above, the orthographic rule has no parameter.
In either case of whether the orthographic rule does or does not have a parameter, the processor 6, in step 218, will undertake to ensure that the outer variant (second created) is identical in all other respects to the matching form rule from which it was derived. All the other data associated with the "source" or matching form rule is associated, in step 218, with the outer variant. This includes the feature specification, whether the form rule is surface or intermediate, whether it can be overridden, and the set of paradigms that share it. Only the outer variant gets associated with the matching form rule, as the inner variant is already chained to the outer variant as its stem.
After step 218, the processor 6 loops to step 206 to determine if there is another matching form rule. If so, the processor 6 will proceed to step 208 to get the form rule and conflate it as described. When all of the matching form rules have been conflated, the processor 6 returns to step 200 to determine whether there are any other orthographic rules to process, and if so, processes them accordingly. Otherwise the processor 6 returns to step 54 in FIG. 2A.
f. Building a discrimination Net.
Referring again to FIG. 2A, the processor 6 completes the compilation process by building the discrimination net, stored as a branch in the tree data structure of the compiled rule set 20, that will be used for the process of morphological recognition in the run-time phase. To construct the discrimination net, the processor 6 will access the compiled rule set 20 for form rule and other information. In the discrimination net, affix characters from all concatenating suffix form rules and their associated variant forms are given corresponding nodes which are formed into a network, so that the suffix of the surface string to be recognized can be most efficiently matched against all possible form rules. In the present invention, only concatenating suffix surface form rules are used to create the discrimination net, excluding all prefix surface form rules and all surface form rules where a suffix is stripped from the stem. These surface form rules are excluded from the indexing procedure, because the complexity they would add to the discrimination net far outweighs any advantage of their inclusion, given the rare occurrence of such surface form rules. The interconnections between the nodes for the elements of the suffix comprise a path from the last character in the suffix to a terminal node, which represents the stem of the form rule and contains information that enables a recognizer function to continue down the chain(s) of form rule references. The discrimination net is constructed by looping through all the surface form rules and building in a path for each concatenating suffix form rule. All of the other surface form rules, i.e., all prefix and stripping suffix form rules, are stored in a "non-netted" set, also maintained in the compiled rule set 20.
Generally, there are three types of suffixes to index in the discrimination net, because an affix can comprise either a string of literal characters, an affix variable, or an affix sequence. The affix sequence, as mentioned above, is a representation of an affix consisting of a sequence of character strings and or orthographic rule variables. An affix sequence occurs only in the variant form rules created during the orthographic rule conflation process (see step 54, FIG. 2A, and see FIG. 2G). The processor 6 must handle each of those possible affixes in building the discrimination net for concatenating suffix surface form rules.
When a character is encountered, the processor 6 will create a character node for the character (or re-use a previously existing character node, if one exists for the character), and then use it as part of a path to a terminal node. The present invention provides an initial array of character nodes, each node corresponding to a letter of the extended character set. A character node is a data structure comprising a character identifier and three sets of pointers to subsequent nodes. Character nodes can point to other character nodes, variable nodes and terminal nodes. A variable node handles the special case of the variable appearing in the affix sequence of a variant form rule created during orthographic rule conflation. As described above, a variable used in an orthographic rule is associated with a set comprising character strings over which the value of the variable may range. The affix of a variant form rule contains a sequence of strings and/or variables (e.g., such as the result sequence for the orthographic rule for geminating the consonant preceding a mute "e" in the French language [vowel gcons gcons "es"]). This sequence must also be mapped into the discrimination net. Generally, where a variable occurs in mapping the suffix of a variant form rule, the processor 6 creates a variable node. Like the character node, the variable node contains an identifier and three sets of pointers to subsequent character, variable and terminal nodes, respectively. However, the present invention provides that the variable node also contain a flag to indicate whether in a given path the given variable is bound, i.e., whether it has already been encountered in the path, and therefore must have the same value as when it was previously encountered.
Assuming the following orthographic rule:
there could be a surface variant form rule created having, as an affix, the affix sequence: [vowel gcons gcons "e"].
As the discrimination net is built, the character "e" is first indexed; then gcons, then gcons, and then vowel, followed by a terminal node. In the example, there are two gcons variables. As described above, the gcons variables are used to identify the same literal character for a given application. In the run-time morphological recognition phase, as characters are matched against the discrimination net, the value of the first gcons variable dictates what value the second gcons variable must be. And in this sense, the value of the second gcons variable must be identical to that which was "bound" to the first gcons variable. Generally, when the processor 6 creates a variable node, it checks a list of bound variables (i.e., a binding list) to determine whether this variable has been encountered already in creating the current suffix path. If so, the processor 6 will mark that variable node as bound, by setting a flag to true.
In the present invention, a form rule that has an affix variable as its suffix, also requires some special processing when indexing it into the discrimination net. As described above, an affix variable is used to represent a set of alternative affix strings. Generally, for each affix string in the set, the processor 6 will create a path to a terminal node.
The terminal node comprises a list of suffix surface form rules, having the affix that corresponds to the path in the discrimination net that leads to that node. Associated with each surface form rule reference in the terminal node is also a list references to the primary and divergent stem form rules that comprise the right-hand-side stem of the surface form rule. Further associated with each stem form rule are the set of paradigms comprising an intersection between the set of paradigms that share the surface form rule and the set of paradigms that share the stem form rule. As will be described below, that information in the terminal node provides information to enable the processor 6 during recognition to avoid taking incorrect divergent paths.
FIG. 2H depicts an exemplary process flow of the discrimination net building process referenced above in step 56 (FIG. 2A). Referring to FIG. 2H, the processor 6, in step 220, begins a loop to process each surface form rule in each paradigm of the user prepared declarative rules 16 (FIG. 1). If, in step 220, there are surface form rules to process, in step 224, the processor 6 will retrieve a form rule and proceed to step 226. The processor 6, in step 226, determines whether the form rule is a concatenating suffix form rule (i.e., it determines whether the right-hand-side of the form rule contains a suffix and a plus (+) operator). Only concatenating suffix surface form rules are used to create the discrimination net, excluding all prefix surface form rules and all surface form rules where a suffix is stripped from the stem. Referring back to step 226, if the form rule is not a concatenating suffix surface form rule, it, in step 228, is added to a separate non-netted set 23, and the processor 6 returns to the top of the loop at 220 to process another surface form rule. Although not included in the discrimination net, the surface form rules stored in the non-netted form rule set will also be used in run-time phase recognition processing, as will be described below.
Referring again to step 226, if the form rule is a concatenating suffix surface form rule, the processor 6, in step 230, will first determine whether the suffix is an affix variable. If so, the processor 6 proceeds to step 232 to retrieve the set of affix variable values from the compiled rule set 20. With that set of character strings, the processor 6 begins a loop to index the form rule, creating a separate path for each member of the affix variable set.
In step 234, the processor 6 determines whether there are any more affix variable set members to index. If so, in step 236, the processor 6 retrieves the next value and, in step 238, invokes a procedure to index the affix string into the discrimination network.
FIG. 21 depicts an exemplary process procedure for adding a character string into the discrimination network 23. Upon the receipt of the character string, the processor 6, in step 246, will reverse the characters of the suffix string and, in step 247, it will use the value of the first character to index into the initial array of the discrimination net (i.e., find the start node). A string pointer is used by the processor 6 as a placeholder in the reversed affix string. As described above, the initial array is a data structure comprising character nodes corresponding to each possible character in the extended character set. The string pointer, used to move through the suffix string, will be incremented; and the initial node reached is the "current" node.
In step 248, the indexing procedure ,continues with a loop to process the remaining characters of the suffix. In step 248, if the processor 6 determines that there are more string characters to process, it proceeds to step 250 to determine whether there is a path already established for the character from the initial indexing point. Multiple form rules may have the same suffix endings. Thus, as a discrimination net is constructed, the same suffix path may have already been established. The processor 6, in step 250, checks to see whether the current node leads to another character node that matches the next character in the suffix string. If such a node exists in step 250, the processor 6 proceeds to step 254 and follows the path to the next character node. In step 256, the string pointer is incremented, and the processor 6 returns to the beginning of the character processing loop at step 248.
Referring back to step 250, if a path for the current character does not exist, the processor 6 will proceed to step 252 and create a node path for this character. As stated above, a character node is a data structure containing a character identifier and 3 sets of pointers to other character nodes, variable nodes and terminal nodes, respectively. In step 252, the processor 6 will create a character node for the character, linking that new character node to the current node. After creating the path for the second character in step 252, the processor 6, in step 256, increments the string pointer and proceeds to the beginning of the affix element processing loop in step 248. If there are no more characters in the string to process, the processor 6, in step 258, then adds a terminal node to the network. As stated above, the terminal node comprises a list of concatenating suffix surface form rules whose affix corresponds to the path leading to the terminal node. Associated with each form rule reference in the terminal node are the stem form rules for the node and for each stem rule, the set of paradigm references comprising the intersection of the set of paradigms sharing that stem form rule and the set of paradigms sharing that stem form rule. This information allows the processor 6 in the recognition phase, to adhere to valid paths, without crossing over at points of divergence.
An exemplary process flow for the process in step 258 of creating a terminal node and placing in it the appropriate path tracking information is depicted in FIG. 2J. In step 259, the processor 6 creates a new node link to the current node using a terminal node pointer from the current node. In step 260, the processor 6 next retrieves for the form rule the set of paradigm references that share it. This information is associated with the node for the form rule. In step 267, the processor 6 adds to the terminal node the form rule whose path is being followed and a list of its stem form rules. This information also is associated with the node for the form rule found in the compiled rule set 20. The list comprises the "prime" stem form rule plus any divergent stem form rules associated with the form rule in the compiled rule set 20. If, in step 268, there are divergent stem form rules, the processor 6, in step 269, references the paradigm "sharing" information associated with that divergent stem form rule (i.e., the sharing information in the compiled rule set 20), and, in step 270, returns the intersection of the set of paradigms that share the form rule and the set of paradigms that share the stem form rule. The processor 6 then returns to step 268 to process another divergent stem form rule. As described above, when all of the divergent stem form rules are processed, the processor 6 returns to step 271 in FIG. 21.
Referring again to FIG. 21, the processor 6, in step 257, then returns to step 238 in FIG. 2H. Referring again to step 238 in FIG. 2H, the processor 6 returns to step 234 to process the remaining members of the affix variable set as described above. When all the members have been indexed, the processor 6 proceeds to step 242 to begin processing the variant form rules of the current form rule as will be described below.
Referring again to step 230 in FIG. 2H, if the affix comprises a character string, the processor 6 will proceed to step 238A to invoke the procedure to add that suffix string to the discrimination net as described above with reference to FIGS. 2I and 2J.
With the discrimination net processing of the form rule affix complete, the processor 6, in step 242, will access the information data structure to determine whether the form rule has associated variants to add into the net. If there are no variants, in step 242, the processor 6 will return to the beginning of the discrimination net construction loop at step 220 to begin processing another surface form. However, if the current surface form rule has associated form rule variants, the processor 6, in step 244, will invoke a procedure to add the variant form rules into the discrimination net, which is described in detail with reference to FIGS. 2K and L. Referring to FIG. 2K, the processor 6 begins loop a to add each variant associated with the form rule into the discrimination net. In step 275, the processor 6 determines whether there are additional variant form rules to process. If so, in step 276, the processor 6 gets the variant form rule. Because the variant form rule results from the orthographic rule conflation process (see step 212, FIG. 2G), the variant's affix will always be an affix sequence (i.e., a sequence of character strings and/or variables), the last element of which will be a string of one or more characters. In step 277, the processor 6 gets the last character of the string and indexes it into the discrimination net in a process as described above. Then, in step 278, the processor 6 invokes a procedure to add the remaining string into the net, which is described in detail referring to FIG. 2L.
Referring to FIG. 2L, the processing of the affix sequence character string is similar to the process described above, with reference to FIG. 2I; however, here the string will not necessarily lead directly to a terminal node. Referring to FIG. 2L, the processor, in step 291, begins a loop to process the remaining characters of the string. In step 291, if the processor 6 determines that there are more string characters to process, the processor 6 proceeds to step 293 to determine whether there is a path already established for the character from the initial indexing point. The processor 6, in step 293, checks for additional character paths by checking any character nodes that are connected to the current node by a character pointer. If the current character matches a linked character node, the processor 6 proceeds to step 295 and follows the path to the next character node. In step 296, the string pointer is incremented, and the processor 6 returns to the beginning of the character processing loop at step 291.
Referring back to step 293, if a path for the current character does not exist, the processor 6 will proceed to step 294 and create a node for this character. In step 294, the processor 6 creates a character node for the character, and links that new character node to the current node. After creating the path for the second character in step 294, the processor 6, in step 296, increments the string pointer and proceeds to the beginning of the affix element string processing loop in step 290. When all the characters of the string have been added, the processor 6, in step 292, returns to step 278 in FIG. 2K.
Referring again to FIG. 2K, once the string representing the last element of the affix sequence has been added to the discrimination net, the processor 6, in step 279, begins a loop to process the remaining elements of the affix sequence in a right-to-left order. The remaining elements can be either character strings or variables.
In step 279, the processor 6 determines whether there are any additional affix sequence elements to process. If so, the processor 6 proceeds, in step 280, to get the next element, proceeding from right to left, incrementing an element pointer. In step 281, the processor 6 determines whether the next element is a string, if so, the processor 6 proceeds to step 278 or invokes the procedure to add the string element into the net as described above with reference to FIG. 2L. If, in step 281, the next element is not a string, the processor 6 proceeds to step 282 and begins a procedure to add this variable.
In step 282, the processor 6 will search the set of variable node pointers contained in the current node to determine whether a path already exists from the current node to a variable node that is equivalent to the current variable. If so, in step 283, the processor will follow the pointer to that variable node and, in step 284, increment the element pointer. The processor 6 then returns to the top of the element processing loop at step 279 for further processing.
Referring again to step 282, if no variable pointer in the current node references a variable node for the current variable, the processor 6 in step 284 will create a node for the variable and link it to the current node. In step 285, the processor 6 next determines whether the variable has been used before in the same path by checking a binding list. The binding list contains a list of variable names and their "bound" value. If the currently developing path has passed through a variable node, having the same identifier as determined in step 285, the processor 6, in step 286, will set a flag in the variable node to indicate that the variable is already bound to a value. The processor 6 increments the string pointer 289, to get the next element to process and returns to the top of the element processing list at step 279.
Referring again to step 285, if the variable has not yet been encountered along the current discrimination net path, the processor 6 will then proceed to step 287 and add the variable and its location to the binding list and set the bound variable flag within the variable node to false. In step 289, the processor 6 increments the string pointer to locate the next element in the affix string being indexed and returns to step 279 to process another element if any remain.
If, in step 279, there are no more elements to process, the processor 6 has made a path of the elements of the affix sequence. The processor 6, in step 236A, adds a terminal node to the discrimination net, as described above with reference to FIG. 2J. Then, the processor 6 returns to step 275. Once all the affix sequences for the variant form rules have been processed, the processor 6, in step 274, returns to step 244 in FIG. 2H. Referring again to FIG. 2H, the processor 6 returns next to step 220. Once all surface form rules have been processed, the processor 6, in step 222, returns to step 56 FIG. 2A. Referring to step 58 in FIG. 2A, the compiled rule set data structure 20, including the discrimination net and the non-netted set, are saved in the secondary storage for use in the run-time phase.
Referring to FIG. 2A, once the discrimination net and non-netted rule set have been created, the resulting data structure created by the compilation process gets saved to the secondary storage 10 and the compilation process is complete.
SURFACE FORM RECOGNITION
Referring again to FIG. 1, the processor 6 will perform database retrieval functions, using the statements and data structures of the database retrieval module 28, when the user 14 inputs queries through the input device 4 for text retrieval from the indexed database files 29. One query might include a surface form of a word and the query would require text references to all forms of the word. To retrieve the text, the processor 6 will invoke the morphological recognizer module 26 to take the surface form of the word and return a set of all possible forms that might produce the given surface string with their associated lemmas. Using each lemma form retrieved, the text retrieval system 28 can then search its database index files 29 for text file locations containing that particular form.
Given the string of a surface form and a compiled rule set, the recognizer module 26 first tries to match the string from right to left by running it through the discrimination net in the compiled rule set 20. The discrimination net is used to strip off a suffix, and then point to the set of stem rules that might apply for the path just taken. The final node in each path in the net also contains information regarding the paradigms that share each of the stem rules and the set of form rules whose path was just taken. Each of the stem form rules for which the intersection of the paradigms that share the form rule and those whose path was just taken is not NULL is applied to the remaining string (i.e., the affix having been stripped, next the set of stem form rules is obtained, and processing continues in this way until the stem form rule has a RHS value of LEX, meaning the string for that form is stored in the lexicon). Once all applicable paths of the discrimination net have been pursued, the set of surface form rules in which the operator is a minus or the affix is prefix are applied against the surface form string. (This is because the discrimination net comprises only surface form rules having a suffix and the plus operator). These two processes (i.e. running the surface form through the discrimination net and applying the other surface form rules to the surface form) produce a set of possible results. Each entry in the possible result set comprises the surface form that could have produced the surface form string, its paradigm, the form and string to which the surface form rule resolved, i.e. that string stored in the lexicon), and any orthographic parameters or affix variable feature values associated with the surface form. Each string in this intermediate result set is looked up in the lexicon. If the form, paradigm and any orthographic parameter and/or affix variable feature values all match, then the entry is maintained in a final result set.
APPENDIX V lists an exemplary algorithm for the morphological recognizer module 26 of the present invention. The appendix represents a high-level overview of the process, while FIGS. 3A-3I and the description to follow provide a detailed description of an exemplary embodiment. Referring to FIG. 3A, the recognition procedure begins in step 300, where the recognition module receives a surface string to recognize. The value of the last character of the surface string is used as an index into the discrimination net. From that initial node, all possible nodes are explored in a recursive process that will return a set of intermediate results to be looked up in the lexicon 22 (FIG. 1)., To perform the recursive path search procedure, in step 302, the processor 6 makes a copy of a binding list (used to keep track of bound variables encountered in the affixes of the form rule variants) and, in step 304, the processor 6 invokes the recursive procedure, which is described in detail with reference to FIGS. 3B-3I. The next step is to attempt to match the surface string against the set of surface form rules in the non-netted rule set (i.e. those surface form rules that were not indexed into the discrimination net). As stated above, those form rules where the affix has a prefix or the operator is a minus, were not incorporated into the net, but rather their forms were stored in a non-netted set. In step 306, the non-netted set is checked. If there are form rules to be processed, the processor 6 proceeds to step 310 to get the next form rule. The processor 6, next invokes a recursive process to apply the form rule to the string. This recursive procedure (described in detail below with reference to FIG. 3D) in step 314 follows all references of a particular chain, until a form rule is encountered the right-hand-side value of which is LEX. The loop will return to step 306 when the processor 6 determines that there are no longer any form rules to apply to the string.
If, in step 306, there are no more, if any, unseen suffix or prefix form rules to process, the processor 6, in step 308, next attempts to look up each string in the result set 305 in the lexicon 22, in a process described more fully below in FIG. 3J. If the form, paradigm and any orthographic parameters or affix variable feature values from the lexicon entry for the word do not match the information in the result set, that entry is culled from the result set. In step 316 the processor 6 returns the final result set 305.
The process flow for discrimination net processing (depicted in step 304 in FIG. 3A) is depicted in detail in the exemplary process flow illustrated in FIG. 3B. Generally, discrimination net processing involves some special techniques to handle affix sequences, which occur in the form rule variants (created during orthographic rule conflation), and to handle form rule divergence, i.e, the branching of the form rule chains due to the superseding of intermediate form rules by subparadigms. Each node in the discrimination net must contain information about at least three possible "next" processing points: character nodes, variable nodes and terminal nodes. In addition, variable nodes must contain information indicating whether the given variable is bound. In step 304 (FIG. 3A), after the last character of the surface form has been matched to an initial node in the discrimination net, the processor 6 proceeds, in step 320, to determine if the next character in the surface form string matches any of the next character nodes to which the current node leads. If there is no match, the processor 6 proceeds to step 330 to see if there are any paths to variable nodes to which the current node leads. As mentioned above, a discrimination net node contains references to other character nodes, variable nodes and terminal nodes. In step 330, the processor 6 determines whether there are any variable nodes to which the current node leads have not yet been processed. If so, in step 332, the processor 6 next attempts to follow the next variable path connected to the node.
In step 334, the processor 6 determines whether the variable is bound by checking the bound flag on its discrimination net variable node. If, in step 334, the variable is not bound (i.e., that variable is being encountered in a given path for the first time), then, in step 338, the processor 6 will add the variable name and the character (from the string being recognized) to a binding list. Processing continues in step 340 where, the processor 6 retrieves the next character from the surface form string, copies the binding list and, in step 304B, recursively calls the discrimination net process of FIG. 3B.
Returning to step 334, if the variable already appears on the binding list, the processor 6 next checks, in step 336, to make sure that the character matches the value to which the variable has been bound. If the character does not match in step 336, that path is no longer followed and processing returns to step 330, If, however, in step 336, the character and the value do match, the processor 6 will repeat step 340 to get the next character from the string, copy the binding list and recursively call, in step 304B, the discrimination net process of FIG. 3B. The processing of variable nodes will continue until all paths to variables have been explored from the current node.
In step 342, the processor 6 determines whether there are any terminal nodes to which the current node leads. If so, in step 344, the processor 6 will access the information stored in the next terminal node in the discrimination net. For a given terminal node, the processor 6, in step 346, determines whether there are any stem form rules that have not yet been applied. If there are stem form rules, the processor 6, in step 348, retrieves the form rule that is referenced in the stem, copies the binding list, and, in step 350, invokes a procedure to apply that stem rule to the remaining surface form string. This form rule application process involves steps of recursively stripping an affix from or concatenating it to the surface form string and then locating a subsequent remaining stem to apply the same technique, until a LEX indicator is found for a stem.
FIGS. 3C through 3I depict process flows for an exemplary form rule application process of step 350 in FIG. 3B. Referring to FIG. 3C, that figure shows the procedure of step 350 FIG. 3B for stem form rule application. Checking a stem form rule is part of a recursive process that involves checking to see whether the stem is stored in the lexicon (i.e., the stem value is LEX), which signals the end of the recursion, or if not, then applying the (stem) form rule, which is the other part of the recursive process. In addition, because shared (inherited) form rules sometimes entail divergence (as a result of intermediate form rules within the chain being superseded by some of the paradigms that are sharing the form rule), some extra checking needs to be done. Specifically, the stem form must be treated as a set of stem form rules. Each stem form rule must be checked for the set of paradigms that share it. Only those stem form rules that are shared by paradigms whose path is being followed are processed. This insures that paths aren't switched in "mid-stream". For example, a surface form listed in a terminal node of the discrimination net is shared by paradigms 2, 3 and 5. The terminal node lists two branches (i.e., two alternative stem form rules): the first path is shared by paradigms 2 and 3, while the second is shared by paradigm 5. Following the latter branch, the processor 6 encounters two more branches: the first is shared by paradigm 5, the second by paradigm 6. If the processor 6 simply followed all paths without checking the paradigms, then it could end up following the second branch, which would represent an illegal path (e.g., starting out with paths 2, 3 and 5, then following down the path 5, and then ending up on path 6).
Referring to FIG. 3C, processing begins in step 360, where the processor 6 determines whether there is only one form rule in the set of form rules referenced by the stem, meaning that there are no divergent paths. If in step 360, there is only the one (stem) form rule, then the processor 6 determines, in step 362, whether the stem form rule has as a right-hand-side value of LEX. If so, the recursive process bottoms out. In step 364, the processor 6 adds the remaining characters of the surface form string along with the form rule in question to the result set 305 (FIG. 3A), and, in step 366, the processor 6 returns to step 350 in FIG. 3B. Referring again to step 362 in FIG. 3C, if the stem form rule does not contain the LEX reference, then the processor 6 attempts, in step 314A, to apply the form rule to the remainder of the surface form string. The form rule application procedure of step 314A is the recursive process of stripping or concatenating an affix and attempting to find a stem as described above. The process flow for this procedure is described more fully below, with reference to FIG. 4D.
Referring again to step 360 in FIG. 3C, if there is more than one form rule in the form rule set representing the stem of a form, each path is followed where the intersection of the paradigms sharing the stem form rule and those whose path(s) is being followed is not null. That process begins in step 370. If, in step 370, there are form rules that have not been applied, the processor 6 gets this intersection, and, if the intersection is not empty in step 372, the processor 6 will apply the form rule. In step 374, the processor 6 copies the binding list and, in step 368, the processor 6 applies the form rule to the remaining characters of the surface form string, in a process that will be described below. The processor 6 then loops again to step 370 until all of the form rules in the stem form rule set are processed. After that, the processor 6 proceeds to step 366 returning the recursively collected results in the result set 305 (FIG. 3A).
The form rule application process referenced above in steps 314A and B in FIG. 3C is now described with reference to the exemplary process flow in FIG. 3D. The process of applying a single form rule to the remainder of the surface form string involves first checking to determine whether the form rule can be overridden by a string in the lexicon 22 (FIG. 1). In step 380, the processor 6 makes that check by searching for the lexical-override indicator in the form rule. If found, the string and the form rule are added, in step 382, to the result set (as if the form rule had a right-hand-side LEX value). The processor 6, however, will continue to process the form rule in case the lexicon entry for the surface form string does not provide a lexical override.
In step 384, the processor 6 determines whether the right-hand-side of the form rule contains an affix. If so, the processor 6 invokes a procedure to perform the inverse operation dictated by the form rule: either strip the affix if the affix operator is a plus (+), or concatenate the affix to the string if the affix is a minus (-). The affix application procedure of step 386 must differentiate between affixes that comprise a string, an affix sequence, or an affix variable (affix.sub.-- var) reference as each entails its own processing. Because application of an affix variable may produce multiple strings, the affix application procedure of 386 returns a set of strings. The procedure of step 386 is described in detail below with reference to FIGS. 3E-3I. Referring to step 388, if the affix procedure did, in step 386, apply the affix of the form rule to the surface form string, the processor 6 will proceed to step 385. If in step 388, the processor 6 finds that the affix procedure of step 386 did not apply the affix, then the procedure in step 390 would return to step 314 with any forms it had in the result set 305.
Referring again to step 384 in FIG. 3D, if the form rule contains no affix on the right-hand-side, the processor 6, in step 385, determines whether any more strings remain to process. If not, the processor 6, in step 387, will return the results of the form rule application. If, in step 385, there are remaining strings, in step 350A, the processor 6 calls the procedure to apply the stem form rules. This call, in step 350A, represents a recursive call back to the stem form rule application procedure illustrated in FIG. 3C, applied this time to the stem of the form rule in question, thus following the chain of form rules provided in the present invention.
After recursively applying the stem of the form rule, in step 350A, the next step of form rule application is to apply the form rule variants, if any exist, to the remaining surface string(s). As described above, a form rule variant is a form rule created in the orthographic rule conflation process (step 54, FIG. 2A). The processor 6, in step 392, determines whether there are any form rule variants that have not been applied. If there is a form rule variant that has not been applied, the processor 6, in step 394, gets the form rule variant, copies the binding list and, in step 314C, makes a recursive call to the apply form rule procedure illustrated in this figure, FIG. 3D, passing in the variant form rule and the string. After the particular form rule variant has been applied, the processor 6 loops back to step 392 to determine if all form rule variants have been applied. If so, the processor 6 returns to step 385 to process the remaining surface form strings. Once all strings have been processed, the processor 6, in step 387, will return the result set 305 to step 314(A or B) in FIG. 3C and continue appropriate processing.
Step 386 in FIG. 8D refers to the precess of affix application; that process is now described below and is illustrated in FIGS. 3E-3I. Referring now to FIG. 3E, the process begins by determining the data type of the affix and processing it accordingly. As described above, an affix may be a character string, a reference to an affix variable or an affix sequence (i.e. a sequence of character strings and/or variables, which is used in form rule variants). Each type of affix must be handled differently. If the affix is a string, then the ending is either stripped (if possible) from the surface string if the operator is a plus, or it is concatenated if the operator is a minus. If the affix is a reference to an affix variable, then the processor 6 tries to apply the affix variable FIG. 3F. If the affix is an affix sequence, then the processor 6 tries to apply the affix sequence. As mentioned above, the affix application procedure returns a set of strings, because if the affix comprises an affix variable, a set of strings may be produced.
The processor 6, in step 406, determines whether the affix is a string of characters. If so, in step 408, the processor 6 will check to determine whether the form rule operator is a plus (+) or a minus (-). If the operator is a minus (-), the processor 6 will concatenate the affix string to the remainder of the surface form string, and in step 412, the processor 6 will return the string to step 386 in FIG. 3D, because the affix has been successfully applied to the string.
Returning to step 408, if the operator is a plus (+), the processor 6, in step 414, next determines whether the affix string matches the substring at the appropriate end of the remaining surface string; if so, it will be stripped from the latter. If the matching and stripping procedure of step 414 is successful, the processor 6, in step 412, returns the shortened character string. If the matching and stripping procedure of step 414 is unsuccessful, in step 416, the processor 6 returns the empty set.
Referring again to step 406, if the processor 6 determines that the affix is not a string, it will next determine whether the affix contains a reference to an affix variable (i.e., affix.sub.-- var). As described above, an affix variable is a declaration which identifies a variable name with a set of possible affix strings. In applying an affix to a string where the affix comprises a reference to an affix variable, a procedure must be invoked to apply each affix string belonging to the affix variable set to the remaining surface string. The procedure invoked by the processor 6, in step 420, is described in detail below with reference to FIG. 3F. Referring again to FIG. 3E, in step 422, the processor 6 will return the set of remaining surface form strings from the affix variable application procedure.
Referring to step 418, if the affix is not an affix variable reference, the processor 6 next determines whether the affix is an affix sequence (i.e. affix.sub.-- seq). As described above, an affix sequence is a sequence of character strings and or variables that represent the affix string. If, in step 424, the affix data type is an affix sequence, the processor 6, in step 426, invokes a procedure to apply the affix sequence to the remaining surface string. That procedure is described in detail below with reference to FIGS. 3G-3I. Referring again to FIG. 3E, in step 428 the processor 6 will return the remaining surface form string after the application of the affix sequence in step 426.
Referring again to step 424, if the processor 6 determines that the affix is not an affix sequence, then the processor 6 must, in step 430, generate an error, because the affix has no legal data type according to the syntax of the M language 12 (FIG. 1). In that case, the processor 6 returns the character string and returns to step 386 in FIG. 3D.
In the affix application process illustrated in FIG. 3E, the processor, in step 420, invokes a process to apply the set of affix strings identified by the affix variable (affix.sub.-- var) reference. FIG. 3F depicts an exemplary process flow for that procedure. Referring to FIG. 3F, the processor 6 begins a loop at step 452 to process each of the affix character strings identified by the affix variable. The processor 6 gets an affix character string, in step 456, and processes it in one of two ways. If, in step 458, the processor 6 determines that the form rule operator is a minus (-), in step 460, it creates a new string by copying the surface string and concatenating the affix string to the surface string copy, which is then added to the result set. Then, the processor 6 returns to step 452 and the beginning of the loop. Because in this case all affix variable set members have been processed, the processor 6 jumps to step 454, returns the entire set of concatenated strings to step 420 in FIG. 3E. That result, of course, is returned to step 386 in FIG. 3D, where, in step 350A, the processor 6 invokes the application of the stem form rule procedure, applying the same stem form rule to each of the different strings contained in the result set. In applying the variant form rules in steps 392, 394 and 314C, the processor 6 would additionally attempt to apply the variant against each newly concatenated string.
Referring again to step 458 in FIG. 3F, the processor 6 determines that the form rule operator is a plus (+) instead of a minus (-). In step 462, the processor 6 will attempt to match the characters of the affix variable character string against corresponding characters at the appropriate end of the surface form string. If there is a match found in step 462, the processor 6 will copy the string, minus the matched affix, add the new string to the result set, and return to the beginning of the loop in step 452 to process the remaining affix character strings in the affix variable set. If no match is found in step 462 the processor 6 again returns to step 452. When all of the affix variable character strings have been processed, the processor 6 will return the set of strings to step 420 in FIG. 3E.
Referring again to step 426 in FIG. 3E, the processor 6 invokes a procedure to apply an affix sequence to the surface string. The process flow for an exemplary affix sequence application process is illustrated in FIGS. 3G-I. Generally, an affix sequence (affix.sub.-- seq) is a sequence of character strings and/or (orthographic rule) variables. Affix sequences require special processing because each element of the affix sequence must be stored with its type (i.e., string, finite string or variable), and variables need special checking. An affix sequence application proceeds in a slightly different way depending on whether the affix is a prefix or suffix (i.e., matching left-to-right vs. right-to-left) or whether the operator is a plus or minus (i.e., stripping vs. appending). The difference between a string and a finite string is that a finite string must be an exact match with the affix, whereas the string may match only a portion of the affix (i.e., that part that is adjacent to the stem). This supports the use of more general orthographic rules, say, specifying a single rule for the concatenation of any suffix that starts with an "e" as opposed to stating three separate rules for the suffixes "e", "es" and "em".
Referring to FIG. 3G processing of the affix sequence begins at step 470, where the processor 6 determines whether the form rule operator is a plus (+) or a minus (-). If the operator is a minus (-), the processor 6 begins a loop, in step 472, to process all of the elements of the affix sequence. In step 476, the processor gets an affix sequence element. If, in step 478, the processor 6 determines that the element is a string of characters, the processor 6 appends that string to the surface form string. Then, the processor 6 returns to the start of the loop in step 472. If, in step 478, the element is not a string, then the element must be an orthographic rule variable. In step 482, the processor 6 will get the value for which the variable is bound (as shown on the binding list), and, in step 480, the processor 6 appends that value to the surface form string. The processor 6 again returns to the start of the loop at step 472. If all elements in the affix sequence have been processed, the processor 6 will, in step 474, return to step 426 in FIG. 3E with the processed surface string.
Referring again to step 470 in FIG. 3G, if the operator is a plus (+) rather than a minus (-), the processor 6, in step 484, will determine next whether the affix is a prefix or a suffix and process the affix sequence for each in a slightly different way. If the affix is a prefix, the processor 6, in step 486, will attempt to strip off the element of the affix sequence matching left-to-right the corresponding characters of the remaining surface string. The process of step 486 for left-to-right stripping is described in detail below with reference to FIGS. 3H and I. Referring again to step 484 in FIG. 3G, if the affix is a suffix, then, in step 488, the processor 6, will attempt to strip off the corresponding characters from the remaining surface string right-to-left, in a process that is also described below. Each of the procedures in steps 486 and 488 will return from the attempt the resulting surface form string. In step 490, the processor 6 will evaluate the results of these procedures. If the affix sequence was stripped, the processor 6, in step 492, will return the stripped surface form string to step 426 in FIG. 3E. Otherwise, in step 494, the processor 6 will return to step 426 in FIG. 3E the empty set.
FIGS. 3H and I depict an exemplary process flow for the left-to-right matching of the affix sequence in step 486 (FIG. 3G). This process begins in step 500 with a loop to process each element of the affix sequence. In step 502, the processor 6 gets an element of the affix sequence and, in step 504, determines whether the element is a string of characters. If so, the processor 6, in step 506, will attempt to match left-to-right the characters of the affix sequence string to corresponding characters in the surface string affix. If, in step 506, there is not a match, the processor 6 will immediately exit the loop in step 508, returning a null pointer. If there is a match in step 506, the processor 6 will return to the beginning of the loop at step 500 to process the remaining elements of the affix sequence.
Referring again to step 504, if the affix sequence element is not a string, then the processor 6, in step 510, determines whether the element comprises a finite string. In the M language syntax, a finite string comprises a string of characters concatenated with an end of word indicator. In this case the processor 6, at step 512, attempts to exactly match, left-to-right, the finite string (minus the end-of-word indicator) against the remaining surface form string. If the two strings do not match exactly, the processor 6, in step 514, immediately exits the loop, returning a null pointer to step 486 in FIG. 3G. If the strings do match exactly in step 512, the processor 6, loops to the beginning step 500 of the loop and processes any additional elements.
Referring again to step 510, if the affix sequence element is not a finite string type element, then the only other remaining type the affix sequence element can be is an affix sequence variable. In that case, the processor 6, in step 516, invokes a process to match the affix sequence variable. These variables require special processing depending on whether they are bound or unbound variables and depending on whether they are declared as character or string variables. The process of affix sequence variable matching is described in detail below with reference to FIG. 3I.
Referring again to step 516 in FIG. 3H, after the results of the matching process are returned, in step 518, the processor 6 determines whether the affix variable matched the corresponding character(s) in the surface string. If not, loop processing is terminated in step 520, and the null pointer is returned to step 486 in FIG. 4G. If there was a match in step 518, the processor 6 returns to the beginning of the loop in step 500. If the processor 6 determines that there are no more affix variable elements to process, the processor 6 will return the remaining surface string to step 486 in FIG. 3G.
The procedure for affix sequence matching of step 486 illustrated by the steps in FIG. 3H is identical to the procedure for matching affix sequences right-to-left by the process mentioned in step 488, except that the checking is performed in reverse, right-to-left so that the processor 6 checks for substrings at the end of the surface form string rather than at the beginning.
FIG. 3I depicts an exemplary process flow for an affix sequence variable matching procedure that was referenced in step 516 in FIG. 3H. As mentioned above, affix sequence variables require special checking/processing depending on whether they are bound or unbound and depending on whether they take character or string values. In the procedure described below, the binding list is first checked to see whether the given variable is already bound. If not, then a check is made to determine whether the variable is of a type that assumes character or string values. If the former, and if the next character in the surface string is a valid value for the affix variable, then the pair is added to the binding list and the result is returned. If the variable accepts string values, then the procedure must try and match all possible values to which the variable may be bound against the surface string, saving the result of the longest string match, if any. If the variable is already bound, then the processor 6 gets the character value from the binding list and sees if it matches and returns the result.
Referring to FIG. 3I, processing begins in step 530, with a determination of whether the affix sequence variable referenced is on the binding list for the given surface string. If so, the processor 6, in step 532, next attempts to strip the bound character value (found in the binding list corresponding to the variable entry) from the surface string. If there is a match, and the character is stripped from the surface string in step 532, the processor 6, in step 534, will return the stripped string to step 516 in FIG. 3H. Otherwise, in step 536, the processor 6 will return a null pointer.
Referring again to step 530, if the affix sequence variable does not appear on the binding list, the processor 6 next determines whether the set of values over which the affix sequence variable may range is a set of character strings. If so, the processor 6, in step 540, begins a loop to check the set of character strings against corresponding characters in the surface string.
In step 542, the processor 6 determines whether all the strings in the set have been processed, and, if not, retrieves, in step 552, the next string in the set. In step 554, the processor 6 attempts to match the characters of the variable set member string against corresponding characters from the surface string. If there is a match in step 554, the processor 6 does not yet strip the string, but instead (in step 556) determines whether the length of the variable set member is greater than the length of the longest member matched so far. If, in step 556, the length is the longest, the processor 6, in step 558, saves the set member and its length. The processor 6 then returns to the beginning of the loop at step 542 to determine whether there are any more members in the variable set for comparison. Additionally, if, in step 554, the member did not match corresponding characters of the surface form or if, in step 556, the length of the set member was not longer than the longest matched string, then the processor 6 would return to the beginning of the loop without storing the member or its length.
Referring again to step 542, if all of the members of the affix sequence variable set have been checked, the loop is completed. If, in step 544, it is determined that there was a match during the member check in loop, the processor 6, in step 548, will strip from the surface form string characters corresponding to the longest matched member string and in step 550 return to step 516 in FIG. 3H the stripped surface form string. If, in step 544, the processor 6 determines that no member string was matched, a null pointer will be returned in step 546.
Referring again to step 538, if the processor 6 determines that the set of values over which the affix sequence variable ranges is not a set of strings, processor 6 next performs processing, in step 560, with the set of characters that are referenced by the affix sequence variable. At this point, the affix sequence variable can only be a variable which assumes the value of an individual character. In step 560, the processor 6 attempts to match one character from the set of possible values against the appropriate character in the surface string. If there is a match, the processor 6, in step 562, will return to step 516 in FIG. 3H the surface string with the character stripped and. Otherwise, in step 564, the processor 6 will return a null pointer.
Referring again to FIG. 3A, the processing of the procedures described above and illustrated in FIGS. 3B-I produces a set of strings and corresponding form rules (containing LEX references) in the result set 305 along with the surface form rule that may have produced the surface string and the paradigm(s) that share both form rules. In step 308, the processor 6 takes a string from the result set 305 and attempts to locate a corresponding entry in the lexicon 22. If such a corresponding entry is found, the processor 6 will then match the form rule from the result set, the corresponding paradigm and any other feature constraints, i.e., orthographic parameters and/or an affix variable feature, against the lemma entry in the lexicon 22. Where the information does not match in step 308, the processor 6 will cull that entry from the data set. Those entries that remain in the result set are returned to the database retrieval system 28 (FIG. 1) as a final result set 318 (FIG. 3A) and recognition processing is complete.
SURFACE FORM GENERATION
Referring again to FIG. 1, the present invention presents a morphological text analysis system that is used in an exemplary embodiment in conjunction with a text retrieval system. In addition to the morphological recognizer module 26, the present invention also includes the morphological generator module 24. At run-time, the text retrieval system may access the morphological generator module 24 to, for example, identify all articles that contain some inflected form of a lemma. In the example of FIG. 1, the text retrieval module 28 would pass, using the processor 6, to the morphological generator module 24, a lexical entry and the one or more desired forms, and identifiers of the one or more forms desired. The morphological generator module 24 outputs one or more strings (surface forms) which can be used by the text retrieval module 28 as keys to locate articles containing those strings.
APPENDIX V lists an exemplary algorithm of the morphological generation 24 of the present invention, which provides a general overview of the generation process. A detailed embodiment is presented by the exemplary process flow for the morphological generator module 24 is depicted in FIGS. 4A-4G. Briefly outlined, the process of generating the surface string for a given form rule is a recursive process in which the set of stem strings is generated and then the affix is applied. During the process, the processor 6 will go down through the chain of form references until it finds a form that is stored in the lexicon 22 (FIG. 1), then pop back up and apply the affix at each intermediate form rule in the chain. If the form rule has variants, the processor 6 first tries to generate surface strings from the variants. If that fails, it uses the (matching) form rule. Given the recursive nature of the process and the fact the an intermediate form rule may be used in multiple paths, a list of form rules and the strings they generate is maintained as an optimization to avoid the repeated generation of the same form strings. This list is initialized with the forms and strings that are stored in the lexicon 22.
Referring to FIG. 4A a call to the morphological generator module 24 is processed as follows. In step 600, the processor 6 determines whether all the strings for the form rule have already been processed. Initially, all the strings for all form rules with a right-hand-side LEX indicator are maintained in a list of strings 601, with the set containing strings for those form rules with a LEX indicator in the right-hand-side. The morphological generator algorithm is a recursive process: the chain of form rule references will be searched until the form is found on the list, causing the procedure to bottom out. If the form rule passed into this routine is not in the list, the processor 6 will continue the recursive processing to generate a set of possible form strings by invoking a procedure to generate the stem strings of the given form rule, in a procedure described in detail with reference to FIG. 4B. Referring to FIG. 4B, the recursive process continues in step 625, where the processor 6 determines if the RHS of the caller form rule is a NIL indicator. As described above, a NIL indicates that a particular form does not exist in a given paradigm. If so, the processor 6, in step 626, returns the empty set to the caller. If, in step 625, the RHS is not NIL, the processor 6, in step 630, gets the stem of the form rule passed in and accesses the form rule referenced by the stem. In step 632, the processor 6 then accesses the form string list 601 to determine whether the string for this form rule has already been generated. If so, the result is returned to caller and stored in an intermediate result set 630 (FIG. 4A). Otherwise, in step 24A, the processor 6 makes a recursive call to the morphological generator module 24 to generate the string for the stem form rule. The recursive calling process generates a set of form stem strings, which, in step 638, are returned to step 602 (FIG. 4A). Using the set of strings generated from the stem of the form rule itself, the processor 6 next attempts to generate all possible strings for each form rule variant.
Referring to FIG. 4A, in step 604, the processor 6 accesses information in the compiled rule set data structure 20 to determine whether there are any form variants. If, in step 604 (FIG. 4A), variants are found, the processor 6 attempts, in step 606, to generate a set of strings from the form rule variants. The procedure in step 606 is described in detail below with reference to FIGS. 4C-G. The process of step 606 (FIG. 4A) is a recursive process to yield a set of strings generated from the variant form rules. In step 608, the processor 6 examines the set returned, from step 606 to determine whether any strings were generated from the variants 603. If so, the processor 6, in step 610, returns the set of strings. If, in step 608, variant strings were not generated (or the form rule has no variants), then the processor 6 will take each stem string generated in step 602 and attempt to "apply" the affix of the given form rule to the string.
The "affix application" process begins with a loop at step 612, the processor 6 determining whether all of the strings in the intermediate result set 603 have been processed. If not, the processor 6 accesses the next string, and, in step 618, attempts to apply the affix to the string. The process for applying an affix to the stem string is described in detail below with reference to FIGS. 4D-4G. Referring again, to FIG. 4A, if the processor 6 determines that the application was successful, in step 622, then the resulting string and form rule are added to the form string list 601 and a final result set 623. Once the form rule list and result set are updated, in step 622, or the result is deemed not successful, the processor 6 returns to the top of the loop and proceeds again to step 612. When, in step 612, the processor determines that all stem strings have been processed, the processor 6 returns to step 614 the resulting set of strings that were generated 621.
Referring again to FIG. 4A, the process for generating the form rule variants for a given form rule is depicted in the exemplary process flows of FIGS. 4C-4G. Referring to FIG. 4C, the processor 6 begins, in step 640, by creating a table to be used as a binding list for variable unification in the processing of the affix sequence variables. As was described previously, the affix of a variant form rule comprises an affix sequence, which is a sequence of strings and/or variables. When a given variable is encountered more than once within a given affix sequence, the value of each occurrence of the variable must be the same. In step 642, the processor 6 checks to determine whether all the stem strings have been processed 603; if so, in step 644, the resulting set of strings is returned. Otherwise, the processor 6, in step 646, gets the next stem string. If, in step 648, all the variant form rules (if any) also have been processed for the current form rule, the processor 6 returns to the top of the loop (step 642) and processing continues for another stem string.
However, if, in step 648, all of the variant form rules have not been processed, the processor 6, in step 650, will retrieve the next variant rule and will continue processing as follows.
In step 652, the processor 6 determines whether the variant form rule contains an orthographic parameter. As discussed above, a parameter is used in an orthographic rule to screen out certain lemmas that do not follow the orthographic rule. The parameters occur in the lexicon entries for the words that are governed by a particular orthographic rule having that parameter. Using the parameter value, the lexicon entry can control the application of a variant form rule as follows. If, in step 652, the form rule variant does have a parameter, then the processor 6, in step 654, will attempt to match the parameter against the parameter listed (if any) in the given lexicon entry. If the lexicon parameter matches the parameter found in the rule variant, the processor 6, in step 656, gets the stem form rule (i.e., the "inner" conflated rule) from the outer form rule variant. The processor 6, in step 660, will next attempt to apply the inner variant affix to the stem string in question. The application procedure invokes the process of either stripping or adding the affix to the current stem string. The procedure is described in detail with reference to FIGS. 4D-G. The procedure will return the stem string along with a flag indicating whether the application was successful. If, in step 662, the processor 6 determines that the application procedure was successful, the processor 6 will first add the result to the form string list 601 (FIG. 4A) and then apply, in step 660A, the affix of the outer variant form rule to the resulting string by invoking the same procedure to be described below with reference to FIGS. 4D-G. The subsequent stem string is also added to the form string list 601 as well as to the result set and the processor 6 returns to the top of the loop at step 648 to process another variant for the given stem string.
Referring again to step 662, if the application in step 660 of the affix of the inner conflated form rule to the stem string is not successful, the processor 6 goes to step 660B to apply the affix of the "source" form rule to the stem string. If the processor 6 determines, in step 668, that the application was successful, the processor 6, in step 670, will add that string and form rule to the form rule list 601 and the string to the result set 603, and return to the beginning of the variant processing loop at step 648.
Additionally, referring back to step 654, if this value in the lexicon entry does not match the parameter contained in the variant form rule, the processor 6 jumps to step 660 to attempt to apply the affix of the source form rule to the stem string. If successful, the processor 6, in step 670, will add the resulting string and form rule to the form rule list and the string to the results set 603, and return to step 648 to continue processing.
If, at step 648, the processor 6 determines that there are no more form rule variants to be applied, the processor 6 returns to step 642 to process another string. When, in step 642, the processor 6 determines that there are additionally no more stem strings, the processor 6 will return to step 606 in FIG. 4A the resulting set of strings. FIGS. 4D-G depict an exemplary process flow for applying affixes as implemented in the present invention.
Referring to FIG. 4D, the process for affix application to the stem string begins in step 680, where the processor 6 gets the affix corresponding to the stem string's parent form rule. If the processor 6 determines in step 682, that an affix exists, then the processor 6 invokes a procedure to apply the affix as will be described below. If the processor 6 determines, in step 688, that the application was successful, then the string is returned. If the result of the application in step 686 is unsuccessful, the processor 6, in step 692, returns a null pointer.
FIG. 4E depicts an exemplary process for an affix application to the stem string of step 686 in FIG. 4D. The processor 6 first determines in step 694 whether the affix is a string of characters. If so, the processor 6 invokes a procedure, in step 696, to generate the surface string and the result of that procedure is returned in step 700.
Referring again to step 694, if the affix is not a string, the processor 6 next checks, in step 698, whether the affix contains a reference to an affix variable. If so, the processor 6 will, in step 702, check the lemma entry for the feature value of the affix variable. In step 704, the processor 6 checks to determine if there was a match. If so, the processor 6 takes the matching member of the affix variable set and attempts, in step 696, to generate the surface string as will be described below. If, in step 704, no match exists between any of the affix variable members and the features of the lexical entry, the processor 6 returns null pointer.
Referring back to step 698, if the affix is not an affix variable reference, the processor 6, in step 708, assumes that the affix is an affix sequence (i.e., a sequence of character strings and/or variables), and invokes a procedure, in step 708, described below with reference to FIG. 4G, to generate a string using the affix sequence. In step 710, the processor 6 returns the result of that procedure.
FIG. 4F depicts an exemplary process flow of a surface string generation procedure as invoked by the processor 6 in step 696 of FIG. 4E. The process begins, in step 720, with a determination of whether the affix operator is a plus (+) or a minus (-). If the operator is a plus (+), the processor in step 722 concatenates the affix to the stem string and, in step 724, returns the resulting string. If, in step 720, the operator is a minus (-), the processor 6, in step 726, determines whether the characters of the affix match corresponding characters of the surface form string so they can be stripped off the latter. If there is a match in step 726, the processor 6 will strip off the string characters and return the shortened string to step 696 of FIG. 4E. Otherwise, if, in step 726, no match can be had, the processor 6 returns a null pointer.
Additionally in FIG. 4E, step 708 references a process for generating strings from an affix sequence. FIG. 4G depicts an exemplary embodiment of that process. The affix sequence string generation procedure depicted in FIG. 4G allows for reuse of the affix sequence application procedure of step 426 in FIG. 3E, whose process flow is described above with reference to FIG. 3G. To use the process of step 426 for morphological generation the processor 6 simply reverses the form rule operator on the affix as follows.
In step 740, the processor 6 determines whether the affix operator is a plus (+) or a minus (-). Where the operator is found to be a plus (+), in step 740, the operator is set to a minus in step 742. If, in step 740, the operator is a minus the processor 6 reverses the operator, in step 744, to be a plus. Once reversed, the processor 6 now invokes the affix sequence application of step 426, which is described in detail above with reference to FIG. 3G. The results of that procedure of step 426 are returned by the processor 6 to step 708 in FIG. 4F.
The above described exemplary embodiment of the invention is meant to be representative only, as certain changes may be made without departing from the clear teachings of the invention. Accordingly, references should be made to the following claims which alone define the invention. ##SPC1##
Claims
What is claimed is:
1. For use in computer-based morphological text analysis of natural languages, a computer implemented method for creating a data structure for computer-based generation and recognition of word forms in a natural language, the computer implemented method comprising the steps of: a. providing a morphological description of a natural language, the description comprising statements in a morphological description language, the morphological description language comprising statements arranged according to a pre-determined syntax, the syntax permitting the specification of inflectional morphologic paradigms, the morphologic paradigms comprising form rules including surface form rules and intermediate form rules, the form rules comprising a left-hand-side identifier and a right-hand-side specifying a word stem and, optionally, the concatenation or removal of an affix, including a prefix or a suffix, the stems comprising the identifiers of other form rules or form sets, or a keyword, said keyword being either a keyword LEX or a keyword NIL, the affixes comprising strings of characters or the identifier or an affix variable, the syntax capable of specifying that the form rules of one morphological paradigm are inherited by another morphological paradigm, the syntax permitting the stem in a form rule to be an indicator to a string in a lexicon, the syntax permitting the stem in a form rule to be an indicator that the form rule is not used in the given paradigm via the keyword NIL, the syntax permitting a form set identifier to represent a plurality of left-hand-side form rule identifiers and the form set identifier to be used as the stem in the right-hand-side of a form rule, the syntax permitting an affix variable to identify a set of affix strings with the affix variable being used as an affix in a right-hand-side of a form rule, said morphological description stored in a memory device; b. disambiguating the stem components of the right-hand-sides of the form rules in each paradigm, the disambiguation process comprising the steps of: i. determining in each form rule whether the stem component is an identifier of another form rule; ii. replacing each stem component that is an identifier with a link to the identified form rule; iii. determining in each form rule whether the stem component is an identifier in a form set; c. determining for each paradigm whether there is a declaration stating that the paradigm inherits the form rules of another parent paradigm; d. creating form rules for the paradigms that will inherit the form rule from a parent paradigm by sharing references to the form rules of the parent paradigm; e. replacing, for each form rule that contains a right-hand-side reference to a form set, the form rule with a set of form rules, one for each form in the corresponding form set, each created form rule corresponding to the form set rule containing the right-hand-side reference to the form set; f. checking each surface form for cycles, the cycle check process comprising the steps of: i. creating a cycle check list initialized to empty; ii. locating a surface form rule; iii. checking stem components on the right-hand-side to determine if the stem is an identifier to another form rule; iv. comparing the stem that is an identifier of another form rule to the entries on the cycle check list; v. adding the stem that is an identifier to the cycle check list unless the identifier is included in the cycle check list; vi. checking the form rule referenced by the identifier for cycles; g. providing a set of orthographic rules; and h. conflating the set of orthographic rules, the process of conflation comprising the steps of: i. finding the set of form rules that match one of the orthographic rules in terms of an operator, an affix and an affix type; ii. creating an inner form rule variant, the form rule variant comprising the stem form rule from the right-hand-side of the matching form rule as the right-hand-side stem and as the affix, an affix sequence comprising character strings and string variables, indicating the correct context determined by the orthographic rule, and as the operator a minus; and iii. creating an outer form rule variant, the outer form rule variant comprising the newly created outer form rule as the right-hand-side stem and as the affix, an affix sequence comprising character strings and string variables, indicating the correct spelling as determined by the orthographic rule and as the operator a plus.
2. For use in computer-based morphological analysis of natural language text, a computer implemented method for generating surface forms of a word, the computer-implemented method comprising the steps of: a. providing a lexicon, the lexicon comprising a plurality of word entries, the word entries containing data on each word in a language, including a citation form of the word and a paradigm, with which each lemma is associated, said lexicon stored in a memory device; b. providing a computer-manipulatable data structure containing information concerning the grammatical form construction rules, paradigms and orthographic rules of a natural language, the form rules comprising a left-hand-side (LHS) comprising an identifier and a right-hand-side (RHS) comprising a word stem, an operator, and an affix, the operator indicating an operation to concatenate or remove the affix, the word stem comprising a reference to another form rule, a LEX indicator to signal that the form string is stored in the lexicon, or a NIL indicator to signal that the form is not used in the current paradigm, each form rule having associated with said form rule a set of pre-selected morpho-syntactic features, each form rule capable of being referenced in pre-selected ones of the grammatical construction rules, the orthographic rules being comprised of variables showing the context and result of the rules applicable, with the variables associated with a set of values over which the variables may range, where each orthographic rule applies there being an outer variant form rule to cover the orthographic rule applied to the particular form rule, the computer-manipulatable data structure comprising a set of interconnected nodes, the nodes containing information on the form construction rules, their related paradigms and the orthographic rules and associated sets and variables, said computer-manipulated data structure being stored in the memory device; c. accepting as input at an input device, data identifying a lemma and the name of the desired form with which is associated a set of features, or morpho-syntactic properties; d. locating in the computer-manipulatable data structure stored in the memory device, the form rule in the paradigm associated with the specified lemma that corresponds to the specified form; e. generating intermediate forms for the right-hand-side stems for the form rule; f. locating in the computer-manipulatable data structure stored in the memory device any variants associated with the form rule, the variants comprising form rules representing orthographic variations on the construction of the form rule; g. locating in the lexicon entry for the given lemma an indicator to determine if the orthographic rule applies; h. applying the affix of the variant according to the operator, if one or more stem strings for the variant's stem were successfully generated; i. applying the affix of the (non-variant) form rule according to the operator, unless the variant form rule is applicable; and j. returning, at an output device, the generated form to a user.
3. A computer implemented method for performing computer-based morphological analysis of words in a natural language, the method utilizing a computer, the computer implemented method comprising the steps of: a. providing a syntax for a description of the inflectional morphology of a natural language, said description comprising a set of statements made according to the syntax, said syntax stored in a memory device; b. accepting, at an input device, as input to the computer a set of statements for the description of the inflectional morphology, the set of statements specified according to the syntax; c. creating a computer-manipulatable data structure, using the set of statements made according to the syntax, the data structure comprising a set of interconnected nodes, the nodes comprising information on the statements of the natural language and the nodes being linked by a hierarchical structure and a plurality of interconnecting references; and d. performing morphological analysis using the computer-manipulatable data structure, the morphological analysis comprising inflectional operations as words found in a natural language.
4. A morphological text analyzer for inflection operations for manipulating word forms in a natural language,the morphological text analyzer comprising: a computer processor; a memory storage device coupled to the computer processor; a computer-manipulatable data structure stored in the memory storage device comprising a hierarchical tree with interconnected nodes, the nodes containing computer-manipulatable information concerning the inflectional morphology of a natural language, wherein the computer-manipulatable data structure was created from a mapping of a high-level description of the inflectional morphology of a natural language, the high-level language comprising a syntax to provide for the specification of inflectional paradigms, the mapping being a compiling process to transform a set of statements of the high-level language into the computer-manipulatable data structure; a lexicon stored in the memory storage device comprising a set of word entries each entry comprising inflection information for a word of the natural language; and means, executed by a computer processor, for performing morphological analysis by accessing and manipulating the data structure and the lexicon stored in the memory storage device.