JPH077399B2 - Language processing - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a language processing method used in a Japanese continuous speech recognition device, a Japanese word processor of a solid kana-kanji conversion method, and the like. , Given multiple bunsetsu candidates with various character positions as the beginning and ending of kana notation, that is, so-called bunsetsu lattices, consider the certainty of those candidates and the matching degree of dependency between bunsetsus. Insert a sentence, select a bunsetsu from bunsetsu candidates so that an optimum bunsetsu example is constructed as a Japanese phrase or sentence, determine its optimum syntax, and obtain the optimum syntax on the optimum bunsetsu example in Japanese. It relates to a technique for calculating the eligibility as a phrase or a sentence of.

[Prior Art] In order to obtain an appropriate final processing result in a Japanese word processor of Japanese continuous speech recognition or a solid kana-kanji conversion method, (A) polymorphism by morpheme division (B) polymorphism by homophones The two ambiguities of must be resolved. When a kana character string is given, it is judged whether or not it forms a phrase, and if it forms a phrase, enumerating all the homophonic phrases that have that kana character string as the kana notation is the input unit of the phrase. This can be done automatically by using a word dictionary and word connection rules in clauses, as has been done in the conventional Japanese word processor. Therefore, the above ambiguity may be paraphrased as follows.

(A ') Ambiguity of delimiting a given kana character string in bunsetsu units (B') It comes from the fact that there are a plurality of homophones in which each partial kana character string delimited in bunsetsu units is a kana notation Ambiguity The problem of eliminating the above-mentioned polysemy and defining a proper segmentation and an appropriate segment having each delimited substring as kana notation has been mainly in the field of Japanese word processors. Has been studied. The related art will be described below.

(1) As a method of dividing a given kana character string into bunsetsu units, there is a two-bunsetsu longest match method (Makino Hiroshi, Kizawa Makoto: IPSJ Transactions, vol.20, No.4, pp.337-345 (197
9). This is a method in which the length of two consecutive bunsetsus is used as a scale for segmentation and the boundary that gives the longest interpretation as a two bunsetsu form is recognized as the boundary between the two bunsetsus.

(2) Similarly, as a method of dividing a kana character string into bunsetsu units, the minimum bunsetsu number method is known (Kenji Yoshimura, Tatsu Hidaka,
Masashi Yoshida: Morphological analysis of solid Japanese sentences using the minimum number of clauses, IPSJ Journal, vol.24, No.1, pp.40-46
(1983). This is a method of optimizing a division method that minimizes the number of clauses formed when the given kana character string is divided into clause units.

The above two methods are so-called heuristic methods, and there is no clear basis for the optimal division method. Also, there is no function to automatically select an appropriate phrase from multiple phrase candidates that use kana notation as a kana character string delimited by phrase unit, like the conventional word processor that divides and inputs in phrase units. It is necessary to take a measure such as ranking and outputting a plurality of phrase candidates by using information on the frequency of use of words, and letting the user make selections thereafter.

(3) The method of selecting the syntactically most appropriate bunsetsu from the bunsetsu candidates by dividing the given kana character string into bunsetsu units by the two-bunsetsu longest matching method and then performing dependency analysis between bunsetsu Ar (Hiroshi Makino, Makoto Kizawa: Kana-Kanji conversion system for solid writing and its homophone processing, Journal of Information Processing Society of Japan, Vol.2
2, No. 1, pp. 59-67 (1981)). This method is superior to the above methods (1) and (2) in that the Japanese structure is used in selecting a phrase to be output from the phrase candidates. However, the longest two-bunsetsu matching method itself is a heuristic method, and it is not always possible to obtain the optimum way of separating into bunsetsu units. As far as it is allowed, there is a problem that heuristics are used that are the closest between clauses and that are sometimes not satisfied in reality.

In order to eliminate the ambiguity of (A ') and (B'),
Ideally, all possible delimiters that divide the given kana character string into bunsetsu units, and all possible clauses that consist of bunsetsu that uses the partial kana character string that is separated into bunsetsu units as the kana notation Considering both the eligibility as a Japanese sentence or phrase and the certainty of each phrase obtained from the frequency of use of words, etc., from among the columns, the optimal segmentation method and the optimal segmentation in that segmentation method An example should be selected. The following paper is based on this idea.

(4) Yoshimitsu Oshima, Masahiro Abe, Katsuhiko Yuura, Nobuyuki Takeichi: Disambiguation of kana-kanji conversion by case grammar, IPSJ Journal, Vol.27, No.7, pp.679-687, (1986).

However, in this method, since the processing is enumerated by the enumeration method, the amount of calculation becomes enormous, so in the end, the number of bunsetsu strings must be narrowed down by local information before parsing. However, there was a problem that the original idea of selecting the optimum one from all possibilities could not be utilized.

Given a sequence of bunsetsu sets, the method described in the following document is used as an algorithm for selecting the optimum bunsetsu example in consideration of both the consistency of dependency between bunsetsu and the certainty of each bunsetsu. is there.

(5) Kazuhiko Ozeki: Multi-stage decision algorithm for selecting the optimal phrase sequence, The Institute of Electronics and Communication Engineers, Speech Study Group material, SP86-3
2, (1986-7) By using this algorithm, the optimum phrase sequence can be selected at high speed. However, the fact that the bunsetsu set sequence is given is equivalent to the fact that the kana character string is divided into only one bunsetsu unit. It cannot be applied to the problem here, which requires moving all to find the optimal solution.

[Problems to be Solved by the Invention] When a kana character string is given, cut out all the partial kana character strings that can be recognized as a phrase, and enumerate all the phrases that have each such substring as a kana notation, A set of clauses having various kana character positions as the beginning and end of the kana notation can be obtained. Such a set of clauses is called a clause lattice. The phrase lattice is also obtained as an output of a continuous voice recognition device that cuts out a section recognized as a phrase from a continuous voice. Using the term bunsetsu lattice, the problem addressed by the present invention is that "when a bunsetsu lattice is given, any bunsetsu can be arranged so that the end and start ends are continuous as kana character positions. Create a sequence and select the most appropriate sequence of phrases, considering both the eligibility as a Japanese sentence or phrase and the certainty of each phrase. ”

In order to describe the problems in executing this and the purpose of the present invention, first, a strict formulation of this problem is performed.

Here, in order not to make a mistake in the equation containing min, the min (condition concerning x) [f (x)] is used instead of the notation of the condition concerning min f (x) x which is usually used. However, when there is no fear of confusion, [,] may be omitted.

Similar notation is used for argmin, Σ, ∪, etc.

The following [E2] is described in the literature (Kazuhiko Ozeki: Multistage decision algorithm for selecting an optimal phrase sequence, IEICE Speech Study Group material, SP86-32, (1986-7), I will list it here because it is necessary for explanation.

A Japanese sentence, or a set of phrases, can be thought of as being formed by a broadly modified relation between units called bunsetsu. When clause x modifies clause y, x is y
It is said that y receives x. In addition, such a modification relationship is called dependency. In order for a bunsetsu sequence to form a set of phrases or sentences in Japanese, it is considered that there is a dependency between those bunsetsu that satisfies the following conditions.

[C1] A clause other than the last clause relates to any one of the clauses after it.

[C2] Dependency between two bunsetsu does not intersect with dependency between two other bunsetsu.

[C3] To have a dependency between two clauses,
We must wait for a certain relationship between the types and meanings of these clauses.

If the given phrase sequence is correct Japanese, parsing can be performed by such a method, but for the spoken language and the phrase sequence that contains an error, which is likely to occur in the output of the speech recognition device, Analysis can get bogged down.

Therefore, the above condition [C3] should be replaced with a more flexible condition [C'3] for a set of two clauses x and y, where x is replaced by y depending on the part of speech and meaning of the words that compose those clauses. A numerical value representing the degree of matching of is given.

There is a method of searching for a syntax in which the sum of the matching degrees becomes maximum or minimum. This will be explained next.

The conditions [C1] and [C2] can be expressed by a "syntax" defined as follows.

[D1] (1) When x is a clause, (x) is "syntax".

(2) When X ₁ , X ₂ , ..., Xm is "syntax" and x is a clause, (X ₁ X
₂ … Xmx) is the “syntax”.

[D2] The phrase sequence x ₁ , x ₂ , ... xn is properly parenthesized to form a syntax, which is called a syntax on x ₁ x ₂ ... xn. Clause sequence
The overall syntax on x ₁ x ₂ ... xn to be expressed as _{K (x 1 x 2 ... xn} ).

Regarding the condition [C3 ′], it is assumed that the matching degree that the clause x relates to the clause y takes a nonnegative value and is expressed by a function PEN (x, y). It is promised that the closer the value of PEN (x, y) is to 0, the higher the degree of matching. How to determine the function PEN is a very important issue, but this is already considered in the past and is not the main point of the present invention, so its explanation is omitted.

The eligibility P (x) of the syntax X is recursively determined as follows.

[D3] (1) When X = (x), (x is a clause), P
(X) = 0, (2 ) X = (Y 1 Y 2 ... Ymx), Y 1 = (... y 1), Y 2 = (...
When y ₂ ), ..., Ym = (... ym), P (X) = P (Y ₁ ) + P (Y ₂ ) + ... + p (Ym) + PEN (y ₁ , x) + PEN (y ₂ , x) + ... + PEN (ym, x) The value of P (X) thus defined is the sum of the PEN values for all the dependencies in X.

X, Y is a syntax and Y = (Z ₁ Z ₂ … Zmy), where Z ₁ ,…, Zm is a syntax and x is a clause), the syntax can be created by inserting X at the beginning of Y ( If XZ ₁ Z ₂ … Zmy) is written as XY, then for [E1] X = (... x), Y = (... y), P (XY) = P (X) + P (Y) + PEN (x, y) holds. [E2] For any clause sequence x ₁ x ₂ ... xn, (1) when n = 1, K (x ₁ ) = (x ₁ ) (2) When n> 1, K (x ₁ x ₂ ... xn) = ∪ (1 ≤ k ≤ n-1) {XY | X ∈ K (x ₁ x ₂ ... xk), Y ∈ K (xk ₊₁ xk ₊₂ ... xn)}.

[D4] When A ₁ , A ₂ , ..., Am is a set of clauses KB (A ₁ , A ₂ , ..., Am) = {X | ^∃ x ₁ ∈A ₁ , ^∃ x ₂ ∈A ₂ ,… , ^∃ xm ∈ Am, X ∈ K (x ₁ x ₂ …
xm)}. KB (A ₁ , A ₂ , ..., Am) is A ₁ , A ₂ , ..., Am
It is the whole of every syntax on every bunsetsu sequence that can be made by selecting a bunsetsu one by one from.

[D5] (1) integer column i, i + 1, ..., the m division of _{j, i-1 = s 0} <s 1 <s 2 <... < integer pairs satisfying _{sm = j (s 0, s} 1 , s ₂ , ..., sm).

(2) The whole m division of the integer sequence i, i + 1, ..., j is written as Dm (i, j): Dm (i, j) = {(s ₀ , s ₁ , s ₂ , ..., sm) | i-1 = s ₀ <s ₁ <s ₂
<... <sm = j} (3) Further, the whole division D (i, j) of the integer sequence i, i + 1, ..., j
Is defined as follows.

D (i, j) = ∪ (1 ≦ m ≦ j−i + 1) [Dm (i, j)] Now, consider the following situation: [J1] Consider kana character positions from 1 to a natural number N, each i ,
For j (1 ≦ i ≦ j ≦ N), i is the kana notation start position,
A set B (i, j) of clauses with j as the terminal position of kana notation is given. In addition, a non-negative real value S (x) is defined for each clause x.

If the same phrase has a different kana notation start position or kana notation end position, it is treated as a different phrase.

The entire B (i, j) and (1 ≦ i ≦ j ≦ N) described above is referred to as a phrase lattice. Taking the example of a Japanese word processor for solid-character input kana-kanji conversion method, given a kana character string a ₁ a ₂ … a _N , B (i, j) changes its subsequence aiai ₊₁ … aj to a kana. It is the whole phrase that we have as a notation. S (x) is a numerical value that represents the certainty of the phrase x, which is determined from information such as the frequency of use of words. The closer to 0, the higher the certainty. Taking continuous speech recognition as an example, B (i, j) is a set of clauses output by the apparatus as recognition result candidates for the sections having the kana character positions i, j as the start position and the end position, respectively. In this case, S (x) is a numerical value indicating the degree of certainty with which the recognition device recognizes the recognition result x, and most speech recognition devices output such a numerical value together with the recognition result. It is supposed to do. In any case, B (i, j) may be an empty set because there may be no clause starting and ending at the kana character position i, j.
In this case as well, B (i,
When j) is an empty set, a dummy clause is added in advance, and the value of S for the dummy clause is promised to be ∞. When at least one of x or y is a dummy clause, PEN (x,
The value of y) is also promised to be ∞.

In addition, S is expanded so that it can be applied to the syntax. That is, S (X) = Σ (i ≦ m ≦ j) [S (xm)] is defined for XεK (xixi ₊₁ ... Xj).

Under such circumstances, the problem handled by the present invention can be stated as follows. Kana character positions 1, 2, ..., N are fixed, and one of the divisions (s ₀ , s ₁ , s ₂ , ..., Sm) ∈ D (1, N) is selected. Corresponding to this division, the set sequence B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm ₋₁ + 1, sm) is determined. When the clause xk is selected one by one from each clause set B (sk ₋₁ +1, sk), the entire syntax K (x ₁ x ₂ ... xm) is determined. If one syntax X is selected from K (x ₁ x ₂ ... xm), the sum P (X) + S (X) of its eligibility and certainty is determined. Therefore, all of the above divisions, clauses, and syntaxes are moved within a possible range, and the divisions, clauses, and syntaxes that minimize P (X) + S (X) are selected. That is, min ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) [min (x ₁ ∈B (s ₀ + 1, s ₁ ), x ₂ ∈B (s ₁ +1 , s ₂ ), ..., xm ∈ B (sm ₋₁ + 1, sm)) [min (X ∈ K (x ₁ x ₂ … xm)) [P (X) + S (X)]]] The problem here is to find the value of each variable and its minimum value.

In order to select the optimal bunsetsu sequence, it is necessary to consider the eligibility of the bunsetsu sequence as a Japanese sentence or phrase. Therefore, the problem is to obtain an optimal syntax as described above. On the contrary, if the optimum syntax is found, the clause sequences that compose it are determined, so min ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) min (x ₁ ∈B (S ₀ + 1, s ₁ ), x ₂ ∈ B (s ₁ + 1, s ₂ ), ..., xm ∈ B (sm ₋₁ + 1, sm)) min (X ∈ K (x ₁ x ₂ … xm)) [P (X) + S (X)] = min (X∈∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm _-1 +1,
sm))]) Pay attention to [P (X) + S (X)] and rewrite the above problem as a problem whose syntax is variable as follows.

[P1] (1) min (X ∈ ∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1,
N)) [KB (B ( s 0 + 1, s 1), B (s 1 + 1, s 2), ..., B (sm -1 +1,
sm))]) [P (X) + S (X)] and (2) argmin (X∈∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) [KB ( B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ),
,, B (sm ₋₁ + 1, sm))]) [P (X) + S (X)].

Conventionally, to solve this problem, an enumeration method, that is, a set ∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm ₋₁ + 1,1
For every element X of sm))]), P (X) + S (X) had to be calculated step by step to find X that gives the minimum value and the minimum value for it. According to the enumeration method, when the number of clauses in each B (i, j) is J and the total kana character string length is N, the required number of addition arithmetic circuits is Σ (1 ≦ j ≦ N) _N-1 Cj ₋₁ · Jj · L (j) · (2j−1) or the number of comparison operations is given by Σ (1 ≦ j ≦ N) _N−1 Cj ₋₁ · Jj · L (j). Where _N-1 Cj _-1 is a binomial coefficient and L
(J) is the number of syntaxes on the phrase sequence of length j, Can be calculated by

Table 1 shows the above formula calculated for several J and N. As can be seen, in the enumeration method, the calculation amount increases exponentially with respect to the character string length,
It was extremely difficult to apply this to practical problems as it would quickly become huge. Therefore, an object of the present invention is to remedy the above-mentioned drawbacks of the conventional technique, and to significantly improve the complexity as compared with the conventional method in which the calculation amount is a polynomial order with respect to the character string length and the number of elements of each clause set. To provide an efficient language processing method.

[Means for Solving Problems] (5-1) Basic Recursive Equation In describing the configuration of the present invention, a recursive equation that plays a basic role in the present invention will be described. First, the following definitions are provided.

[D6] Fixing the natural number N, 1 ≦ i ≦ m ≦ j ≦ N, XεB
For (m, j) (1) OPTPS (i, j, m, x) = min (X∈∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, m-1 )) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp ₋₁ +1,
sp), {x})]) [P (X) + S (X)] However, when m = i, D (i, m-1) is not defined, but ∪ ((s ₀ , s ₁ , s ₂ , ..., sp) ∈ D (i, m-1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp _-1 +1)
sp), {x}] = KB ({x}).

(2) OPTKS (i, j, m, x) = argmin (X∈∪ (s ₀ , s ₁ , s ₂ , ..., sp) ∈D (i, m−
1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp ₋₁ +1,
sp), {x})]) [P (X) + S (X)] In the above (2), since there are generally a plurality of Xs that minimize P (X) + S (X), OPTKS (i, j , m, x) is a set.

OPTPS and OPT play a fundamental role in the present invention.
The following two recurrence equations [T1] and [T2] satisfied by KS.

[T1] For 1 ≦ i ≦ m ≦ N, x∈B (m, j) (1) When i = m OPTPS (i, j, m, x) = S (x) (2) i < When m, OPTPS (i, j, m, x) = min (i ≦ n ≦ k ≦ m−1) [min (yεB (n, k)) [OPTPS (i, k, n, y) + OPTPS (K + 1, j, m, x) + PEN (y,
x)] [T2] For 1 ≦ i ≦ m ≦ j ≦ N, X ∈ B (m, j) (1) When i = m OPTKS (i, j, m, x) = {(x) } (2) When i <m, give the minimum value in (2) of [T1]
Writing the set of n, k, y pairs (n, k, y) as KTS (i, j, m, x) OPTKS (i, j, m, x) ＝ ∪ (n, k, y) ∈ KTS (i, j, m, x)) [{XY | X∈OPTKS (i, k, n, y), Y∈OPTKS (k + 1, j, m, x)}] Explain what to do.
For that purpose, the following [E3] is shown first.

[E3] ∪ ((s ₀ , s ₁ , s ₂ , ..., sp) ∈ D (i, m-1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ),…, B (sp ₋₁ +1,
sp), {x})] = ∪ (i ≤ n ≤ k ≤ m-1) ∪ (y ∈ B (n, k)) {YX | Y ∈ ∪ ((u ₀ , u ₁ , u ₂ … uq ) ∈D (i, n-1 )) [KB (B (u 0 + 1, u 1), B (u 1 + 1, u 2), ..., B (uq -1 +1,
uq), {y})], X ∈ ∪ ((v ₀ , v ₁ , v ₂ …, vr) ∈ D (k + 1, m +
1)) KB (B (v ₀ + 1, v ₁ ), B (v ₁ + 1, v ₂ ), ..., B (vr ₋₁ + 1, v
r), {x})} This is shown as follows.

Z ∈ ∪ (s ₀ , s ₁ , s ₂ ,, ..., sp) ∈ D (i, m-1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), …, B (sp _-1 +1,
sp), {x})]. Then, (s ₀ , s ₁ ,, s ₂ ,, ..., sp) ∈ D (i, m-
1)) and x ₁ ∈ B (s ₀ + 1, s ₁ ), x ₂ ∈ B (s ₁ + 1, s ₂ ),
..., xp ∈ B (sp _-1 + 1, sp) exists, and Z ∈ K (x ₁ x ₂ ... xpx) holds. From [E2], 1 ≤ t ≤ p and Y ∈ K (x ₁ x ₂
… Xt), X ∈ K (xt ₊₁ xt ₊₂ … xpx) exists, and Z can be written as Z = YX ,.

If n = st ₋₁ + 1, k = st, y = xt, then i ≦ n ≦ k ≦ m−1, y_∈B (n, k), Y∈∪ ((u ₀ , u ₁ , u ₂ …. , uq) ∈D (i, n -1)) [KB (B (u 0 + 1, u 1), B (u 1 + 1, u 2), ..., B (uq +1 +1,
uq), {y})], X ∈ ∪ ((v ₀ , v ₁ , v ₂ …, vr) ∈ D (k + 1, m + 1) [KB (B (v ₀ + 1, v ₁ ), B (v ₁ + 1, v ₂ ), ..., B (vr _-1 +1,
vr), {x})] Therefore, Z∈∪ (i ≦ n ≦ k ≦ m−1) ∪ (y∈B (n, k))
{YX | Y ∈ ∪ ((u ₀ , u ₁ , u ₂ …, uq) ∈ D (i, n−1)) [KB (B
_{(U 0 +1, u 1)} , B (u 1 + 1, u 2), ..., B (uq -1 + 1, uq),
{Y})], X ∈ ∪ ((v ₀ , v ₁ , v ₂ …, vr) ∈ D (k + 1, m + 1)) [KB (B (v ₀ + 1, v ₁ ), B (v ₁ +1, v ₂ ), ..., B (vr _-1 +1,
vr), {x})} and it can be seen that the left side is included in the right side. It is similarly indicated that the right side is included in the left side.

Next, [T1] is shown using [E3].

OPTPS (i, j, m, x) = min (Z∈∪ ((s 0, s 1, s 2, ..., sp) ∈D (i, m-1)) [KB (B (s 0 +1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp _-1 +1,
sp), {x})]) [P (Z) + S (Z)] (by definition) = min (i≤n≤k≤m-1) min (yεB (n, k)) min
{Y ∈ ∪ ((u ₀ , u ₁ , u ₂ …, uq) ∈ D (i, n−1)) [KB (B (u ₀ +
1, u ₁ ), B (u ₁ + 1, u ₂ ), ..., B (uq ₋₁ + 1, uq), {y})], X ∈ ∪ ((v ₀ , v ₁ , v ₂ …, vr ) ∈D (k + 1, m -1)) [KB (B (v 0 + 1, v 1), B (v 1 + 1, v 2), ..., B (vr -1 +1,
vr), {x})]) [P (YX) + S (YX)] (according to E3) = min (i≤n≤k≤m-1) min (yεB (n, k)) min
{Y ∈ ∪ ((u ₀ , u ₁ , u ₂ …, uq) ∈ D (i, n−1)) [KB (B (u ₀ +
1, u ₁ ), B (u ₁ + 1, u ₂ ), ..., B (uq ₋₁ + 1, uq), {y})], X ∈ ∪ ((v ₀ , v ₁ , v ₂ …, vr ) ∈D (k + 1, m -1)) [KB (B (v 0 + 1, v 1), B (v 1 + 1, v 2), ..., B (vr -1 +1,
vr), {x})]) [P (Y) + P (X) + PEN (y, x) + S
(Y) + S (X)] (according to E1) = min (i ≦ n ≦ k ≦ m−1) [min (yεB (n, k)) [OPTPS (i, k, n, y) + OPTPS ( k + 1, j, m, x) + PEN (y,
x)] This shows [T1]. Next, [T2] is shown. Since (1) is clear from the definition, (2) is shown. First, X ∈ ∪ ((s ₀ , s ₁ ,, s ₂ ,, ..., sp) ∈ D (i, m-1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp _-1 +1,
sp), {x})], X∈OPTKS (i, j, m, x) and (P (X) + S (X) = OPTPS
Note that (i, j, m, x)) are equivalent.

Now, to show (2), (a) OPTKS (i, j, m, x) ⊃∪ ((n, k, y) ∈ KTS (i, j, m, x)) [{YX | Y ∈OPTKS (i, k, n, y), X∈OPTKS (k + 1, j, m, x)}] (b) OPTKS (i, j, m, x) ⊂∪ ((n, k, y) ∈ KTS (i, j, m, x)) [{YX | YεOPTKS (i, k, n, y), XεOPTKS (k + 1, j, m, x)}] should be shown. (A) is shown as follows.

Z∈∪ ((n, k, y) ∈KTS (i, j, m, x)) [{YX | Y∈OPTKS (i, k, n, y), X∈OPTKS (k + 1, j, m, x)}], (n, k, y) ∈ KTS (i, j, m, x), Y∈OPTKS (i, k, n, y), X∈OPTKS (k + 1, j, m, x) exists and can be written as Z = YX. Naturally, Z ∈ ∪ (s ₀ , s ₁ ,, s ₂ , ..., sp) ∈ D (i, m-1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ),…, B (sp ₋₁ +1,
sp), {x})], and P (Z) + S (Z) = P (YX) + S (YX) = P (Y) + P (X) + PEN (y, x) + K (Y) + S
(X) = P (Y) + S (Y) + P (X) + S (X) + PEN (y,
x) = OPTPS (i, k, n, y) + OPTPS (k + 1, j, m, x) + PEN (y,
x) = OPTPS (i, j, m, x) Therefore, ZεOPTKS (i, j, m, x) (b) is expressed as follows.

Let ZεOPTKS (i, j, m, x).

Z ∈ ∪ ((s ₀ , s ₁ , s ₂ , ..., sp) ∈ D (i, m-1)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ )] ,…, B (sp _-1 +1,
sp), {x})], and thus [E3], i ≦ n ≦ k ≦ m−1, yεB (n, k), Yε∪ ((u ₀ , u ₁ , u ₂ …, uq) ∈ D (i, n-1)) [KB (B
_{(U 0 +1, u 1)} , B (u 1 + 1, u 2), ..., B (uq -1 + 1, uq),
{Y})], X ∈ ∪ ((v ₀ , v ₁ , v ₂ …, vr) ∈ D (k + 1, m−1)) [KB (B (v ₀ + 1, v ₁ ), B (v ₁ + 1, v ₂ ), ..., B (vr _-1 +1,
vr), {x})] exists and can be written as Z = YX. However, P (Z) + S (Z) = P (Y) + P (X) + S (Y) +
Since S (X) + PEN (y, z) and Z minimizes the left side, Y and X must also minimize the right side. Therefore, as can be seen from the proof of [T1], (n, k, y) ∈KTS (i, j, m, x) Y∈OPTKS (i, k, n, y), E∈OPTKS (k + 1, j, m, x)}] Therefore, Z ∈ ∪ ((n, k, y) ∈ ＝ KTS (i, j, m, x)) [{xY | X ∈ OPTKS (i, k, n, y) , YεOPTKS (k + 1, j, m, x)}] [T2] is shown.

OPTPS (i, j, m, x) has four variables i, j, m, x.
However, m is the start position of the phrase x, and if x is defined,
Determined automatically. Therefore, [D7] (1) I (x) = (starting position of clause x) (2) B (i, j) = ∪ (i ≦ k ≦ j) B (k, j) (3) xεB If OPT (i, j, x) = OPTPS (i, j, I (x), x) is defined for (i, j), [T1] can be rewritten as follows.

[T1 ′] 1 ≦ i ≦ j ≦ N, x ∈ B (i, j) (1) When i = I (x) OPT (i, j, x) = S (x) (2) When i <I (x) OPT (i, j, x) = min (i ≦ k ≦ I (x) −1) [min (yεB (i,
k)) [OPT (i, k, y) + OPT (k + 1, j, x) + PEN (y, x)] Similarly, for OPTKS, [D8] 1 ≦ i ≦ j ≦ N, x ∈ B (i , k) OPTK (i, j, k) ＝ OPTKS (i, j, I (x), x) is redefined to give the minimum value in [D9] [T1 ′] (2). If the set of y pairs (k, y) is written as KT (i, j, x), [T2] can be rewritten as follows.

[T2 ′] For 1 ≦ i ≦ j ≦ N, x ∈ B (i, k) (1) When i = I OPTK (i, j, x) = {(x)} (2) i < When I (x), OPTK (i, j, x) = ∪ ((k, y) ∈KT (i, j, x)) [{YX | Y∈OPTK (i, k, y), X∈ OPTK (k + 1, j, x)}] For an element (k, y) of KT (i, j, x), k is called an optimal segment point for i, j, x, and y is called an optimal clause.

(5-2) OPT and method of determining optimum segment point and optimum clause set [T1 '] (1) is such that when I (x) = i, the value of OPT (i, j, x) is S (x). And [T1 '] (2)
Is I (x)> i, OPT (i, k, y) and OPT (k + 1,
j, x), (i ≦ k ≦ I (x) −1, y ∈ B (i, k) have already been planned, OPT (i, j, x) can be calculated.Using these facts, j-1 starts from the 0 part and OPT
The calculation of (i, j, x) is started, and opt with larger j-i sequentially
(I, j, x), (1 ≤ i ≤ j ≤ N, x ∈ B (i, k)) can be calculated, and at the same time, the optimal segment point and optimal phrase set can be determined. . OPT (1, N, x), (xεB (i,
When k)) is calculated, the calculation of OPT and the optimum segment point and optimum clause pair is completed.

(5-3) Optimum Syntax Calculation Method For simplicity, a case will be described in which the set of optimum segment points and optimum clauses is always uniquely determined.

Then OPTK (i, j, x) is equal to only one syntax.

First, min (X∈∪ (s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ),…, B (Sm ₋₁ +1,
sm))]) [P (X) + S (X)] = min (xεB (1, N)) [OPT (1, N, x)] Therefore, by calculating this right side, the optimum The eligibility for the optimal syntax on the lexical sequence is calculated. If x ₀ = argmin (x ∈ B (1, N)) [OPT (1, N, x)], the optimal clause sequence and the optimal syntax on it are OPTK (1, N, x ₀ ) Given in. This can be calculated more concretely as follows. If I (x ₀ ) = 1, then [T
Since OPTK (1, N, x ₀ ) = (x ₀ ) by (1) of 2 ′], the optimum syntax is determined by this.

If I (x ₀ ) ≠, if the pair of optimal segment points and optimal clause numbers for 1, N, x ₀ is (k ₁ , x ₁ ), then OPTK (1 , N, x ₀ ) = OPTK (1, k ₁ , x ₁ ) OPTK (k ₁ + 1, N, x ₀ ). If I (x ₁ ) ≠ 1, then OPTK
(1, k ₁ , x) is the optimal partition point k ₂ and optimal clause x ₂ for 1, k ₁ , x
Can be decomposed into OPTK (1, k ₁ , x ₁ ) = OPTK (1, k ₂ , x ₂ ) OPTK (k ₂ + 1, k ₁ , x ₁ ). OPTK (k ₁ + 1, N, x ₀ ) is also I (x ₀ ).
≠ k ₁ +1 if in the same manner, k ₁ + _1, N, the optimum segment point k ₃ for x _0, OPTK using the optimal clause _{x 3 (k 1 + 1,} N, x 0 = OPTK (k 1 + 1, k ₃ , x ₃ ) OPTK (k ₃ + 1, N, x ₀ ). Therefore, OPTK (1, N, x ₀ ) = (OPTK (1, k ₂ ,, x ₂ ) OPTK (k ₂ + 1, N , x ₁ )) (OPTK (k ₁ + 1, k ₃ , x ₃ ) OPTK (k ₃ + 1, N, x ₀ )) This decomposition operation is performed on all the appearing OPTK (i, j, x) Repeat until I (x) = i, and when I (x) = i, use (1) of [T2 '] to replace with a syntax consisting of only one clause and insert it by tracing the reverse of decomposition. When the operation is performed, the optimum phrase sequence and the optimum syntax on the phrase sequence can be obtained at the same time.

When there are multiple pairs of optimal segment points and optimal clauses, the same operation is performed for all of these pairs, and all the constructed syntaxes can be the source of OPTK (1, N, x ₀ ).

As described above, according to the present invention, a kana character position determined by a natural number from 1 to N, a set of clauses in which the kana notation start position and the kana notation end position are at various positions within the range of 1 to N, and When a numerical value representing the certainty of a bunsetsu is given, the first bunsetsu is selected under the optimal criterion of minimizing or maximizing the sum of the dependency consistency between two bunsetsu and the numerical value representing the certainty of each bunsetsu. Kana notation start position of is equal to 1, the kana notation end position of the last clause is equal to N, and the value obtained by adding 1 to the kana notation end position of the clause other than the last clause is the kana notation start position of the next clause. The optimal bunsetsu sequence and the optimal syntax of that bunsetsu sequence from among all bunsetsu sequences that can be created by arranging those bunsetsus to satisfy the condition
And a linguistic analysis method that determines its eligibility, the first two-dimensional upper triangular matrix with the number of rows and columns equal to N.
Tables and Table 2 are prepared, and each grid of Tables 1 and 2 has the same number of clauses where the kana notation end position is equal to the column number and the kana notation start end position is greater than or equal to the line number. And divide the first and second tables into three dimensions,
For the q-th clause in the clause set in which the kana notation start position is a natural number i or more and the kana notation end position is a natural number j, when the kana notation start position is equal to i, the i-th row in Table 1 , The j-th column, the q-th term stores the certainty of the phrase, and the natural number k starts from i, the kana notation start position is i or more, and the kana notation end position is equal to j. When moving up to the value obtained by subtracting 1 from the kana notation start end position of the q-th clause of, the items at the i-th row and the k-th column of the first table, and the k + 1-th row, the j-th column of the first table, The calculated value is stored in the q-th term, and if stored, the calculated value of the i-th row, the k-th column, the p-th term of the first table and the k + 1-th row of the first table. , The j-th column, the q-th term, the kana notation start end position is i or more, and the kana notation end position is k Of the p-th clause of the kana notation start end position is i or more and the kana notation end position is j, and the degree of consistency is added, and the addition result The minimum or maximum value for k and p of is stored in the i-th row, the j-th column, the q-th term of Table 1, and k is the optimal partition point that gives the minimum or maximum value.
And a set of values of p, which is the optimum clause number, are stored in the i-th row, the i-th column, and the q-th term of Table 2, and are stored in Tables 1 and 2.
Fill the table sequentially with the calculated values, and
When the calculated value is stored in each item in the first row and Nth column of the table, the minimum value or the maximum value in each item in the first row and Nth column of the first table is set. It is characterized in that the final eligibility and the clause number of the final clause are obtained by obtaining, and the entire set of optimal segment points and optimal clause numbers required for constructing the optimal syntax is obtained in Table 2. .

[Operation] In the present invention, a set of clauses at various positions where the kana notation start end and the kana notation end are in a range from 1 to a natural number N, that is, a clause lattice, and a numerical value indicating the certainty of each clause are given. Then, the optimal bunsetsu sequence is selected from the bunsetsu lattice based on the matching degree of the dependency between the two bunsetsu and the certainty of each bunsetsu, and the optimum syntax for the bunsetsu string is determined. When calculating the eligibility of the syntax, the given two natural number character positions are the kana notation start position and the kana notation end position, respectively, and the Japanese phrase is selected from the entire phrase sequence where the last phrase is fixed. If the most qualified phrase sequence is selected as, and the syntax for it and the qualification for that syntax are calculated, it is memorized and it is determined by the above-mentioned start end and end. By using the same calculation for a longer kana character section including a kana character section, it is systematically avoided that the same calculation is partially repeated. Therefore, by applying the calculation method of the present invention to a given bunsetsu lattice, among all possible bunsetsu bunsetsu, a Japanese phrase or a bunsetsu string most highly qualified as a sentence, a syntax on it, And the eligibility for the syntax can be calculated with a significantly smaller amount of calculation than the conventional method.

It goes without saying that the present invention can be applied not only to the case of Japanese but also to a foreign language having a grammatical structure similar to that of Japanese such as Korean.

EXAMPLES The present invention will be described in detail below with reference to the drawings.

In the following description, kana character positions are 1, 2, ..., N.
Let # (i, j) be the original number of the phrase set B (i, j), and B (i,
The element of j) is represented as xi, j, ₁ , xi, j, ₂ , ..., xi, j, _{# (i, j)} .
Let M be the maximum value of i, j of the original number of the clause set B (i, j).

An embodiment of the apparatus for carrying out the present invention is shown in FIG.

In FIG. 1, SC is a RAM or BUF that holds a numerical value S (xi, j, q) representing the certainty of each clause input from the input terminal i _1.
Is the RA holding the phrase set input from the phrase input terminal i _2.
It is a buffer memory such as M. For example, when the present invention is used for speech recognition, each phrase of the phrase lattice output from the recognition device is input from the terminal i ₂ , and the certainty associated with each phrase is input from the terminal i ₁ . Further, when applying the present invention to solid writing input kana-kanji conversion system Japanese word processors, given kana character string a _1, a _2, ... morphological analysis is first prior art a _N, substring ai, ai ₊₁ ,…, aj
Each bunsetsu candidate that has as a kana notation is i, j (1 ≤ i ≤ j ≤
N) are all listed and input from the terminal i ₂ . At that time, the certainty of each phrase, which is determined by the frequency of use of the word, is input from the terminal i ₁ .

PE is a device that calculates the degree of matching PEN (x, y) of the dependency between the two phrases x and y read from the buffer memory BUF.

T1 and T2 are for realizing the tables TABLE1 and TABLE2 of the flowchart shown in FIGS. 2 (A) and (B).
RAM.

INIT is a phrase start position detector that determines whether or not the start position of the phrase xi, j, q is equal to i, that is, I (xi, j, q) = i.

When the SEL receives a signal from the INIT indicating that the start position of the clause xi, j, q is equal to i, the S held in the SC
(Xi, j, q) is selected and TABL realized in T1
It is a data selection device that writes to E1 (i, j, q).

ADD1 is an adder that adds TABLE1 (i, k, p) and PEN (xi, k, p, xi, j, q).

MIN1 is a minimum value detector for detecting the minimum value of the output of the adder ADD1 when the above p is changed, and p which gives the minimum value.

ADD2 is the output of minimum value detector MIN1 and TABLE1 (k + 1, j, q)
It is an adder that adds and. MIN2 is a minimum value detector for detecting the minimum value when the above k of the output of the adder ADD2 is changed and k which gives the minimum value.

CONT is a control device for controlling the operation sequence of each of these parts, for example, a central processing unit CPU, a memory MEM1 in the form of a ROM for storing the control procedure of each part in advance, and a form of a working RAM. Of memory MEM2. 0 ₁ and 0
Reference numeral ₂ is an output terminal for outputting the results written in the RAMs T1 and T2, respectively.

2A and 2B show the qualification degree of the optimum syntax above the optimum phrase sequence, the optimum phrase sequence, as an example of the control procedure stored in advance in the memory MEM1 in the embodiment shown in FIG. 9 is a flowchart showing a procedure for sequentially obtaining a set of optimum segment points and optimum clauses for determining the optimum syntax thereabove. This will be described below.

As shown in FIGS. 3A and 3B accompanying the flowcharts of FIGS. 2A and 2B, a number of rows and columns equal to the assumed total length N of the character string, and Two three-dimensional tables TABLE1 (i, j, q), TABLE2 having a number of terms equal to the maximum value M of the original number of the clause set B (i, j)
(I, j, q) (1≤i≤j≤N, 1≤q≤M) is required.
The subscripts in each table represent rows, columns, and terms from the left. TA
BLE1 (i, j, q) is the value of OPT (i, j, xi, j, q) and TABLE2
(I, j, q) is for storing a set of optimal segment points and optimal clause numbers for i, j, xi, j, q.

In the flow charts of FIGS. 2 (A) and (B),
In steps S1 to S13, the column number j of each table is incremented by 1 starting from 1 and incremented to N, and the following process is executed for each column.

In steps S2 to S11, i starts from j and is reduced by 1 to 1 and the following processing is executed.

In steps S3 to S9, starting q from 1 with # (i,
It is incremented by 1 up to j) and the following processing is executed.

(1) If I (xi, j, q) = i is determined in step S4, the following is executed in step S7.

[F1] TABLE1 (i, j, q): = S (xi, j, q) (2) If I (xi, j, q)> i is determined in step S4, the following [[ F2], and the following [F3] is executed in step S6.

[F2] min (i≤k≤I (xi, j, q) -1) [min (1≤p
≤ # (i, k)) [TABLE1 (i, k, p) + PEN (xi, k, p, xi, j, q)] + TABLE1 (k + 1, j, q)] and calculates it as TABLE1 (i , j, q). [F3]
TABLE2 shows the pair (k, p) of k and p that gives the minimum value in [F2].
Store in (i, j, q).

Through the above processing, the above calculation is applied to each row, column, and term of TABLE1 and TABLE2, and the results are written into the table in sequence.

When j> N in step S13, the calculation ends, and TABLE1 (1, N, q) has OPT (1, N, x ₁ , _N , q), (1 ≦ q
≦ # (1, N)) is stored. Also, since the information of the optimum segment point and the optimum clause number is stored in TABLE2,
By the method described in the paragraphs (5-2) and (5-3),
From this information, the optimal phrase sequence and optimal syntax can be constructed.

When actually using the present invention, in addition to the flow charts of FIGS. 2 (A) and (B), a mechanism for constructing an optimum clause example and an optimum syntax on it from the information of TABLE2 is required. Since the main point of the invention is to calculate the contents of TABLE1 and TABLE2, the mechanism for constructing the optimal clause sequence and the optimal syntax thereabove from this information will be limited to the above description.

However, if the contents of TABLE1 and TABLE2 can be calculated,
Note that the most computationally expensive part of the computation needed to construct the optimal phrase sequence and the optimal syntax above it from a given set of phrases is no longer done.

There may be multiple pairs of k and p that give the minimum value in [F2]. In that case, TABLE2 (i, j,
Make it possible to store multiple sets of numerical values in q),
All of them should be stored in TABLE2 (i, j, q) in [F3]. Thus, even if the flowcharts of FIGS. 2A and 2B are changed, the calculation amount is almost unchanged.

As described above, the feature of the present invention is that the kana character position i, j
Set of clauses B (i, j) (= 1 ≦ i
≦ N), the kana notation start position of the first clause is equal to 1, the kana notation end position of the last clause is equal to N, and the kana notation end position of the clauses other than the last clause is incremented by 1. Among all bunsetsu strings that can be selected so as to satisfy the condition that they are equal to the starting position of kana notation of bunsetsu, the optimum one when fixing one final bunsetsu x ₁ , _N , q ∈ B (1, N) In obtaining the phrase sequence, the optimum syntax on it, and the eligibility for it, the kana notation start position of the first phrase is equal to i, and the kana notation end position of the last phrase is j.
Under the condition that is equal to, the optimal phrase sequence and the optimal syntax above it when fixing the last phrase as above, and its eligibility are obtained in order from the smallest j−i, K = i, ... When memorizing and determining the above numerical values under the condition that the kana notation start position of the first phrase is equal to i and the kana notation position of the last phrase is equal to j , I (xi, j, q) −1, which is already obtained and stored, has a kana notation start position of the first clause equal to i and a kana notation end position of the last clause equal to k. The above numerical values below, the above numerical values under the condition that the kana notation start position of the first clause is equal to k + 1 and the kana notation end position of the last clause is equal to j, and the clauses xi, k, A function that represents the degree of matching that p ∈ B (i, k) relates to clause xi, j, q ∈ B (i, j). This is where only numerical values are used.

As can be seen from the definition of OPT (i, j, x), the column number j is N or 1 from the last character position of a certain non-dummy clause and the first character position of a certain non-dummy clause. There is no meaning other than the value obtained by subtracting. If such a meaningless column number is known in advance, remove such a column, renumber the remaining columns again, and then perform the above process. , The calculation amount can be further reduced. Similarly, the line number i is 1 or other than a value that is the first character position of a certain non-dummy clause and 1 is added to the last character position of a certain non-dummy clause. Has no meaning. If such a meaningless line number is known in advance, remove such line, renumber the remaining lines again from 1 and perform the above process. , The calculation amount can be further reduced.

In the above-described embodiment, the case of the process of obtaining the minimum value is shown, but the smaller the value of S, the higher the certainty,
This is because the smaller the PEN value, the higher the degree of dependency matching. When the value of S is large, the degree of certainty is high, and as the value of PEN is large, the degree of matching of the dependency is high, the process of obtaining the maximum value instead of the minimum value may be performed.

[Effects of the Invention] Regarding the function PEN indicating the degree of dependency matching, once the calculation is stored, the calculation amount becomes the same between the conventional method and the present invention. Therefore, if this part is excluded, the basic operation is addition and comparison operation of real numbers, so the conventional method and the present invention are compared by the number of times of these operations.

When the total length of a given kana character string is N and the original number of B (i, j) is J, the number of additions in the above embodiment of the present invention is given by the following equation.

2 · J · [Σ (1 ≦ j ≦ N) Σ (1 ≦ i ≦ j−1) Σ
(I + 1 ≦ r ≦ j) Σ (i ≦ m ≦ r−1) [J · (m−
i + 1) +1]] Further, the number of comparisons is given by the following equation.

J · [Σ (1 ≦ j ≦ N) Σ (1 ≦ i ≦ j−1) Σ (i +
1 ≦ r ≦ j) Σ (i ≦ m ≦ r−1) [j · (m−i +
1) +1]] + 2 · J · [Σ (1 ≦ j ≦ N) Σ (1 ≦ i
≤j) [j-i + 1]] These expressions are polynomials of the order of the power of 2 for J and the power of 5 for N.

Table 2 lists these equations calculated for some J and N.

As can be seen by comparing Table 1 and Table 2, the larger the value of J and N, the greater the effect of the present invention.
N = 1 number of additions of about ¹⁰⁷ minutes when 10, one of the comparison operation number about ¹⁰⁶ minutes, and J = 10, N = 40 1 number of additions of about 10 ⁵⁵ minutes when the comparison operation times Is improved to about ^1/1053 .

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of an apparatus for carrying out the present invention, FIGS. 2 (A) and 2 (B) are flow charts showing an example of the control procedure, and FIGS. 3 (A) and 3 (B) are FIG. 3 is a structural diagram showing an example of a table required when executing the flowchart of FIG. 2. SC: Numerical value holding RAM that indicates the certainty of each clause, BUF: Clause set holding buffer memory, PE ... Two clause matching degree calculator, INIT ... Clause kana notation start position detector, SEL ... Data selection device, T1 ... TABLE1 RAM, T2 ... TABLE2 RAM, ADD1 ... adder, MIN1 ... minimum value detector, ADD2 ... adder, MIN2 ... minimum value detector, CPU ... central processor, MEM1 ...... control procedure for storing ROM, MEM2 ...... CPU work RAM, a control device for controlling the operation sequence of the CONT ...... each part, i ₁ ...... clause certainty input terminals, i ₂ ...... clauses input terminal , O ₁ ... Output terminal of the result obtained at T1, o ₂ ... Output terminal of the result obtained at T2.

Claims (1)

[Claims] Claims: 1. A kana character position determined by a natural number from 1 to N, a set of clauses having kana notation start end position and kana notation end position at various positions within the range of 1 to N, and the certainty of those clauses. Kana notation of the first bunsetsu under the optimum criterion that minimizes or maximizes the sum of the dependency consistency between two bunsetsus and the certainty of each bunsetsu when a numerical value is given. The start position is equal to 1, the last phrase's kana notation end position is equal to N, and the value obtained by adding 1 to the kana notation end position of a phrase other than the last phrase is equal to the kana notation start position of the next phrase. The number of rows and columns that are equal to N in the language processing method that determines the optimal bunsetsu sequence, the optimal bunsetsu sequence syntax, and its eligibility from among all bunsetsu sequences that can be arranged to meet the conditions. Have 2 The first table and the second table of the upper triangular matrix of the dimension are prepared, and in each of the grids of the first table and the second table, the kana notation end position is equal to the column number, and the kana notation start end position is The first table and the second table are three-dimensionalized by dividing the number of clauses equal to or greater than the line number into three dimensions, and the kana notation start position is a natural number i or more and the kana notation end position is For the q-th phrase in the phrase set having a natural number j, when the kana notation start position is equal to i, the certainty of the phrase is stored in the i-th row, the j-th column, and the q-th term of the above Table 1. Then, the natural number k starts from i, the kana notation start position is i or more, and the kana notation end position is equal to j, and 1 is subtracted from the kana notation start position of the q-th phrase in the set of phrases. When moving up to the value, each item in the i-th row and the k-th column of the first table (K + 1) th row of Table 1, the j-th column stores the computed values to the q term, if that storage is made, of the computed, the first
The value of the i-th row, the k-th column, the p-th term of the table and the k-th value of the first table
+ 1st row, jth column, qth value and the kana notation start position is i
The p-th clause in the clause set whose kana notation end position is k and whose kana notation end position is j or more and whose kana notation end position is j The degree of matching of the q-th clause is added, and the minimum value or the maximum value of k and p of the addition result is stored in the i-th row, the j-th column, the q-th term of the table 1, A set of values of k, which is the optimum segment point giving the minimum value or the maximum value, and p, which is the optimum clause number, is stored in the i-th row, the j-th column, and the q-th term of Table 2 above, The first table and the second table are sequentially filled with the calculated values, and the calculated values are stored in the first row and the Nth column of the first table and the second table. Then, the minimum value or the maximum value in each item of the 1st row and the Nth column of the above Table 1 is obtained to obtain the final value. A language processing method characterized in that a proper qualification degree and a clause number of a final clause are obtained, and at the same time, the entire set of optimal segment points and optimal clause numbers necessary for constructing an optimal syntax is obtained in the second table.