JP2000259629A - Morphological analysis method and its device - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To analyze a document that has not been word-separated, extract words constituting the sentence, and identify the part of speech of each word at a higher speed by a computer. A list of words connectable to a given word is calculated in advance for each word list of each search result in a word dictionary, and the result is used during analysis.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention can be used in all fields including a process of decomposing a continuous character string into constituent word strings. In particular, the present invention is effective in retrieval, machine translation, kana-kanji conversion processing, and natural language interface in which a sentence in a language in which words such as Japanese cannot be separated is input. In the present invention, the term “sentence” does not necessarily mean a sentence ending with a reading mark “.” But refers to a character string that has a meaning that can be understood by a person.

[0002]

2. Description of the Related Art Morphological analysis is a process of analyzing a sentence in a language that is not separated by words, extracting words constituting the sentence, and identifying the parts of speech of each word. Conventionally, the following analysis methods have been used in morphological analysis.

[0003] 文字 is a set of character strings, FT is a set of preceding connection attribute codes of a word, RT is a set of post-connection attribute codes of a word, and a word dictionary D is a finite of Σ × FT × RT × [0, ∞). It is a subset (unknown words and digit strings are not included here). Now, for a character string w, w = (s_w, ft_w, rt
_w, c_w) ∈D, this is called a word w or a morpheme w (hereinafter referred to as a word for simplicity).
Here, s_w is the notation of the word w, ft_w is the connection attribute code before the word w, rt_w is the connection attribute code after the word w,
c_w is the word cost. The word cost c_w is expressed as 0 or a positive real number, and a small value is given when the frequency of use of the word is high. The pre-connection attribute and post-connection attribute of a word are attributes that represent the characteristics of the connection between words, and are determined by the word description, part of speech, inflection type, inflection type, and the like. Also, f
t_start (@FT), rt_start (@RT)
And ft_end (@FT), rt_end (@RT)
Is a special grammatical code representing the beginning and end of a sentence, respectively, and ε is represented by a character string of length 0, and the special grammatical code representing the beginning is w_start = (ε, ft_
start, rt_start, 0), and a special grammar code representing the end is w_end = (ε, ft_end, rt)
_end, 0).

[0004] A function γ indicating the ease of connection between the post-connection attribute RT of a word and the pre-connection attribute FT of a word connected thereto.
, Γ × RT = FT → {x | x is expressed as an integer of 0 or more, or −1}, and a certain word w ′ on the front side and a certain word w thereafter are γ (ft_w, rt_w ′) ≧ 0
When the word w ′ and the word w are connectable, when −1, the word w ′ and the word w are not connectable. Here, the function γ is called a connection cost function, and the value returned by γ is called a connection cost.

The ease of connection between words is expressed by the connection cost between the connection attributes, and the value is an integer of 0 or more. The smaller the value, the easier the connection. For example, a case particle having the notation "ha" and a common noun is generally easily connected, so a small value is given, and a particle "ha" and a particle "ga" are usually not connected, so an infinite value is given.

A set of candidate words starting from position i (≧ 0) of a certain sentence S∈Σ is written as W ＾ start_i (S), and a set of candidate words ending at position i of the sentence is written as W ＾ end_i (S). However, the position i of the sentence is a positive integer and indicates the number between characters, the head position of the sentence S is i = 0, and the position between the i-th character and the (i + 1) -th character of the sentence S is a position i. I will call it.
The candidate word is a word having a continuous substring of the sentence S in the notation. In this case, even if the notation is the same, if the part of speech is different, it is a different candidate word.

[0007] The route information r is divided into three sets (w, P, c) of a word w, a set P of pointers p to the route information, and a cost cc.
c). Here, the pointer p is an address indicating the storage location of the value (w, P, cc) of the route information r. ^* p indicates path information indicated by the pointer p. Also, the entire set of the route information is written as Re.

A set R (S, i, w) of partial solutions from a position i to a word w is a sum of a pointer to a partial solution connectable to and in contact with the word w and a cost to the word w. A set created by selecting one of the routes having the lowest cost from a set of route information R_all (S, i, w) consisting of
It is defined recursively as in (Equation 1).

[0009]

(Equation 1)

Note that the function argmin is a set R∈Re
And an evaluation function f: Re → [0, ∞), and returns a set of R elements that minimize the value of the evaluation function.
Φ represents an empty set.

F and argmin can be defined as (Equation 2).

[0012]

(Equation 2)

A function one extracts one element r = (w, P, cc) from a given set of paths, and further extracts one element p of P to form a set ｛(w,
{P}, cc)} is returned. (As a definition of the set R (S, i, w), a case where an operation for selecting only the element whose rank of the cost c is Nth or less is used, or a set whose cost is within a certain width from the smallest cost is selected. (A calculation may be used.) R (S, i, w_end) is called a morphological analysis solution. This is obtained by obtaining R (S, i, w), (w∈W ＾ start_i (S)) in order from the word whose start position is the previous one.

In the Japanese morphological analysis described above, R
A horizontal search based on dynamic programming is used in the calculation of _all (S, i, w). It is important to reduce this search time to improve the analysis speed.

The following shows a given sentence S and a position i.
And all candidate words w \ W \ start starting with i
_i (S) is a conventionally used procedure for calculating R_all (S, i, w). Here, w ′ is a candidate word ending at position i−1 in the given sentence S. Step 1: For each w \ W \ start_i (S), empty R_all (S, i, w). Step 2: Each w '= (s_w', rt_w ', rt_
w ′, c_w ′) ∈W ＾ end_i (S), the candidate word w ′ is partially resolved r ′ = (w ′, P ′, cc) ∈R
If it has (S, i, w '), the following steps 3 and 4 are repeated. Step 3: Each w = (s, ft_w, rt_w, cw) ∈
The following is repeated for W @ start_i (S). Step 4: If the candidate word w ′ and the candidate word w are connectable (γ (rt_w ′, ft_w) ≧ 0), then r =
(W, P, c_w '+ γ (rt_w', ft_w) + c
c) is added to R_all (S, i, w).

However, in this procedure, the loop of step 2 and step 3 may be reversed.

[0017]

In the conventional method, the combination of words w and w 'which are logically connectable in steps 3 and 4 of the procedure for calculating R_all (S, i, w) And the processing took a long time, but these connectable words w and w '
, Meaningful connection is possible (γ (rt
_w ′, ft_w) ≧ 0) is generally inefficient because the calculation is performed for all cases, although the actual data is as small as about 10%.

[0018]

In the present invention, attention is paid to the fact that the analysis can be performed efficiently and the processing speed can be increased by omitting the check of the correspondence relation of the set of words that cannot be connected at this part. In step 3 of the search, a list of words w 'in W @ end_i (S) that can be connected to the candidate word w is prepared in advance, and step 4 is executed only for a set of connectable words at the time of search. This makes it possible to process Steps 3 and 4 at high speed.

[0019]

DESCRIPTION OF THE PREFERRED EMBODIMENTS In the present invention, in order to operate this object at high speed and to express it with a sufficiently small data amount,
The following data structure is used.

In step 3, connect to the partial solution r 'given in step 2 (in W @ start_i)
The list of words is a set W ＾ start_i (S) of the connection attribute code m ′ and the candidate word w after the word w ′ in the path information r ′.
Can be obtained from Since the number of words included in the word dictionary D is finite, a set L_W (D) of possible W ＾ start_i (S) = {W ＾ start_i (S) | S},
i (0 ≦ i <| S |)} is finite. This is because when the word dictionary D is represented by a trie, | L_W (D) | is suppressed by the number of nodes of the trie.

Therefore, for all post-connection attribute codes rt @ RT and a set W @ start_i (S) of all candidate words w obtained from the word dictionary in advance,
W $ connectable to word w ′ having post-connection attribute code rt
A list of words in start_i can be prepared.

These are represented by an array table A_W which is a set of arrays of the following lists.

For each W∈L_W (D), a pointer sequence AH indexed by the ID number of the subsequent connection attribute code rt
_W and a data string AD_W [rt] indicating the contents of the index of the word in W @ start_i (S). The element of the data string AD_W [rt] pointed to by the pointer string AH_W specifies a list of connectable candidate words in W @ start_i.

FIG. 1 shows this in detail as follows. For example, the word “ha” (ft case particle, rt case particle, 1) of the word w′1 ending at position 2 of the input sentence S “Inu wa Hashiru”
Focusing on 0), consider a case in which a word that can be connected to the connection attribute code rt after this “wa” is searched from the word dictionary D. As the word w whose head part matches “Hashiru” starting from position 2, WL = W ＾ start — 2 from the contents of the word dictionary D corresponding to the search character string “Hashiru”
A word in the block 12 as (S) is given as a candidate word w. Between these candidate words w and the word “ha” of the word of interest w ′ 1, connectable words are (“wa”, ft noun, rt noun, 100), (“hashi”, ft
Noun, rt noun, 100) and ("hasuru", ft verb,
rt verb, 100).

Therefore, when examining the connection between the candidate word w in the block 12 and the word "ha" of the word w'1 ending at position 2, it is clear that it is sufficient to examine the relationship between these three. That is, the present invention pays attention to this point, prepares data on the connectability of words in advance, and performs morphological analysis processing only between connectable words.

Referring to FIG. 1, the pointer string AH_W of the array table A_W is searched, and "ha" of the word w'1 of i = 1 is searched.
Find the pointer corresponding to. Next, the list of connectable words in the pointer string is searched from the data string AD_W [rt] indicating the connectability to the rt case particle, and the data AD_W corresponding to the pointer of “ha” of the word w′1 is retrieved. [Rt case particle] is obtained, “ha” of word w′1 and WL = W ＾ of word D are obtained.
The connection possibility with start_2 (S) is determined. In the case of the input sentence S in the figure, data AD_W [rt case particle] is designated from the pointer sequence AH_W corresponding to “ha” of the word w′1 of i = 1, and data AD_W [rt case particle] , Connectable words are ("wa", ft noun, rt noun, 10
0), ("Hashi", ft noun, rt noun, 100) and ("Hashiru", ft verb, rt verb, 100).

FIG. 2 shows an example in which the search character string starting from the position 2 of another input sentence "Karahashiru" is "Hashiru" as in FIG. Since the search character strings are the same, WL = W @ start_n
Words in the block 12 as (S) are listed as candidate words. On the other hand, by searching the pointer string AH_W of the array table A_W for a pointer corresponding to "he" of the word w'2 ending at position 2, a search is made from the data string AD_W [rt] indicating the possibility of connection to the rt noun. Thus, data AD_W [rt noun] corresponding to the pointer of “he” of the word w′2 can be obtained. in this case,
The words pointed to by AD_W [rt noun] are (“wa”, ft case particle, rt case particle, 100) and (“hashiru”, ft verb,
rt verb, 100).

In the present invention, the array table A_
W @ start_i connectable from W to post-connection attribute rt
The list of words in the middle is obtained simply by the correspondence of the pointer sequence corresponding to W @ start_i, and enables the morphological analysis to proceed only for words that can be connected.

When the word dictionary D is represented by a trie, W∈L_W (D) is given for each node of the trie. In the present invention, the word list WL corresponding to each node of the trie is recorded. Saving the word list WL requires more memory than saving words, but it does not require time to create the list in the morpheme analysis process, leading to higher speed.

Therefore, an array table A_W corresponding to each node of the trie is also determined in advance. By creating the array table A_W in advance for each node of the trie, a high-speed search can be performed when executing the morpheme analysis processing.

FIG. 3 is a diagram for explaining a device for compressing the data amount of the array table A_W. In this embodiment, a case where the pointer sequence AH_W is compressed will be described.

As shown in FIG. 1, the pointers of the pointer sequence AH_W corresponding to the post-connection attribute rt include:
The data string AD_W [rt] corresponds. Therefore, the data amount of the pointer string AH_W is equal to the length of the pointer string AH_W and the data string AH_W specified by the pointer string AH_W.
It has a width corresponding to the width for specifying D_W [rt]. FIG. 3 (a) is drawn in wide columns to schematically show this spread. On the other hand, although not shown in FIG. 1, the data string AD_W designated by the pointer string AH_W
[Rt] is very often the same. FIG. 3 (a)
Here, this is schematically represented by the same characters a, b, and c. As can be easily understood from this, the pointer sequence AH_W is composed of a set of a correspondence table AM_W in which simple index numbers indicating the order of pointers are arranged, and a data list a, b, c indicating the contents corresponding to the index numbers. It is configured in combination with the table AP_W. Therefore, according to the present embodiment, the pointer sequence AH_W can be of a small capacity substantially composed of a column indicating the index number. That is, for the column AM_W of the index number, the number of rows required as data cannot be reduced, but a data amount of 4 bytes is sufficient. The data list AP_W requires the number of bytes required for each data as the data amount, but the number is limited as shown in the figure, so the data amount for the total pointer row AH_W is limited. Can be greatly reduced.

Although the description of the embodiment is omitted, the data string AD_W [rt] can be similarly compressed.

The verification contents of the Japanese morphological analysis program constructed according to the present invention will be described below.

1. Implementation method of program 1.1. Word dictionary For the experiment, a word dictionary of about 530,000 words and 6691 pieces of connection relation information were used.

The words to be used are registered in the dictionary by dividing the stem portion and the ending portion. The connection between the corresponding stem and the ending can be processed by setting a connection relationship of zero cost in a connection cost table described later.

As a result, it is possible to efficiently process the vocabulary words without complicating the structure of the dictionary.
However, on the other hand, there is a disadvantage that the number of candidate words searched from the dictionary at each position of the sentence increases. However, this disadvantage does not adversely affect the analysis time by using the present invention.

The words in this dictionary are the minimum prefix trie (mi
Implemented using a data structure expressed as a double array (double prefix, nimal prefix TRIE) (see “Words and Dictionaries” written by Yuji Matsumoto et al., Iwanami Shoten p.80). However, links with symbols indicating the end of words have been omitted. Therefore, a word can correspond to a node that is not a leaf of the trie tree.

Each node has not only part-of-speech information of a word obtained by connecting the labels of the branches from the head to the node, but also
The point different from the example of the above-mentioned document is that a list (a value indicating) including the word length and part-of-speech information in which the labels of the branches from the beginning to the middle of the path are connected is recorded. With this change, it is not necessary to record and organize information regulated along a route in the middle of searching a dictionary, so that execution time can be saved.

For the list attached to each node,
If node a is an ancestor node of node b, the list recorded in a is the same as a part of the list of b. Therefore, nodes other than the trie leaf node can reduce the total amount of information in this list by referring to a part (only a short one) of the descendant node list. By utilizing this property, the area for storing the list was saved. The character strings of the words were expressed in Japanese EUC code. Each branch of the trie was assigned a value for each byte of the character string.

Next, the tries were represented by a double array. The double array stores link information of a branch from each node of the trie, a value (pointer) indicating a list of word class and length information of words recorded by each node, and a value indicating a character string after the minimum prefix.

This try is performed at a position i of a given sentence S.
Suitable for searching the dictionary for all words that match a string starting with.

1.2. Connection Cost Table The connection cost table is a matrix describing connection costs between the back connection attribute and the previous connection attribute. When the rear connection attribute rt and the front connection attribute ft are connectable, 0 or a positive integer value is described.

1.3. Connectable Word Search Table The pointer row AH_W of the array table A_W, which is a connectable word search table, was created with a data structure composed of two types of arrays as shown in FIG. From the connectable word lookup table corresponding to a list of words,
A list of indices of words that can be connected to the post-connection attribute rt is obtained. Let the ith element of the word list WL be WL [r
t], array table A_ using connection attributes as indexes
A_W [rt] is an element corresponding to W after connection attribute rt,
The list pointed to by A_W [rt] has n elements and its j
If the th element is A_W [rt] [j], the list of words connected to rt is WL [A_W [rt]
[1]], WL [A_W [rt] [2]],. . . , W
L [A_W [rt] [n]].

Further, it is possible to enumerate all connectable words in a time proportional to the number of connectable words by using the arrangement table. This is particularly effective when the word list WL is large.

1.4. Morphological analysis routine Only words that can be connected at high speed are selected using the array table A_W, and the connection cost table is searched for only the connectable words, so that the processing speed is increased.

2. Result As shown in FIG. 3B, the number of the pointer arrays AH_W of the array table A_W used for speeding up the search became 971 by merging the same arrays. The number of data AD_W indicated by the pointer sequence AH_W is 24,362 after merging.

The amount of data for speeding up the search is 4,147,252 bytes in total. The size of the word dictionary (including data of the word list L_W (D)) is about 1
2 Mbytes.

At the time of execution of this embodiment, a maximum of about 22 Mb
It uses the main memory of ytes, but the mapped f
Using the ile system, the main memory can operate even at 10 Mbytes or less. The execution speed depends on the CPU, but up to 3
2,000 bytes / sec or more is possible, which means that a speedup of about 6 to 8 times as compared with the related art can be realized.

The factors enabling this high-speed operation also contribute to improvements such as tuning the memory access method and preparing the word list W @ start_i in the dictionary in advance in addition to the array table A_W. I have.

It should be noted that this method does not truncate the necessary search, so that the result of the search is the same as the conventional method.

[0052]

By using a list of connectable words, the analysis process can be speeded up by increasing the efficiency except for the unnecessary portion of the process that requires the longest processing time in the conventional procedure.

[Brief description of the drawings]

FIG. 1 is a schematic diagram for explaining a flow of a process of searching for correspondence of connectable words using an array table A_W.

FIG. 2 is a schematic diagram for explaining a flow of a process of searching a correspondence of connectable words having parts of speech different from those in FIG. 1 using an arrangement table A_W.

FIG. 3 is a schematic diagram for explaining a device for reducing the data amount of a pointer array AH_W.

[Procedure amendment]

[Submission date] March 15, 1999 (1999.3.1.
5)

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] 0004

[Correction method] Change

[Correction contents]

[0004] A function γ indicating the ease of connection between the post-connection attribute RT of a word and the pre-connection attribute FT of a word connected thereto.
, Γ: RT × FT → {x | x is expressed as an integer equal to or greater than 0 or −1}, and a certain word w ′ on the front side and a certain word w thereafter are γ (ft_w, rt_w ′) ≧ 0
When the word w ′ and the word w are connectable, when −1, the word w ′ and the word w are not connectable. Here, the function γ is called a connection cost function, and the value returned by γ is called a connection cost.

Claims (6)

[Claims] 1. A word string D having a word string D having a meaning and a word dictionary D described by a trie in which a pair of a word notation and a word connection attribute is recorded, and a connection cost table describing connection costs between word attributes. A morphological analysis method for decomposing a sentence S into a word string, wherein a set of words w in a dictionary D starting from a certain position i of the sentence S is defined as W ^ start_i (S), and after a word w 'ending with i-1. When the connection attribute is rt_w ', the connection possibility between the word w' and the word w is determined by the post-connection attribute of rt_w '.
A morphological analysis method that searches only for a relationship with a subset of words in W ^ start_i (S) that can be connected to the word. 2. The connection possibility between the word w ′ and the word w is
2. The morphological analysis method according to claim 1, wherein the post-connection attribute is prepared as an array table indicating connectable words corresponding to rt_w '. 3. The arrangement table is prepared as a table including a pointer string corresponding to the connection attribute rt_w 'after the word w' and a data string indicating a connectable word list corresponding to each pointer of the pointer string. 3. The morphological analysis method according to claim 2, wherein the pointer sequence is composed of an index number indicating the order of the pointer sequence and data indicating the content of the index number, and the same content of the index number is integrated. 4. A sentence comprising a word dictionary D described by a trie in which a pair of a word notation and a word connection attribute is recorded, a connection cost table describing connection costs between word attributes, and a character string having a meaning. A table indicating a set of words w in the dictionary D starting from a position i connectable to a word w ′ ending at a position i-1 of S, and performing a morphological analysis of the sentence S to a subset of the connectable words w A morphological analyzer that searches only for. 5. A connection possibility between the word w ′ and the word w,
The morphological analyzer according to claim 4, wherein the post-connection attribute is prepared as an array table indicating connectable words corresponding to rt_w '. 6. The method according to claim 6, wherein the table is connected to the word w 'after the connection attribute rt
_w 'is prepared as an array table including a data string indicating a connectable word list corresponding to each pointer of the pointer string and each pointer of the pointer string, and the pointer string has an index number indicating an order of the pointer string. 6. The morphological analyzer according to claim 5, comprising data indicating the contents of the index numbers, and integrating the same contents of the index numbers.