JPH077400B2 - Language processing method - 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 kana-kanji conversion system Japanese word processor, and the like. When a plurality of bunsetsu candidates whose phonetic transcription ends are at various positions, that is, a so-called bunsetsu lattice is given, the certainty of those candidates and the bunsetsu are related to another bunsetsu at the same time in a certain order. The optimal bunsetsu sequence obtained by selecting the bunsetsu from the bunsetsu candidates and determining its optimal syntax so that the optimal bunsetsu sequence is constructed as a Japanese phrase or sentence, taking into account the degree of consistency of time The present invention relates to a language processing method for calculating eligibility as a Japanese phrase or sentence of the above optimum syntax.

[Prior Art] In a Japanese kana-kanji conversion method for a solid writing Japanese word processor, in order to obtain an appropriate final processing result, the polymorphism due to morpheme division and the polysemy due to homophones, which a given kana character string has, are given. Must be resolved.

Also, in continuous speech recognition, it is possible to assume that the result is first output as a phonetic symbol string, but in consideration of the uncertainty of recognition, usually multiple recognition candidates are used for one time interval. Something is done. Therefore, in this case, in addition to eliminating the above-mentioned polysemy, it is necessary to perform processing for selecting an appropriate one from a plurality of candidates.

In order to solve the above problems, the problem of defining a highly qualified bunsetsu sequence as a Japanese sentence or phrase has been studied as a problem of selecting an optimal bunsetsu sequence from a bunsetsu lattice. When using the sum of the dependency consistency between two clauses and the certainty of each clause as a criterion of eligibility as a sentence or phrase, a conventional method for efficiently solving this problem is described in the following document. Has been.

Kazuhiko Ozeki: “Multistage Decision Algorithm for Selecting Optimal Phrase Sequences from Phrase Lattice”, IEICE Computation Workshop Material, COMP86-48 (1986.11.20) [Problems to be solved by the invention] Phonetic symbols When a sequence is given, cut out all partial phonetic sequences that can be recognized as syllables, and list all the syllables that have each such subsequence as phonetic notation, the various phonetic symbol positions A set of clauses at the beginning and the phonetic transcription end is 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 in it can be arranged so as to satisfy the condition that the end and start ends are continuous as phonetic writing positions. Create a bunsetsu sequence, and select the most appropriate bunsetsu sequence, taking into consideration both the eligibility as a Japanese sentence or phrase and the certainty of each bunsetsu. "

As mentioned in the explanation of the prior art, when the eligibility as a Japanese sentence or phrase is defined by the sum of the degree of dependency matching between two clauses, a method for efficiently solving this problem is available. Already known. However, in this way of determining eligibility, even if the order of bunsetsus related to one predicate is unnatural or the case of bunsetsus related to one bunsetsu is unnatural, There is a problem that it may have the same eligibility as a natural sentence that has nothing to do with it. In order to completely solve such inconvenience, the eligibility as a Japanese sentence or phrase is determined not by the sum of the degree of dependency matching between two bunsetsus, but by a plurality of bunsetsus at the same time as another one. Although it is necessary to determine it based on the degree of consistency of the clause,
If the eligibility is set as such, only the enumeration method is known to solve the above-mentioned problem, and this cannot be executed due to the problem that the amount of calculation becomes huge.

Therefore, an object of the present invention is that the eligibility as a Japanese sentence or phrase is not the degree of dependency matching between two bunsetsu, but that a plurality of bunsetsus are related to one other bunsetsu at the same time. When it is based on the degree of matching, it selects the optimal phrase sequence as a Japanese sentence or phrase from the given phrase lattice, determines the syntax above it, and determines the Japanese phrase or phrase of the obtained phrase sequence. It is to provide a language processing method capable of calculating the eligibility of a sentence significantly more efficiently than the enumeration method.

[Means for Solving Problems] (a) Japanese Structure in Phrase Units In describing the configuration of the present invention, first, a Japanese structure in bunsetsu units will be described.

A Japanese sentence, or a set of phrases, can be thought of as being formed by a broadly modified relation between units called bunsetsu. For example, in the Japanese sentence [S1] "I go to the office by train at 7 o'clock", "I am", "7 o'clock",
"By train", "To the company", and "I'm going" are phrases, and "I", "By train", and "To the company" are all modified to "Go", and "Constitutes a single sentence by modifying" by train ".

When clause x modifies clause y, x is related to y and y is x
To receive. 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] The clauses other than the last clause relate to any one of the clauses on the end side of the clause.

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

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 are “syntax” and x is a clause, [X ₁ X ₂ ... XmX] is “syntax”.

[D2] The phrase sequence x ₁ x ₂ ... xn with proper parenthesis to obtain the syntax is called the syntax on x ₁ x ₂ , ... xn. Clause sequence x
The overall syntax on ₁ x ₂ ... xn to be expressed as _{K (x 1 x 2 ... xn} ).

Syntax [X ₁ X ₂ ... Xmx], X ₁ = [... x ₁ ], X ₂ = [... x ₂ ], ..., Xm
Assuming that x = ₁ , ... x ₂ , ..., xm in x = [... xm] is related to x, the syntax in the above sense is
Dependency relations in a clause sequence satisfying the conditions [C1] and [C2] and the conditions [C1] and [C2] can be expressed by the syntax in the above meaning.

Now, for one clause sequence, there are multiple syntaxes above it. For example, [[I] [7 o'clock] [by train] [company] go] [[[[[I] 7 o'clock] by train] go] [] [[[i] [7 o'clock by train] [go to work] [] [[I] [[7] go by train] go] [[I] [[7] go by train] [Go to company], etc. are all the syntax on the clause sequence of the example sentence [S1]. Some kind of evaluation function is necessary to select a highly qualified phrase sequence from among many such syntaxes. Therefore, it is assumed that the degree of dependency matching is determined as follows.

[C3] Consistency that clauses x ₁ , x ₂ ,, ..., xm relate to clause x in this order is represented by a non-negative function PEN (x ₁ , x ₂ ,, ..., xm, x) .

We promise that the closer the PEN value is to 0, the higher the degree of matching. How to define the function PEN is a very important issue, but this is not the main point of the present invention, and therefore its explanation is omitted. With the above preparations, the eligibility P (X) of the syntax x
Is recursively determined as follows.

[D3] (1) X = [x], (x is clauses) When, P (X) = 0, (2) X = [X 1 X 2 ... Xmx], X 1 = [... x 1], X ₂ = […
When x ₂ ], ..., Xm = [... xm], P (X) = P (X ₁ ) + P (X ₂ ) + ... + P (Xm) + PEN (x
₁ , x ₂ , ..., xm, x) The value of P (X) thus defined is the sum of the PEN values for all the dependencies in X.

Some notation is prepared for use in later explanation.

[D4] (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 ₁ , s ₂ , ..., sm).

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

D (i, j) = ∪ (1 ≦ m ≦ j−i + 1) [Dm (i, j)] [D5] Phrase set sequence A ₁ , A ₂ , ..., Am to KB (A ₁ A ₂ ... Am) = {X | X ∈ K (x ₁ x ₂ … xm), x ₁ ∈ A ₁ , x ₂ ∈ A ₂ ,…, xm ∈ Am} (b) Problem setting In the following, make long mathematical expressions easy to read. For Instead of, the notation Σ (i ≦ m ≦ j) [f (m)] is used. The same applies to min, argmin and ∪. Brackets [,] may be omitted if there is no risk of confusion.

Now consider the following situation: [J1] Consider the phonetic symbol positions from 1 to a natural number N, for each i,
For j (1 ≦ i ≦ j ≦ N), i is the phonetic notation start position,
A set B (i, j) of clauses having j as a phonetic transcription end position is given. In addition, a non-negative real value S (x) is defined for each clause x.

If the phonetic transcription start position or the phonetic transcription end position is different even in the same phrase, 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 input kana-kanji conversion method, given a kana character string a ₁ a ₂ ... a _N , B (i, j) is the partial kana character string a ₁ ai ₊₁ ... a
It is the whole clause that has j as a kana 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 zero, the higher the certainty. Taking continuous speech recognition as an example, B (i, j) is output by the device as a recognition result candidate for a section in which the phonetic symbol position i, j is the phonetic transcription starting end position and the phonetic transcription end position, respectively. It is a set of clauses. In this case, S (x) is a numerical value indicating the degree of certainty with which the recognition device has recognized 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 either case, since there may be no clause starting and ending at the phonetic symbol positions i, j, B
(I, j) can be an empty set. Also in this case, when B (i, j) is an empty set, a dummy clause is added so that no special handling is required, and the value of S for the dummy clause is ∞.
I promise you. Also, when at least one of x ₁ , x ₂ , ..., xm, x is a dummy clause, the value of PEN (x ₁ , x ₂ , ..., xm, x) 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 addressed by the present invention can be stated as follows. The phonetic symbol 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 +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 the 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 +
1, sm)) [min (X∈K (x ₁ x ₂ ... xm)) [P (X) + S
The problem here is to find the value of each variable that achieves (X)]]] 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 other hand, 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, s
m)) [min (X∈K ( x 1 x 2 ... 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, s
m))]) [P (X) + S (X)] and rewrite the above problem as a problem with syntax as follows:

[P1] Find the following two things.

(1) min (X ∈ ∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)
[KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm _-1 +1,
sm))]) [P (X) + S (X)] (2) argmin (X∈∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1,
N) [KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm _-1
+ 1, sm))]) [PX) + S (X)] Conventionally, the solution to this problem is enumeration, that is,
Set ∪ ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (1, N)) [KB (B (s ₀ +
1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm ₋₁ + 1, sm))] for every element X of P (X) + S (X), It was necessary to find X that gives the minimum value and the minimum value for it. However, as shown in Table 1, the original number of this set rapidly increased with N and became enormous, and it was impossible to apply the enumeration method to practical problems.

Set ∪ ((s ₀ , s ₁ , ..., sm) ∈ D (1, N) [KB (B (s ₀ +1,
s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sm ₋₁ + 1, sm))] for any i, j (1 ≦ i ≦ j ≦ N) Let M be the original number of B (i, j).

According to the present invention, such drawbacks of the prior art are remedied,
It is possible to provide a language processing method that requires a significantly smaller amount of calculation than the enumeration method.

The function PEN is PEN (x ₁ , x ₂ ,, ..., xm, x) = PEN (x ₁ , x) + PEN (x ₂ x) + ... + PEN (xm, x) When it can be expressed as a sum, this problem can be solved efficiently by the above-mentioned conventional method. On the other hand, the present invention is symmetric when the function PEN cannot be decomposed into such a sum.

(C) 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] (1) B (i, j) = ∪ (i ≦ m ≦ j) [B (m,
j)] (2) For xεB (i, j), set INIT (x) to xεB
When (m, j), INIT (x) = m.

[D7] With the natural number N fixed, 1 ≦ i ≦ j ≦ N, x ∈ B (i, j)
For (1) OPT (i, j; x) = min (X ∈ ∪ ((s ₀ , s ₁ , s ₂ , ..., s
p) εD (i, INIT (x) −1)) [KB (B (s ₀ + 1, s ₁ ),
B (s ₁ + 1, s ₂ ), ..., B (sp _-1 + 1, sp), {x})])
[P (X) + S (X)] (2) OPK (i, j; x) = argmin (Xε∪ ((s ₀ , s ₁ , s ₂ , ...,
sp) ∈ D (i, INIT (x) -1)) [KB (B (s ₀ +1,
s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp ₋₁ + 1, sp),
{X})]) [P (X) + S (X)] In the above (1) and (2), when INIT (x) = i, D (i, INIT (x) -1) is defined. However, in this case ∪ ((s ₀ , s ₁ ,, s ₂ ,, ..., sp) ∈ D (i, INIT (x) -1))
[KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp _-1 +1,
sp), {x})] = KB ({x}). Also, since there are generally a plurality of Xs that minimize P (X) + S (X), OPK (i, j; x) is a polymerization.

For OPT and OPK defined in this way, the following recurrence equation holds.

For [E1] xεB (i, j), (1) when INIT (x) = i OPT (i, j; x) = S (x) (2) when INIT (x)> i OPT (i, j; x) = min ((s ₀ , s ₁ , s ₂ , ..., sm) ∈ D (i, INIT
(X) −1), x ₁ ∈B (s ₀ + 1, s ₁ ), x ₂ ∈B (s ₁ +1,
s ₂ ), ..., xm ∈ B (sm ₋₁ + 1, sm)) [OPT (s ₀ + 1, s ₁ ;
x ₁ ) ＋ OPT (s ₁ + 1, s ₂ ; x) ＋… ＋ OPT (sm _-1 + 1, sm; xm)
_{+ PEN (x 1, x 2} , ..., xm, x)] + S (x) [E2] x∈B (i, j) with respect to, (1) INIT (x) = when i OPK (i, j ; x) = [X] (2) When INIT (x)> i, the minimum value is given in (2) of [E1] s ₀ , s ₁ , s ₂ , ..., sm, x ₁ , x ₂ , …, Xm respectively s ₀ , s ₁ ,
When s ₂ , ..., sm, x ₁ , x ₂ , ..., xm OPK (i, j; x) = [OPK (s ₀ + 1, s ₁ ; x ₁ ) OPK (s ₁ + 1, s ₂ ;
x ₂ ) ... OPK (sm ₋₁ + 1, sm; xm) x] [E1] and [E2] can be easily proved by noting that the following [E3] holds, so detailed description will be omitted.

[E3] ∪ ((s ₀ , s ₁ , s ₂ , ..., sp) ∈ D (i, INIT (x) -1)}
[KB (B (s ₀ + 1, s ₁ ), B (s ₁ + 1, s ₂ ), ..., B (sp _-1 +1,
sp), {x})] = ∪ ((t ₀ , t ₁ , t ₂ , ..., tm) ∈ D (i, INIT (x) -1), x
₁ ∈ B (t ₀ + 1, t ₁ ), x ₂ ∈ B (t ₁ + 1, t ₂ ), ..., xm ∈ B (t
m ₋₁ + 1, tm)) {[X ₁ X ₂ … Xmx] | x ₁ ∈ ∪ ((s _1,0 , s _1,1 , s _1,2 , ..., s _{1, p1} ) ∈ D (t ₀ + 1, I
NIT (x ₁ ) -1)) [KB (B (s _1,0 + 1, s _1,1 ), B (s
_{1,1 + 1, s 1,2),} ..., B (s 1, p1-1 + 1, s 1, p1),
{X ₁ })], x ₂ ∈∪ ((s _2,0 , s _2,1 , s _2,2 , ..., s _{2, p 2} ) D (t ₁ + 1, I
_{NIT (x 2) -1))} [KB (B (s 2,0 + 1, s 2,1), B (s
_{2,1 + 1, s 2,2),} ..., B (s 2, p2-1 + 1, s 2, p2),
_{{X 2})], ...} , xm∈∪ ((s m, 0, s m, 1, s m, 2, ..., s m, pm) ∈D (tm -1 +
1, INIT (xm) -1)) [KB (B (s _{m, 0} + 1, s _{m, 1} ), B
( _{Sm, 1} + 1, sm _{, 2} ), ..., B (sm _{, pm-1} + 1, sm _{, pm} ), {x
m})]} Now, the syntax [X ₁ X ₂ … Xmx], X ₁ = [… x ₁ ], X ₂ ＝ […
In x ₂ ], ..., Xm = [... xm], x ₁ , x ₂ , ..., Xm relate to x. That is, x receives x ₁ , x ₂ , ..., Xm, but it can be considered that there is a certain upper limit to the number of clauses that one clause receives. When this upper limit is L, in [E1], the minimization may be performed within the range of 1 ≦ m ≦ L. With such restrictions, [E1] is as follows.

For [E1 ′] xεB (i, j), (1) when INIT (x) = i OPT (i, j; x) = s (x) (2) INIT (x)> i When OPT (i, j; x) = min (1 ≦ m ≦ L, (s ₀ , s ₁ , s ₂ …, sm) ∈
(I, INIT (x) −1), x ₁ εB (s ₀ + 1, s ₁ ), x ₂ εB ( ₁
+ 1, s ₂ ), ..., xm ∈ B (sm ₋₁ + 1, sm)) [OPT (s ₀ +1,
s ₁ ; x ₁ ) ＋ OPT (s ₁ + 1, s ₂ ; x ₂ ) ＋… ＋ OPT (sm _-1 ＋, sm; x
_{m) + PEN (x 1,} x 2, ..., xm, x)] + S (x) be provided such limitations, there is no effect on the [E2]. N
If ≤L, [E1 '] is the same as [E1]. That is, [E1 '] includes [E1] as a special case. Therefore, hereinafter, the description will be made using [E1 ′].

In [E1 ′] (2), s ₁ , s ₂ , ..., Sm giving the minimum value
Are called optimal segment points for i, j, x, and x ₁ , x ₂ , ..., xm are optimal segments at these segment points.

(D) Method for determining OPT, optimal segmentation point, and optimal clause (2) of [E1 '] is OPT (s, when INIT (x)> i.
t, y) (i ≤ s ≤ t ≤ j, y ∈ B (s, t)) has already been calculated, we show that OPT (i, j; x) can be calculated using those values. There is. When INIT (x) = i, using (1) of [E1 ′], OPT (i, j; x) = S
The value of OPT (i, j; x) is determined as (x). Using these facts, the value of OPT (i, j; x) is calculated starting from the part where j−i is 0 and proceeding to the part where j−i is larger,
At the same time, it is possible to determine the optimum segment point and optimum phrase set. When OPT (1, N; x) and (xεB (1, N)) have been calculated, the calculation of the set of OPT, the optimal segment point, and the optimal clause number ends.

(E) Optimal Syntax Calculation Method For simplicity, a case will be described in which the set of optimal segment points and optimal clause numbers is always uniquely determined. At this time, OPK (i,
j; x) (1 ≦ i ≦ j ≦ N, xεB (i, j)) is equal to only one syntax.

First, 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, s
m))]} [P (X) + S (X)] = min (xεB (1, N)) [OPT (1, N, x)] Therefore, by calculating this right side, the optimum The sum of the eligibility and the reliability for the optimum syntax on the lexical sequence is calculated. If x ₀ = argmin (x ∈ B (1, N)) [OPT (1, N, x)], the optimal phrase sequence and the optimal syntax on it are OPK (1, N, x ₀ ) Given in. This can be calculated more concretely as follows.

If INIT (x ₀ ) = 1, OPK (1, N, x ₀ ) = [x ₀ ] according to (1) of [E2], and thus the optimum syntax is determined.

If INIT (x ₀ ) ≠ 1, the optimal segment points for 1, N, x ₀ are s ₁ ,, s ₂ , ,,, sm, and the corresponding optimal clauses are x ₁ , x ₂ , ,,, xm, respectively, [E2 ] (2) in OPK (1, N, x ₀ ) = [OPK (1, s ₁ ; x ₁ ) OPK (s ₁ + 1, s ₂ ; x ₂ ) ... OPK (sm _-1 +
1, sm; xm) x ₀ ] holds. If INIT (x ₁ ) = 1, OPK (1, s ₁ ; x ₁ ) = [x ₁ ], so OPK (1, N, x ₀ ) = [[x ₁ ] OPK (s ₁ +1 , s; x ₂ ) ... OPK (sm _-1 + 1, sm; xm) x
_0] In addition, INIT (x ₁₎ ≠ ₁ if _1, s 1, t 1 an optimum segment point for x _1, t _2, ..., respectively optimum clause corresponding to tp y _1, y _2,
..., yp OPK (1, s ₁ ; x ₁ ) = [[OPK (1, t ₁ ; y ₁ ) OPK (t ₁ + 1, t ₂ ; y ₂ ) ... OPK (tp _-1
Since + 1, tp; yp) x ₁ holds, OPK (1, N, x ₀ ) can be rewritten as follows.

OPK (1, N, x ₀ ) = [[OPK (1, t ₁ ; y ₁ ) OPK (t ₁ + 1, t ₂ ; y ₂ ) ... OPK (tp _-1
+ 1, tp; yp) x] ₁ OPK (s ₁ + 1, s ₂ ; x ₂ ) ... OPK (sm _-1 + 1, s
m; xm) x ₀ ] If we continue this kind of operation until the OPK that appears has a syntax consisting of only one clause, then OPK (1, N, x ₀ ),
That is, the optimum phrase sequence and the optimum syntax on it can be determined at the same time.

For one set of i, j, x (1 ≤ i ≤ j ≤ N, x ∈ B (i, j)), there may be a plurality of sets of optimal clauses corresponding to optimal segment points. In this case, the above operation should be performed for all the sets, and all the obtained syntaxes should be listed.

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 such as Korean that can be described by the same dependency as Japanese.

[Operation] According to the present invention, the optimum phrase sequence when the last phrase is fixed within the range of the subsequence i, i + 1, ..., j of the given character string positions 1, 2, ..., N. And its optimal syntax, and its eligibility, are sequentially sought from the ones corresponding to the short subsequences and stored, and the same is applied to the longer subsequences containing those subsequences. By utilizing them when calculating things, the desired result can be efficiently obtained without repeating the same calculation.

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

In the following description, phonetic symbol positions are 1, 2, ..., N. In the following, the original number of the phrase set B (i, j) is NUM (i,
j) and the element of B (i, j) is B (i, j) = {x _{i, j, 1} , x _{i, j, 2} , ..., x _{i, j, NUM (i, j)} } Enumerate and represent.

An embodiment of the apparatus for carrying out the present invention is shown in FIG. First
In the figure, SC is a buffer memory such as a RAM for realizing the table score described in the flowcharts shown in FIGS. 2A and 2B, and the input terminal i1
This is for holding the certainty S (x _{i, j, q} ) of each clause x _{i, j, q} input from. BUF is a buffer memory such as a RAM that holds a phrase set input from the phrase input terminal i2. Each phrase describes not only its phonetic symbol string but also the information of the beginning and end. As an example, when the present invention is used for speech recognition, each phrase candidate output from the recognition device as a recognition result is input from the terminal i2, and the certainty associated with those phrases is input from the terminal i1. Further, when the present invention is applied to a solid writing input kana-kanji conversion method Japanese word processor, a given kana character string a ₁ , a ₂ ,
…, A _N is first morphologically analyzed by the conventional technique, and the partial kana character string a
Each bunsetsu candidate that has i, ai ₊₁ , ..., aj as a kana notation is i, j
All (1≤i≤j≤N) are listed, and the phrase candidates are input from the terminal i2. At that time, the certainty of each phrase, which is determined by the frequency of use of the word, is input from the terminal i1. T1
And T2 are RAMs for realizing the tables table1 and table2 shown in FIGS. 3A and 3B, respectively. COMBI is the division point among phonetic symbol positions 1, 2, ..., N 0 = k (0) <k (1) <k (2) <... <k (m) = N, and the phrase determined by it Set B (k (0) + 1, k
(1)), B (k (1) +, k (2)), ..., B (k (m-
1) + 1, k (m)) each clause x
_{k (0) + 1, k (1), p (1)} , x _{k (1) + 1, k (2), p (2)} , ... x
It is a device that generates a combination that selects _{k (m-1) +1, k (m), p (m)} . SEL1 is a device for selecting only a specific clause specified by the combination generator COMBI from the buffer memory BUF. PE reads PEN (x for the clauses x ₁ , x ₂ , ..., xmx read from the buffer memory BUF via the selection device SEL1.
It is a device that calculates ₁ , x ₂ , ..., xm, x). INT is the selection device S
It is a device that detects the beginning of the phrase x read by EL1. SEL2 is a combination generator COMBI from memory T1
It is a device that selects only specific information specified by. SEL3 is a device for selecting a specific one from the information stored in the buffer memory SC based on the signal sent from the phrase start end detecting device INT. ADD1 is an adder that adds the output of the PEN calculation device PE and the numerical value read from the memory T1 by the selection device SEL2. MIN is a minimum value detector that detects the minimum value of the output of the adder ADD1 when the combination generator COMBI generates various combinations and the combination at that time. ADD2 is an adder that adds the output of the minimum value detector MIN and a specific numerical value in the buffer memory SC.

CONT is a control device for controlling the operation sequence of each of these parts, for example, in the form of a central processing unit CPU and 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. It has a memory MEM2. 01 and 02
Are output terminals for outputting the calculation results written in the memories T1 and T2, respectively.

2 (A) and 2 (B), 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 clause numbers for determining the optimum syntax on the table. This will be described below.

As shown in FIGS. 3A and 3B accompanying the flowcharts of FIGS. 2A and 2B, the number of rows and columns equal to the assumed bunsetsu column length N, and The original number NUM (i, j) of the phrase set B (i, j) at row i, column j
Two three-dimensional tables with terms equal to table1 (i,
j, q) and table2 (i, j, q) (1 ≤ i ≤ j ≤ N, 1 ≤ q ≤ N
UM (i, j)) is required. The subscripts in each table represent rows, columns, and terms in order from the left.

table1 (i, j, q) is the value of OPT (i, j; x _{i, i, q} ) and tabl
e2 (i, j, q) is for storing a set of optimum segment points and optimum clause numbers for i, j, x _{i, j, q} . Bun Set B
The original number NUM (i, j) of (i, j) is a two-dimensional table num (i,
j) is input and held. The certainty of the p-th clause x _{i, j, p} in the k-th clause set B (i, j) is the three-dimensional table score (i,
j, p) and is held. Also, PEN (x
_{k (0) + 1, k (1), p (1)} , x _{k (1) + 1, k (2), p (2)} , ..., x
_The function to calculate _{k (m-1) + 1, km, pm} , x _{i, j, q} ) is pen ((k (0) + 1, k (1), p (1)), k (1) +1 , k
(2), p (2)), ..., (k (m-1), k (m), p
(M)), (i, j, q)). The function that calculates INIT (x _{i, j, q} ) is init (i, 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 the j-th column.

In each of steps S2 to S11, the row number i of each table starts from j and is decreased by 1 to 1, and the following processing is executed for the i-th row.

In steps S3 to S9, the term number q of each table is incremented from 1 by 1 up to num (i, j), and the following processing is executed for the q-th term.

(1) In step S4, if it is determined that init (i, j, q) ≠ i, the process proceeds to step S5, where the next [F1] is executed, and then [F2] is executed in step S6. .

[F1] table1 (i, j, q): = min (1≤m≤min {init (i, j, q) -1, L} min (i
−1 = k (0) <k (1) <K (2) <... <k (m) =
init (i, j, q) -1) min (1≤p (1) ≤num (k
(0) + 1, k (1)), 1 ≦ p (2) ≦ mun (k (1) +1,
k (2)), ..., 1 ≦ p (m) ≦ num (k (m−1) + 1, k
(M)) [table1 (k (0) + 1, k (1), p (1)) + t
able1 (k (1) + 1, k (2), p (2)) + ... + table1
(K (m-1) + 1, k (m), p (m)) + pen ((k
(0) + 1, k (1), p (1)), (k (1) + 1, k
(2), p (2)), ..., (k (m-1) + 1, k (m), p
(M)), (i, j, q))] + score (i, j, q) [F2] table2 (i, j, q): = ([F1] gives the minimum value (k (1), p
(1)), (k (2), p (2)), ..., (k (m), p
(M)) (2) If init (i, j, q) = i is determined in step S4, the process proceeds to step S7, where the next [F3] is executed.

[F3] table1 (i, j, q): = score (i, j, q) The combination generating device COMBI shown in FIG. 1 generates the combination of the selection points and the segment points in [F2]. The minimum value detector MIN detects the minimum value of those combinations and the combination giving the minimum value. PEN calculator PE
The selection of the clauses required to calculate PEN at is done by the selector SEL1, table1 (k (0) + 1, k (1),
p (1)), table1 (k (1) + 1, k (2), p (2)),
.., table1 (k (m-1) + 1, k (m), p (m)) is read by the selector SEL2. init (i, j,
The calculation of q) and the determination as to whether it is equal to i or not are performed by the clause start end detecting device IN. Also, table num is buffer B
Memorized in part of UF. Through the above processing, the above calculation is performed on each row, column, and term of table1 and table2, and the results are sequentially written into table1 and table2.

When j> N in step S13, the calculation ends, and OPT (1, N, x _{1, N, q} ) and (1 ≦ q for table1 (i, N, q).
≦ NUM (1, N)) is stored. Also, since the information of the optimum segment point and the optimum clause number is stored in table2,
(4) By the method described in (e), the optimum clause sequence and the optimum syntax can be constructed from this information.

When the present invention is actually used, in addition to the apparatus shown in FIG. 1 and the flow charts shown in FIGS. 2A and 2B, an optimum phrase sequence and an optimum syntax on it are constructed from the information in table2. However, the main point of the present invention is
The contents of table1 and table2 are calculated, and the mechanism of constructing the optimal clause sequence and the optimal syntax on it 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 sequence of phrases and the optimal syntax above it from a given set of phrases is now complete.

The pair of numerical values ((k
(1), p (1)), ((k (2), p (2)), ..., (k
(M), p (m))) may exist, in that case, it is possible to store a plurality of sets of numerical values in table2 (i, j, q), and in [F2] All of them
It should be stored in table2 (i, j, q). Thus, even if the flowcharts of FIGS. 2A and 2B are changed, the calculation amount is almost unchanged.

In the above-described embodiment, the case of the process of obtaining the minimum value is shown. However, the smaller the value of S (x), the higher the certainty of the clause x, and the smaller the value of PEN, the degree of dependency matching. Because it is high. If the larger the value of S (x) is, the higher the certainty is, and the larger the value of PEN is, the higher the matching degree of the dependency is, the process of obtaining the maximum value instead of the minimum value may be performed.

[Effects of the Invention] As described above, according to the present invention, the last clause within the range of the subsequence i, i + 1, ..., j of the given character string positions 1, 2 ,. The optimum phrase sequence when fixed, the optimum syntax above it, and its eligibility are obtained sequentially from the ones corresponding to the subsequences with short lengths and stored, and rather than including those subsequences. By utilizing them when calculating similar ones for long subsequences, the desired result can be efficiently obtained without repeating the same calculation.

Consistency PEN (x ₁ , x ₂ , ..., xm, x) that a plurality of phrases x ₁ , x ₂ , ..., xm are related to a certain phrase x at the same time is attribute of words forming each phrase. Or describe statistical information such as the frequency of dependency appearing in the actual sentence in advance in the irregular letter,
It can be calculated based on it. Although the amount of calculation varies depending on the construction method of the language dictionary and the like, as one guide, the number of times of addition and comparison operations in the calculation method and enumeration method of the present invention are evaluated in the following cases. It should be noted that m-1 number of addition operations are required to obtain the sum of the m numbers, and m− is required to obtain the minimum value of the m numbers.
It is assumed that one comparison operation is necessary.

(1) In order to calculate PEN (x, y), the calculation amount for J additions is required.

(2) To calculate PEN (x ₁ , x ₂ , ..., xm, x),
(X ₁ , x) + PEN (x ₂ , x) + ... + PEN (xm, x) The same amount of calculation, that is, addition (J + 1) · m-1
It requires a lot of calculation.

Further, it is assumed that the original numbers of the clause set B (i, j) are all equal to M. Then, the parameters that determine the size of the problem to be solved are as follows.

M: Original number of each bunsetsu set B (i, j) N: Character string length L: Upper limit of the number of bunsetsus that can be related to one bunsetsu at the same time J: Addition conversion of the degree of dependency matching between two bunsetsus Under the assumption that the value is higher than the value, the calculation amount is

(A) The function F (n, k) of the present invention is expressed as F (n, k) = Σ (m ₁ + m ₂ + ..., mk = n, 1 ≦ mi ≦ n) [m ₁ · m
₂ … mk] and use this to express the number of additions and the number of comparisons.

(1) Add function to f (n) Is defined as (2) Compare function g (n) Is defined as (B) The enumeration knum (n, L) is defined as the number of bunsetsus that are simultaneously related to one bunsetsu and is L or less in the dependency structure on the bunsetsu string of length n, and _N-1 Cn is two. Assuming a term coefficient, the number of additions and the number of comparisons are expressed as follows.

(1) Addition Total number of additions = Σ (0 ≤ n ≤ N-1) [ _N-1 Cn · {knum
(N + 1, L) · (J + 1) · n + n} · Mn ^{+ 1} ] (2) Comparison Total number of comparisons = Σ (0 ≦ n ≦ N−1) [ _N-1 Cn · {knum
(N + 1, L) * Mn ^{+ 1} ] -1 knum (n, L) can be calculated using the following recurrence formula.

Tables 2 and 3 show the values obtained by calculating the total number of additions and the total number of comparisons for J = 1 and some M, N, L.

According to these tables the effect of the present invention are apparent, for example, the calculation amount when the M = 5, N = 20, L = 5 is reduced by a factor of about ¹⁰¹³ minutes enumeration methods.

[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 It is a table structure diagram which shows an example of the table required when performing the flowchart of FIG. SC: RAM for holding clause certainty, BUF: RAM for holding clause sets, T1: RAM for table1, T2: RAM for table2, SEL1 ... data selection device, SEL2 ... data selection device, SEL3 .. Data selection device, PE ... Dependency matching degree calculation device, COMBI ... Combination generator, INT ... Phrase start detection device, ADD1 ... Adder, ADD2 ... Adder, MIN ... Minimum value detector, CPU: Central processing unit, MEM1: ROM for control procedure storage, MEM2: RAM for CPU work, CONT: Control device for controlling the operation sequence of each part, i1 ... Phrase certainty input terminal, i2 ... Phrase Input terminal, o1 ... output terminal of the result obtained in the memory T1, o2 ... output terminal of the result obtained in the memory T2.

Claims (1)

[Claims] 1. A phonetic symbol position determined by a natural number from 1 to N, and a set of clauses whose phonetic notation start position and phonetic notation end position are at various positions within the range of 1 to N, and those. Given a numerical value that represents the certainty of a bunsetsu, minimizes or maximizes the sum of the numerical values that represent the degree of consistency of each bunsetsu with respect to another bunsetsu at the same time and the certainty of each bunsetsu. Under the optimum criterion, the phonetic transcription start position of the first phrase is equal to 1, the phonetic transcription end position of the last phrase is equal to N, and the phonetic transcription end position of a phrase other than the final phrase is 1 From among all the bunsetsu strings that can be arranged so that the value added with is equal to the phonetic transcription start position of the next bunsetsu, the optimum bunsetsu string, the optimum syntax of that bunsetsu string, and its eligibility In the language processing method that determines the degree Two-dimensional upper triangular matrix-shaped first and second tables having the same number of rows and columns as N are prepared, and each grid of the first table and the second table is represented by a phonetic transcription termination. The first table and the second table are three-dimensionalized by dividing into the number of clauses whose position is equal to its column number and whose phonetic notation start position is equal to or more than its line number. For the q-th bunsetsu in the bunsetsu set in which the notation start position is a natural number i or more and the phonetic notation end position is a natural number j, when the phonetic 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, and the phonetic transcription start position is a natural number i or more and the phonetic transcription end position is a natural number j. For the q-th phrase, if its phonetic notation start position is not equal to i, the phonetic Divide into several sections up to the number obtained by subtracting 1 from the phonetic transcription start position of the q-th phrase in the set of phrases whose start position is i or more and the phonetic transcription end position is equal to j. , The start position s, the end position t, and the p-th p in the clause set whose start position is s or more and whose end position is t
Corresponding to the clause, the calculated value is stored in the s-th row, the t-th column and the p-th term of the first table, and if the storage is done, the calculated first value is stored.
The values of the s-th row, the t-th column, and the p-th term of the table are added to all the sections of the above division, and this value is associated with the start position s and the end position t of each section of the division. , The p-th phrase in the phrase set whose phonetic transcription start position is s or more and whose phonetic transcription end position is t has the phonetic transcription start position i or more and the phonetic transcription end position is j. The degree of matching of the q-th phrase in the same phrase set at the same time, and the minimum value or the maximum value for the combination of the above-mentioned divisions and the above-mentioned clauses associated with each section of the division is calculated. , A value obtained by adding to the minimum or maximum value the certainty of the q-th phrase in the phrase set in which the phonetic transcription start position is i or more and the phonetic transcription end position is j. The division that is stored in the i-th row, j-th column, and q-th term of Table 1 and gives the minimum value or the maximum value A segment point and a set of clause numbers associated with each segment of the segment are stored in the i-th row, the j-th column, and the q-th term of the second table, and the first table and the second table are stored according to the above procedure. When the calculated values are stored in the first row and the Nth column of the first table and the second table, the calculated values are sequentially filled in with the calculated values. By obtaining the minimum value or the maximum value in each item in the 1st row and the Nth column, the final eligibility and the clause number of the final clause are obtained, and the optimal segmentation point necessary for constructing the optimal syntax is obtained. And the entire set of optimum phrase numbers is obtained in the second table.