Abstract:
A morphological analyzer divides a received text into known words and unknown words, divides the unknown words into their constituent characters, analyzes known words on a word-by-word basis, and analyzes unknown words on a character-by-character basis to select a hypothesis as to the morphological structure of the received text. Although unknown words are divided into their constituent characters for analytic purposes, they are reassembled into words in the final result, in which any unknown words are preferably tagged as being unknown. This method of analysis can process arbitrary unknown words without requiring extensive computation, and with no loss of accuracy in the processing of known words.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to a morphological analyzer and a method of morphological analysis, more particularly to a method and analyzer that can accurately analyze text including unknown words.  
         [0003]     2. Description of the Related Art  
         [0004]     A morphological analyzer divides an input text into words (morphemes) and infers their parts of speech. To be able to conduct a robust and accurate analysis of a variety of texts, the morphological analyzer must be able to analyze words not stored in its dictionary (unknown words) correctly.  
         [0005]     Japanese Patent Application Publication No. 7-271792 describes a method of Japanese morphological analysis that uses statistical techniques to deal with input text including unknown words. From a part-of-speech tagged corpus, a word model and a part-of-speech tagging model are prepared: the word model gives the probability of occurrence of an unknown word given its part of speech, based on character trigram statistics; the part-of-speech tagging model gives the probability of occurrence of a word given its part of speech, and the probability of occurrence of a part of speech given the previous two parts of speech. These models are then used to identify the most likely word boundaries (not explicitly indicated in Japanese text) in an arbitrary sentence, assign the most likely part of speech to each word, output a most likely hypothesis as to the morphology of the sentence, and then generate a selectable number of additional hypotheses in decreasing order of likelihood. The character trigram information is particularly useful in identifying unknown words, not appearing in the corpus, and their parts of speech.  
         [0006]     One problem with this method is that character trigram probabilities do not provide a reliable basis for identifying the boundaries and parts of speech of unknown words. Accordingly, because the method generates only a limited number of hypotheses, it may fail to generate even one hypothesis that correctly identifies an unknown word, and present misleading analysis results that give no clue as to the word&#39;s correct identity. If the number of hypotheses is increased to reduce the likelihood of this type of failure, the amount of computation necessary to generate and process the hypotheses also increases, and the analysis process becomes slow and difficult to make use of in practice.  
         [0007]     Other known methods of dealing with unknown words generate hypotheses for words that tend to occur in personal names, or generate hypotheses for unknown words by using rules or probability models relating to special types of characters appearing in the words (numeric characters, or Japanese katakana characters, for example), but the applicability of these methods is limited to special categories of words; they fail to address the majority of unknown words.  
         [0008]     A more general known method separates all words into their constituent characters, and performs the morphological analysis on the characters by tagging each character with a special tag indicating the word-internal position of the character. This method can analyze arbitrary unknown words, but it involves a considerable sacrifice of accuracy, because it does not make full use of information about known words and groupings of known words.  
         [0009]     It would be desirable to have a morphological analysis method and program and a morphological analyzer that could analyze text including arbitrary unknown words without taking undue time, sacrificing accuracy, or producing misleading results.  
       SUMMARY OF THE INVENTION  
       [0010]     An object of the present invention is to provide an accurate method of performing a morphological analysis on text including unknown words.  
         [0011]     Another object of the invention is to provide a robust method of performing a morphological analysis on text including unknown words.  
         [0012]     The invention provides a morphological analysis method in which one or more hypotheses are generated as candidate results of a morphological analysis of a received text. The hypotheses include a hypothesis in which known words listed in a dictionary are presented together with the individual characters constituting an unknown word. The probability of occurrence of each of the one or more hypotheses is calculated by using a stochastic model that takes account of morphemes, groups of consecutive morphemes, and characters constituting words, and a solution is selected from among the one or more hypotheses according to the calculated probabilities. If the solution includes characters constituting an unknown word, these characters are reassembled to restore the unknown word.  
         [0013]     The invented method is accurate because it makes full use of available information about known words and groups of known words.  
         [0014]     The invented method is robust in that, by dividing unknown words into their constituent characters, it can analyze any unknown word on the basis of linguistic model information about the characters. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]     In the attached drawings:  
         [0016]      FIG. 1  is a functional block diagram of a morphological analyzer according to a first embodiment of the invention;  
         [0017]      FIG. 2  is a flowchart illustrating the operation of the first embodiment during morphological analysis;  
         [0018]      FIG. 3  is a flowchart illustrating the hypothesis generation operation in more detail;  
         [0019]      FIG. 4  shows an example of information stored in a dictionary;  
         [0020]      FIG. 5  shows an example of hypotheses generated in the first embodiment;  
         [0021]      FIG. 6  is a functional block diagram of a morphological analyzer according to a second embodiment of the invention;  
         [0022]      FIG. 7  is a flowchart illustrating the operation of the second embodiment during morphological analysis; and  
         [0023]      FIG. 8  is a flowchart illustrating the parameter calculation operation in more detail. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0024]     Embodiments of the invention will now be described with reference to the attached drawings, in which like elements are indicated by like reference characters.  
       FIRST EMBODIMENT  
       [0025]     The first embodiment is a morphological analyzer that may be realized by, for example, installing a set of morphological analysis programs in an information processing device such as a personal computer. The programs may be installed from a storage medium, entered from a keyboard, or downloaded from another information processing device or network. Functionally, the morphological analyzer has the structure shown in  FIG. 1 . The morphological analyzer may also be implemented by specialized hardware, comprising, for example, one or more application-specific integrated circuits (ASICs) for each functional block in  FIG. 1 .  
         [0026]     The morphological analyzer  100  in the first embodiment comprises an analyzer  110  that performs morphological analysis, a model storage facility  120  that stores a dictionary and parameters of an n-gram model used in the morphological analysis, and a model training facility  130  that trains the model from a part-of-speech-tagged corpus of text provided for parameter training. An n-gram is a group of n consecutive morphemes, where n is an arbitrary positive integer. A morpheme is typically a word, symbol, or punctuation mark.  
         [0027]     The analyzer  110  comprises an input unit  111 , a hypothesis generator  112 , an occurrence probability calculator  115 , a solution finder  116 , an unknown word restorer  117 , and an output unit  118 .  
         [0028]     The input unit  111  enables the user to enter the source text on which morphological analysis is to be performed. The input unit  111  may be, for example, a manual input unit such as a keyboard, an access device that reads the source text from a recording medium, or an interface that receives the source text by communication from another information processing device.  
         [0029]     Given a sentence or other input text to be analyzed, the hypothesis generator  112  generates candidate solutions (hypotheses) to the morphological analysis. The hypothesis generator  112  has a known word hypothesis generator  113  that uses a morpheme dictionary stored in a morpheme dictionary storage unit  121 , described below, to generate hypotheses comprising known words in the input source text, and a character hypothesis generator  114  that generates hypotheses by treating each character in the source text as a character in an unknown word. The full set of hypotheses generated by the hypothesis generator normally includes hypotheses that are generated partly by the known word hypothesis generator  113  and partly by the character hypothesis generator  114 .  
         [0030]     The occurrence probability calculator  115  calculates probabilities of occurrence of the hypotheses generated by the hypothesis generator  112  by using parameters stored in an n-gram model parameter storage unit  122 , described below.  
         [0031]     The solution finder  116  selects the hypothesis with the maximum calculated probability as the solution to the morphological analysis.  
         [0032]     If the solution selected by the solution finder  116  includes characters constituting an unknown word, the unknown word restorer  117  reassembles these characters to restore the unknown word. When the solution selected by the solution finder  116  does not include characters constituting an unknown word, the unknown word restorer  117  does not operate.  
         [0033]     The output unit  118  outputs the optimal result of the analysis (the solution) to the user. The solution may include unknown words restored by the unknown word restorer  117 . The output unit  118  may display the solution, print the solution, transfer the solution to another device, or store the solution on a recording medium. The output unit  118  may output a single solution or a plurality of solutions.  
         [0034]     The model storage facility  120  comprises the morpheme dictionary storage unit  121  and the n-gram model parameter storage unit  122 . In terms of hardware, the model storage facility  120  may be a large-capacity internal storage device such as a hard disk in a personal computer, or a large-capacity external storage device. The morpheme dictionary storage unit  121  and n-gram model parameter storage unit  122  may be stored in the same large-capacity storage device or in separate large-capacity storage devices.  
         [0035]     The morpheme dictionary storage unit  121  stores a morpheme dictionary used by the hypothesis generator  112  for generating hypotheses. The morpheme dictionary may be an ordinary morpheme dictionary.  
         [0036]     The n-gram model parameter storage unit  122  stores the parameters of an n-gram model used by the occurrence probability calculator  115 . These parameters are calculated by an n-gram model parameter calculation unit  132 , described below. The parameters include both parameters relating to characters constituting an unknown word and parameters relating to known words.  
         [0037]     The model training facility  130  comprises a part-of-speech (POS) tagged corpus storage unit  131  and the n-gram model parameter calculation unit  132 .  
         [0038]     In terms of hardware, the part-of-speech tagged corpus storage unit  131  may be a large-capacity internal storage device such as a hard disk in a personal computer, or a large-capacity external storage device storing the part-of-speech tagged corpus.  
         [0039]     The model training facility  130  uses the corpus stored in the part-of-speech tagged corpus storage unit  131  to estimate the parameters of the n-gram model, including parameters related to known words and parameters related to characters constituting unknown words. The estimated n-gram model parameters are stored in the n-gram model parameter storage unit  122 .  
         [0040]     The model training facility  130  may be disposed in a different information-processing device from the analyzer  110  and model storage facility  120 , in which case the n-gram model parameters obtained by the n-gram model parameter calculation unit  132  may be transferred to the n-gram model parameter storage unit  122  through, for example, a removable and portable storage medium. If necessary, this method of transfer may also be used when the model training facility  130  and model storage facility  120  are disposed in the same information-processing device.  
         [0041]     Next, the morphemic analysis method in the first embodiment will be described by describing the general operation of the morphemic analyzer  100  with reference to the flowchart in  FIG. 2 , which indicates the procedure by which the morphemic analyzer  100  performs morphemic analysis on an input text and outputs a result.  
         [0042]     First, the input unit  111  receives the source text, input by a user, on which morphemic analysis is to be performed (step  201 ). The hypothesis generator  112  generates hypotheses as candidate solutions to the analysis of the input source text by using the morpheme dictionary stored in the morpheme dictionary storage unit  121  (step  202 ).  
         [0043]     These hypotheses can be expressed by a graph having a node representing the start of the text and another node representing the end of the text; each hypothesis corresponds to a path from the starting node to the end node. The hypothesis generator  112  executes the operations illustrated in the flowchart in  FIG. 3 . The known word hypothesis generator  113  uses the morpheme dictionary stored in the morpheme dictionary storage unit  121  to generate nodes corresponding to known words (morphemes appearing in the morpheme dictionary) in the text input through the input unit  111 , and adds these nodes to the graph (step  301 ). The character hypothesis generator  114  generates nodes corresponding to the individual characters constituting an unknown word, attaching character position tags indicating the position of each character in the word (step  302 ). The character hypothesis generator  114  uses, for example, four character position tags: a tag (here denoted B) that indicates the first character in an (unknown) word; a tag (denoted I) that indicates an intermediate character in the word (neither the first nor the last character); a tag (denoted E) that indicates the last character in the word; and a tag (denoted S) that indicates the single character in a one-character word. In a language such as Japanese in which word boundaries are unmarked, the character hypothesis generator  114  treats every word as potentially unknown, and simply generate four nodes, tagged B, I, E, and S, respectively, for each character of the input text.  
         [0044]     Returning to  FIG. 2 , the occurrence probability calculator  115  uses an n-gram model with the parameters stored in the n-gram model parameter storage unit  122  to calculate probabilities for each path (hypothesis) in the graph generated in the hypothesis generator  112  (step  203 ).  
         [0045]     In the following discussion, the input text has n elements, where n is an arbitrary positive integer, not necessarily the same as the ‘n’ in the n-gram model. Each element is either a known word or a character in an unknown word. The i-th element will be denoted ‘w i ’ and its part-of-speech tag (if it is a known word) or character position tag (if it is a character in an unknown word) will be denoted ‘t i ’. The notation ‘w i ’ (i&lt;1) and ‘t i ’ (i&lt;1) may be used to denote an element and tag at the beginning of the text, and its tag. The notation ‘w i ’ (i&gt;n) and ‘t i ’ (i&gt;n) may be used to denote an element and tag at the end of the text. Hypotheses, that is, tagged element sequences constituting candidate solutions to the morphological analysis, are expressed as follows.
 
w 1 t 1  . . . w n t n 
 
 Since the hypothesis with the highest probability should be selected as the solution, the best tagged element sequence satisfying equation (1) below must be found.  
                         w   ^     1     ⁢       t   ^     1     ⁢           ⁢   …   ⁢           ⁢       w   ^     n     ⁢       t   ^     n       =       ⁢         arg   ⁢           ⁢   max         w   1     ⁢     t   1     ⁢           ⁢   …   ⁢           ⁢     w   n     ⁢     t   n         ⁢     P   ⁡     (       w   1     ⁢     t   1     ⁢           ⁢   …   ⁢           ⁢     w   n     ⁢     t   n       )                     =       ⁢         arg   ⁢           ⁢   max         w   1     ⁢     t   1     ⁢           ⁢   …   ⁢           ⁢     w   n     ⁢     t   n         ⁢       ∏     i   =   1       n   +   1       ⁢     P   ⁡     (         w   i     ⁢     t   i       ❘       w   1     ⁢     t   1     ⁢           ⁢   …   ⁢           ⁢     w     i   -   1       ⁢     t     i   -   1           )                       ≈       ⁢         arg   ⁢           ⁢   max         w   1     ⁢     t   1     ⁢           ⁢   …   ⁢           ⁢     w   n     ⁢     t   n         ⁢       ∏     i   =   1       n   +   1       ⁢       ∑     M   ∈   M       ⁢     {         λ   1     ⁢     P   ⁡     (         w   i     ⁢     t   i       ❘       w   1     ⁢     t   1         )       ⁢     P   ⁡     (     t   i     )         +                             ⁢         λ   2     ⁢     P   ⁡     (       w   i     ❘     t   i       )       ⁢     P   ⁡     (       t   i     ❘     t     i   -   1         )         +                     ⁢         λ   3     ⁢     P   ⁡     (       w   i     ❘     t   i       )       ⁢     P   ⁡     (       t   i     ❘       t     i   -   2       ⁢     t     i   -   1           )         +                     ⁢       λ   4     ⁢     P   ⁡     (         w   i     ⁢     t   i       ❘       w     i   -   1       ⁢     t     i   -   1           )         }                   ⁢       (         λ   1     +     λ   2     +     λ   3     +     λ   4       =   1     )     .                   (   1   )             
 
         [0046]     In equation (1), the best tagged element sequence is denoted ‘ˆw 1 ˆt 1  . . . ˆw n ˆt n ’ in the first line, and argmax indicates the selection of the tagged element sequence with the highest probability of occurrence P(w 1 t 1  . . . w n−1 t n−1 ) among the plurality of tagged element sequences (hypotheses).  
         [0047]     The probability P(w 1 t 1 . . . w n t n ) of occurrence of a tagged element sequence can be expressed as a product of the conditional probabilities P(w i t i |w 1 t 1  . . . w i−1 t i−1 ) of occurrence of the tagged element in the i-th position in the sequence, given the existence of the preceding tagged elements, where i varies from 1 to n+1. Each conditional probability P(w i t i |w 1 t 1  . . . w i−1 t i−1 ) is approximated as a weighted sum of four terms: in the first three terms, the probability P(w i |t i ) of occurrence of element w i  given tag t i  is multiplied by the probability of occurrence of tag t i , the probability of occurrence of tag t i  given preceding tag t i−1 , and the probability of occurrence of tag t i  given preceding tags t i−1 , and t i−2  and the products are weighted by weights λ 1 , λ 2 , and λ 3 , respectively; in the fourth term, the probability of occurrence of tagged element w i t i  given the preceding tagged element w i−1 t i−1  is weighted by weight λ 4 .  
         [0048]     When the occurrence probabilities have been calculated as described above, the solution finder  116  selects the hypothesis that gives the highest probability of occurrence of the entire text (step  204  in  FIG. 2 ). This hypothesis can be found by use of the well-known Viterbi algorithm, for example.  
         [0049]     If the hypothesis found by the character hypothesis generator  114  includes characters constituting an unknown word, the unknown word restorer  117  reassembles these characters to restore the unknown word (step  205 ). If the hypothesis found by the character hypothesis generator  114  does not include any characters constituting an unknown word, the unknown word restorer  117  does not operate. The characters constituting an unknown word are reassembled by use of their tags. If the B, I, E, and S tags mentioned above are used, the procedure is as follows. Taking the Japanese character sequence ‘ku/B, ru/I, ma/E, de/S, ma/B, tsu/E’ as an example, in which each syllable represents a hiragana character, the characters from each B-tag to the following E-tag are reassembled to form a word and the single character with the S-tag forms another word, producing the sequence of three unknown words ‘ku-ru-ma/unknown, de/unknown, ma-tsu/unknown’.  
         [0050]     Incidentally, the Japanese hiragana character sequence ku-ru-ma-de-ma-tsu is ambiguous in that it can be parsed either as ‘ku-ru-ma de ma-tsu’ (‘wait in the car’) or ‘ku-ru ma-de ma-tsu’ (‘wait until they come’) . This type of ambiguity can be resolved by the use of conventional stochastic models, provided the necessary morphemes are present in the morpheme dictionary so that both candidate hypotheses can be created. In this case, for example, both ‘ku-ru-ma’ and ‘ku-ru’ are necessary; if one or both of these morphemes are missing from the dictionary, conventional analysis may fail. The analysis in the present embodiment succeeds because it can supply the necessary candidate hypotheses by allowing for the possibility that the characters constitute an unknown word.  
         [0051]     When the best hypothesis has been found and any unknown words in it have been restored, the output unit  118  outputs the result to the user (step  206 ).  
         [0052]     The n-gram model parameter calculation unit  132  derives n-gram model parameters for use in the approximation formula given in equation (1) above from the part-of-speech tagged corpus stored in the part-of-speech tagged corpus storage unit  131 , and stores the parameters in the n-gram model parameter storage unit  122 . More specifically, the values P(w i |t i ), P(t i ), P(t i |t i−1 ), P(t i |t i−2 t i−1 ), P(w i t i |w i−1 t i− ), λ 1 , λ 2 , λ 3 , and λ 4  are calculated and stored in the n-gram model parameter storage unit  122 . The values of P(w i |t i ), P(t i ), P(t i |t i−1 ), P(t i |t i−2 t i−1 ), P(w i t i |w i−1 t i−1 ) can be calculated by the maximum likelihood method; the weighting coefficients λ 1 , λ 2 , λ 3 , λ 4  can be calculated by the Expectation Maximization method. These two methods are described on pages 37-41 and 63-66 of ‘kakuritsuteki gengo moderu’ (Stochastic Linquistic Models) by Kenji Kita, published in November 1999 in Japanese by the University of Tokyo Press.  
         [0053]     When the n-gram model parameter calculation unit  132  processes unknown words, or words that occur so infrequently that they can be regarded as being nearly unknown, in the part-of-speech tagged corpus stored in the part-of-speech tagged corpus storage unit  131 , it divides these words into individual characters and attaches the B, I, E, and S tags described above before calculating the n-gram model parameters and storing the results.  
         [0054]     Next the morphological analysis process will be illustrated through an example. First (step  201  in  FIG. 2 ), a user enters a sequence of Japanese kanji and hiragana characters readable as ‘hoso-kawa-mori-hiro-shu-sho-ga-ho-bei’ (‘prime minister Morihiro Hosokawa visits the U.S.A.’), including the unknown word ‘mori-hiro’.  
         [0055]     If the morpheme dictionary storage unit  121  stores the dictionary information shown in  FIG. 4 , the known word hypothesis generator  113  generates hypotheses for the known words as expressed by the upper nodes  611  in the graph  FIG. 5 , thereby performing the first step  301  in  FIG. 3 . The character hypothesis generator  114  performs the next step  302  by adding the characters constituting unknown words to the graph as further nodes  612 . The hypothesis generator  112  then generates hypotheses represented by the entire graph structure  610  in  FIG. 5 , thereby performing step  202  in  FIG. 2 . More specifically, after the known word nodes  611  and unknown word nodes  612  have been generated, the hypothesis generator  112  adds the arcs linking known word nodes  611  to unknown word nodes  612 .  
         [0056]     It should be noted that no arcs are generated that contradict the positional tags. For example, no arcs are generated linking a B-tagged character in an unknown word to another B-tagged character in an unknown word, an E-tagged character in an unknown word to another E-tagged character in an unknown word, or a B-tagged character in an unknown word to a known word.  
         [0057]     The occurrence probability calculator  115  uses equation (1) to calculate the probability of occurrence of each hypothesis (step  203  in  FIG. 2 ). The solution finder  116  finds the hypothesis with the highest probability of occurrence. In  FIG. 5 , this is the hypothesis indicated by the thick lines. The unknown word restorer  117  reassembles the two tagged characters ‘mori/B’ and ‘hiro/E’ located at unknown word nodes  612  in this hypothesis into the unknown word ‘mori-hiro’, and attaches a tag indicating that the part of speech of the word is unknown. The output unit  118  then outputs the tagged sequence ‘hoso-kawa/noun, mori-hiro/unknown, shu-sho/noun, ga/particle, ho-bei/noun’ as the result of the morphological analysis.  
         [0058]     As this example shows, the morphological analyzer  100  in the first embodiment is capable of performing a robust morphological analysis, even when the input text includes unknown words. By dividing an unknown word into its constituent characters, the morphological analyzer  100  can consider arbitrary unknown words that may occur in texts with less computation than conventional systems that process unknown words on a word basis, for while the conventional systems must contend with a substantially unlimited number of possible unknown words, the number of possible constituent characters of these words is limited.  
         [0059]     Compared with conventional systems that divide both known words and unknown words into constituent characters, the system of the first embodiment is more accurate because it can make fuller use of information about known words and groups of known words. That is, it analyzes known words with high accuracy by making use of the known information about the words, and analyzes unknown words in a highly robust manner by dividing the words into their constituent characters.  
         [0060]     Compared with known methods that rely on the appearance of special types of characters in unknown words, the method of the first embodiment is much more useful because it is applicable to all types of words, regardless of the language or type of characters in which they are entered.  
       SECOND EMBODIMENT  
       [0061]     Referring to  FIG. 6 , the morphological analyzer  100 A in the second embodiment adds a maximum entropy model parameter storage unit  123  and a maximum entropy model parameter calculation unit  133  to the structure shown in the first embodiment, and alters the processing performed by the occurrence probability calculator.  
         [0062]     The maximum entropy model parameter calculation unit  133  calculates the parameters of a maximum entropy model from the corpus stored in the part-of-speech tagged corpus storage unit  131 , and stores the calculated parameters in the maximum entropy model parameter storage unit  123 . The occurrence probability calculator  115 A calculates occurrence probabilities from both an n-gram model and a maximum entropy model, using both the parameters stored in the n-gram model parameter storage unit  122  and the parameters stored in the maximum entropy model parameter storage unit  123 .  
         [0063]     The operation of the morphological analyzer  100 A in the second embodiment will be described with reference to the flowchart in  FIG. 7 . The description will focus on the calculation of occurrence probabilities, since in other regards, the morphological analyzer  100 A in the second embodiment operates in the same way as the morphological analyzer in the first embodiment.  
         [0064]     After the text to be analyzed has been entered (step  201 ) and hypotheses have been generated (step  202 ), the occurrence probability calculator  115 A uses the parameters stored in the n-gram model parameter storage unit  122  and maximum entropy model parameter storage unit  123  to calculate occurrence probabilities for the paths (hypotheses) in the graph generated by the hypothesis generator  112  (step  203 A).  
         [0065]     The occurrence probability calculator  115 A in the second embodiment uses the same equation (1) as in the first embodiment, but the conditional probabilities P(w i |t i ) of characters tagged with character position tags, indicating that they belong to unknown words, are calculated from equation (2) below. Equation (2) is not used when the i-th node represents a known word.  
               P   ⁡     (       w   i     ❘     t   i       )       =         P   ⁡     (       t   i     ❘     w   i       )       ⁢     P   ⁡     (     w   i     )           P   ⁡     (     t   i     )                 (   2   )             
 
         [0066]     The value of P(t i |w i ) on the right side of equation (2) is the probability of occurrence of position tag t i , given that the character it tags is w i . If w i  is the i′-th character from the beginning of the text, this probability is calculated according to the maximum entropy method from the following information, in which c x  is the x-th character from the beginning of the text and y x  indicates the character type of character c x : 
    (a) characters (c i′−2 , c i′−1 , c i′ , c i′+1 , c i′+2 )     (b) character pairs    
 
         [0069]     (c i′−2 c i′−1 , c i′−1 c i′ , c i′−1 c i′+1 , c i′ c i′+1 , c i′+1 c i′+2 ) 
    (c) character types (y i′−2 , y i′−1 , y i′, y   i′+2 )     (d) character type pairs    
 
         [0072]     (y i′−2 y i′−1 , y i′−1 y i′ , y i′−1 y i′+1 , y i′y   i′+1 , y i′+1 y i′+2 )  
         [0073]     Character types may include such types as, for example, alphabetic, numeric, symbolic, and Japanese hiragana and katakana. After the occurrence probabilities have been calculated, the optimal solution is found (step  204 ), unknown words are restored (step  205 ), and the result is output (step  206 ) as in the first embodiment.  
         [0074]     The process of calculating the parameters of the n-gram model and the maximum entropy model is carried out in the two steps illustrated in  FIG. 8 . First, as in the first embodiment, the parameters of the n-gram model are calculated from the part-of-speech tagged corpus ( 901 ). This step differs from the first embodiment in that, because equation (2) is used as well as equation (1), the occurrence probability parameters P(w i ) must be calculated as well. Next, the maximum entropy model parameter calculation unit  133  calculates the parameters of the maximum entropy model for calculating the probability of occurrence of character position tags conditioned by characters constituting unknown words, and stores the results in the maximum entropy model parameter calculation unit  133  ( 902 ). The parameters of the maximum entropy model can be calculated by, for example, the iterated scaling method described on pages 163-165 of the Kenji Kita reference cited above.  
         [0075]     The second embodiment provides the same effects as the first embodiment and can be expected to provide the additional effect of greater accuracy in the analysis of unknown words, because of the use of information about character types and notation, including the characters preceding and following each character in an unknown word.  
         [0076]     In a variation of the preceding embodiments, hypotheses are generated to include some of the characters in the input text rather than all of the characters. For example, when the input text includes a character sequence that cannot be found in the dictionary in the morpheme dictionary storage unit, the character hypothesis generator may generate hypotheses in which a predetermined number of characters preceding that sequence, a predetermined number of characters following that sequence, and the characters in the sequence, are treated as characters of an unknown word. This variation reduces the number of hypothesis to be considered.  
         [0077]     Nodes generated by the known word hypothesis generator and nodes generated by the character hypothesis generator need not be treated alike as they were in the embodiments above: for example, the weighting coefficients applied to probabilities such as P(w i |t i ) and P(t i ) may differ depending on whether the node in question (w i ) was generated by the known word hypothesis generator or the character hypothesis generator.  
         [0078]     The set of tags applied the characters constituting unknown words is not limited to the four tags (B, I, E, S) used above. For example, it is possible to use only two tags (B and I) . In this case, the unknown word restorer  117  makes a B-tagged character the first character of a new unknown word, adds each consecutive I-tagged character to the word, and considers that the word has ended when a tag other than an I-tag is encountered. The I-tag is applied not only to intermediate characters in a word, but also to the last character in the word, and the B-tag is also applied to the sole character in a single-character word.  
         [0079]     The embodiments above output the most likely hypothesis obtained as the result of the morphological analysis to the user, but the result of the morphological analysis may be output directly to, for example, a machine translation system or other natural language processing system that provides output to the user.  
         [0080]     The morphological analyzer need not include the model training facility that was included in the embodiments above; the morphological analyzer may include only the analyzer and model storage facility. The information stored in the model storage facility in this case is generated in advance by a separate model training facility, similar to the model training facility in the embodiments above.  
         [0081]     The corpus from which the models are derived may be obtained from a network.  
         [0082]     Applications of the invention are not limited to the Japanese language.  
         [0083]     Those skilled in the art will recognize that further variations are possible within the scope of the invention, which is defined in the appended claims.