JP2006209173A - Dependency structure analyzing apparatus and computer program - Google Patents

Abstract

To determine the dependency between clauses even during utterance so that it can be used for later processing.
A dependency structure analyzing device 42 analyzes a dependency structure of utterances 40 sequentially input, detects a node boundary of the utterance 40 based on local information of the utterance, A node determination processing unit 60 that outputs a node boundary unit composed of utterances between the node boundary and the immediately preceding node boundary, and a node boundary unit whose relationship destination is undetermined in response to the detection of the node boundary. Intersection dependency analysis processing unit 70 that outputs dependency destination information obtained by inter-node dependency estimation using inter-subordinate dependency probability model 38, and the dependency destination is undetermined in response to the output of dependency destination information Based on the history of the dependency destination information obtained for each node boundary unit, among the node boundary units for which the dependency destination is not yet determined, the interdependence dependency determination process for determining and outputting the dependency destination that satisfies a predetermined condition Part 72.
[Selection] Figure 2

Description

  The present invention relates to a dependency analysis technique between sentence components, and more particularly to a technique for dependency analysis simultaneously with its progress, such as simultaneous interpretation and subtitle generation, that is, an improvement of a progressive dependency analysis technique.

  In order to obtain appropriate results in simultaneous interpretation or automatic caption generation in movies or television broadcasts, speech is once converted into text information by voice recognition processing, etc., and dependency analysis is performed simultaneously with input of the speech recognition results. It is necessary to. Such a technique of performing dependency analysis simultaneously with input is referred to as progressive dependency analysis in this specification.

  Due to the above-described demand, several studies on gradual dependency analysis have been conducted. In such a conventional method, the input is divided in a certain language unit (for example, sentence, clause, etc.), and dependency analysis is repeatedly performed on the divided language unit based on some method. For example, Non-Patent Document 1 discloses a technique for performing dependency analysis gradually based on a probability context free grammar.

  On the other hand, for example in monologue, Non-Patent Document 2 discloses a technique for detecting dependency of a clause in a sentence and performing dependency analysis based on the clause boundary, focusing on the feature that a sentence is long and complicated in structure. Yes. In this method, dependency analysis is executed in two stages, a clause level and a sentence level. First, a sentence is divided into clauses by clause boundary analysis, and dependency analysis in each clause is identified by performing dependency analysis on each clause. Next, a dependency relationship across the node boundaries is determined, and the entire dependency structure is created.

On the other hand, Patent Document 1 discloses a node boundary detection method for detecting a node boundary during speech. The method described in Patent Document 1 basically assumes that when a specific pattern is detected locally in a morpheme string, a node boundary is assumed at a predetermined location related to the pattern. For this purpose, a rule in which the local pattern of the morpheme string and the position of the node boundary are expressed by a so-called regular expression is prepared in advance. At the time of detecting a node boundary, a unit between the detected node boundary and the node boundary detected immediately before can be sequentially output as an approximate node.
JP 2004-318300 A Yoshihide Kato, Shigeki Matsubara, Katsuhiko Toyama, Yasuyoshi Inagaki, “Progressive Parsing Based on Stochastic Context Free Grammar”, IEEJ Transactions, Vol. 122-C, no. 1, 2, 109-2119, December 2002 Masanobu Ohno, Shigeki Matsubara, Takehiko Maruyama, Hideki Sasaoka, Hideki Tanaka, Yasuyoshi Inagaki, "Efficiency of dependency analysis based on clause boundaries", IPS-162, pp. 213-220, 2004

  By the way, in the case of utterance data to which no sentence boundary is given, especially monologue data, there is no explicit sentence end indicator. Therefore, it is not easy to divide speech data into sentence units prior to dependency analysis. In such a situation, it is difficult to apply the method described in Non-Patent Document 1 described above. In addition, it is assumed that the method described in Non-Patent Document 2 is applied after input of the entire speech data. Therefore, this method cannot be used for progressive dependency analysis as it is.

  However, in the present age when economics and human exchange are internationalized, there is a great demand for technology for automatically converting the utterance content of one language into another language in real time and generating subtitles. Such processing requires technology that can perform dependency analysis with high accuracy in parallel with the progress of the utterance.

  Accordingly, an object of the present invention is to provide a dependency structure analyzing apparatus and a computer program therefor, which can determine dependency between clauses even during utterance and can be used for later processing.

  A dependency structure analyzing apparatus according to a first aspect of the present invention is a dependency structure analyzing apparatus that progressively analyzes a dependency structure of utterances that are sequentially input, and is a node boundary of utterances that are sequentially input. Is detected based on the local information of the utterance, and the node boundary is detected by the node boundary detecting means for outputting the node boundary unit consisting of the utterance between the relevant node boundary and the immediately preceding node boundary, and the node boundary detecting means detects the node boundary. In response to this, an inter-node dependency analysis means for applying a predetermined inter-cell dependency analysis method to a node boundary unit whose dependency point is undetermined, and outputting the obtained dependency information, In response to the output of the dependency destination information by the dependency dependency analysis means, a history of dependency destination information obtained by the inter-cell dependency analysis means for the node boundary unit whose dependency is undetermined is retained, and based on the history , Out of the node boundary unit whose relationship is not yet determined, And a internode dependency determination means for determines and outputs one of dependency destination that satisfies certain conditions.

  The node boundary detection means detects the node boundary of the input utterance, and outputs the node boundary unit consisting of the utterances between the node boundaries so far. When the node boundary is detected, the inter-node dependency analyzing means estimates the dependency for the node boundary unit whose dependency is not yet determined. The inter-node dependency determination means retains the history of the estimated dependency destination for the node boundary unit for which the dependency destination has not been determined, and determines the dependency destination of the node boundary unit that satisfies a predetermined condition based on the history. . The detection of the node boundary by the node boundary detecting means, the output of the node boundary unit, and the inter-node dependency analysis by the inter-node dependency analyzing means are sequentially performed. When a predetermined condition is satisfied according to the result of the inter-node dependency analysis, the inter-cell dependency determining means determines and outputs a corresponding inter-unit boundary unit. Since these processes are performed gradually in parallel with the input of the utterance, the dependency between the clauses can be determined not only in the sentence unit but also in the middle of the utterance and used for the subsequent process.

  Preferably, the dependency structure analyzing apparatus further includes a predetermined intra-section dependency analysis method for the nodal boundary unit output from the nodal boundary detecting means in response to the nodal boundary being detected by the nodal boundary detecting means. And inter-group dependency analysis means for storing the obtained intra-section dependency result, and the inter-node dependency determination means responds to the output of dependency destination information by the inter-node dependency analysis means. A history holding means for holding the history of the dependency destination information obtained by the inter-node dependency analysis means for the node boundary unit whose dependency destination is undetermined, and a relationship based on the history held by the history holding means Among clause boundary units whose destinations are not yet determined, a clause destination determination means for determining a destination of a clause that satisfies a predetermined condition, a dependency destination determined by the clause destination determination means, and the clause boundary unit Dependency in section Together with intranodal dependency results held in the analyzing means and means for outputting as a dependency relationship information for the clause boundary unit.

  The intra-clause dependency analysis means performs intra-clause dependency analysis on the node boundary unit and holds the result. When the inter-node dependency is determined for a certain node boundary unit, the dependency relationship is output together with the result of the intra-node dependency analysis for the node boundary unit. For utterances that are input sequentially, a dependency relationship with respect to each node boundary unit is obtained progressively for both within and between nodes. As a result, it is possible to determine the dependency within the clause and between the clauses even during the utterance instead of the sentence unit, and use it for later processing.

  More preferably, the history holding means responds to the output of the dependency destination information by the inter-node dependency analysis means, and the dependency destination information obtained by the inter-node dependency analysis means for the node boundary unit whose dependency is not yet determined. Including a means for holding a predetermined number of previous histories for each node boundary unit, and the node destination determination unit includes all the destination information held in the unit for holding a node boundary unit. In response to the coincidence, means for determining a destination of the certain node boundary unit as a last obtained by the inter-node dependency analyzing means is included.

  The inter-node dependency determining means further includes a predetermined value storage means for storing a predetermined natural number, and the means for holding is in response to the output of dependency destination information by the inter-node dependency analyzing means. In order to hold the history immediately before the dependency destination information obtained by the inter-node dependency analysis means for the undecided clause boundary unit, by the number of a predetermined natural number stored in the predetermined value storage means for each node boundary unit. These means may be included.

  The dependency structure analyzing apparatus may further include an input unit for inputting a predetermined natural number stored in the predetermined value storage unit.

  Preferably, the node destination determination means is the response destination information obtained by the node dependency analysis means for the node boundary unit whose dependency is not yet determined in response to the output of the dependency destination information by the internode dependency analysis means. And the determination means for determining whether or not the last relation information held in the means for holding the relevant section boundary unit matches, and the determination means continuously obtains the result of the match. In response to the counter means for counting the number of times for each of the node boundary units for which the relationship is undetermined, and the count result of a certain node boundary unit by the counter means reaching a predetermined value, And a means for determining a dependency point of the certain node boundary unit as a dependency point finally obtained by the inter-node dependency analysis means for the certain node boundary unit.

  The computer program according to the second aspect of the present invention, when executed by a computer, causes the computer to operate as any one of the dependency structure analyzing apparatuses described above. Therefore, the same operation and effect as the above-described dependency structure analyzing apparatus can be obtained.

[Section and dependency]
The embodiment of the present invention described below uses a gradual dependency analysis method of utterances with a section as a basic analysis unit. Therefore, the fact that the node boundary detection described in Patent Document 1 described above can detect the node boundary of the utterance in almost real time is utilized. Furthermore, every time a node boundary is detected and a node to be analyzed is determined, a dependency structure inside the node is created, and an attempt is made to determine the dependency of a node that has already been input. The determination of the clauses to which the clauses are related is executed at a dynamic timing in consideration of the likelihood of the dependency with some subsequent clauses.

  A clause is a group centered on a predicate. In the case of a compound sentence or a heavy sentence, a sentence is composed of a plurality of clauses. In addition, a clause is a syntactically and semantically unit. Therefore, clauses can be used as units that change into sentences. In the following embodiment, it is assumed that “a sentence is a concatenation of one or more clauses, and the clauses constituting each clause are related to the clauses inside the clause except the last clause of the clause”. Realized.

  FIG. 1 schematically shows a dependency structure analysis performed in the following embodiment. Referring to Figure 1, the sentence "The percentage of people who support the death penalty is nearly 80 percent according to a poll released by the Prime Minister the other day." It was made up of “I did it”, “According to public opinion polls”, “To support the death penalty”, and “Persons are nearly 80 percent”. Each section forms a dependency structure, and they are connected by a dependency structure from the last sentence of the section. In FIG. 1, the dependency in the node is indicated by a solid arrow, and the dependency between the nodes is indicated by a dotted arrow.

  In order to make a clause an analysis unit instead of a sentence, it is necessary to divide an utterance sentence into clauses as a preprocessing of dependency analysis. Since there are subordinate clauses embedded in the main clause, it is inherently difficult to divide the sentence into one-dimensional sections. Further, in the gradual processing, it is necessary to perform dependency analysis of the first half of the utterance before the end of the sentence is reached, and the sentence division is further difficult.

  However, by using the node boundary detection method described in Patent Document 1, the sentence can be approximately divided into nodes at the detected node boundary. In addition, in the method described in Patent Document 1, necessary information is a local pattern of a morpheme string obtained as a result of morphological analysis of an input sentence. Therefore, by applying this method to the progressive method, the internal dependency structure can be analyzed for each node. In the following description, a language unit sandwiched between detected clause boundaries is referred to as a “section boundary unit” and is considered as a new analysis unit. In the method described in Patent Document 1, the end position of a node boundary unit and the type of node boundary unit are specified using only a local morpheme string as a clue, and any one of 144 types of node labels is assigned to each node boundary unit. To do.

  In the following embodiment, after analyzing the dependency structure inside each clause boundary unit as described above, the dependency destination from the final clause of each clause boundary unit is further determined as follows. That is, each time a subsequent clause boundary unit is input, the dependency between clauses is repeatedly analyzed, and when a predetermined condition is satisfied, the destination of the final clause of each clause boundary unit is determined. In the following description of the embodiments, the node boundary unit is simply referred to as a node in order to simplify the description.

[Relationship between section and dependency structure]
In order to clarify the relationship between clauses and dependency structures, we analyzed the relationship between clauses and dependency structures using a monologue corpus. For the analysis, the Japanese Broadcasting Corporation (NHK) commentary program "Read Asu" transcription data 200 sentences, automatically morphological analysis, paragraph summarization, clause boundary analysis, and dependency analysis, the result The one that was manually corrected was used.

  Table 1 shows the basic statistics of these 200 sentences.

表１に示すように、総文節数２，４３０のうち、節の最終文節（９５１文節）を除いた１，４７９文節の中で、９４文節のみが節外に位置する文節に係っていた。これは、全体の９３．６％（１，３８５／１，４７９）の係り受けが節で閉じていることを意味している。従って、以下で説明する実施の形態での「文は一つ以上の節の連接であり、各節を構成する文節は、節の最終文節を除き、その節の内部の文節に係る」という仮定がある程度妥当であることを表している。

As shown in Table 1, out of 1,479 clauses excluding the last clause (951 clause) of the total number of clauses of 2,430, only 94 clauses were related to clauses located outside the clause. . This means that 93.6% (1,385 / 1,479) of the dependency is closed at the node. Therefore, in the embodiment described below, it is assumed that “a sentence is a concatenation of one or more clauses, and the clauses constituting each clause are related to the clauses inside the clause except the last clause of the clause”. Indicates that it is appropriate to some extent.

[First Embodiment]
−Configuration−
Hereinafter, the functional configuration of the dependency structure analyzing system 30 according to the first embodiment of the present invention will be described with reference to FIGS. Referring to FIG. 2, the dependency structure analysis system 30 includes an intra-node dependency probability model 36 that is a probability model related to intra-node dependency and an inter-node dependency probability model that is a probability model related to inter-node dependency. 38, a dependency structure analyzing device 42 for progressively analyzing the dependency structure for the input utterance 40 and sequentially outputting the dependency relationship 46 in units of nodes. The dependency structure analyzing device 42 is connected to an input / output device 44 operated by a user when inputting a predetermined value (N) used in internal processing, as will be described later.

  The intra-node dependency probability model 36 and the inter-node dependency probability model 38 use the learning data 32 to which information indicating the result of the dependency structure analysis performed in advance is used, and the dependency learning processing unit 34 according to an expression described later. Prepared by.

  The dependency structure analyzing apparatus 42 sequentially divides the utterance 40 into clauses by performing morphological analysis, sentence summarization, and node boundary detection processing described in Patent Document 1 for each utterance 40, and each time a clause is divided. The node determination processing unit 60 for outputting the clause, the utterance data temporary storage unit 62 used by the node determination processing unit 60 to temporarily store utterance data during the node determination processing, and the node determination processing unit 60 Each time a clause is output, the clause is received, the clause dependency analysis process is performed on the clause with reference to the clause dependency probability model 36, and the result is output together with the morpheme sequence of the clause. A dependency analysis processing unit 64 and an analysis result storage unit 66 for storing the dependency analysis result by the intra-node dependency analysis processing unit 64 together with the morpheme sequence of the nodes are included.

  The dependency structure analyzing device 42 further detects a node boundary by a predetermined number storage unit 68 for storing a predetermined value (N) input by an operator using the input / output device 44 and a node determination processing unit 60. In response to the fact that the clauses are output to the intra-section dependency analysis processing unit 64, the inter-node dependency analysis is performed on a clause that has been output before and whose final destination has not yet been determined. An inter-node dependency analysis processing unit 70 for performing processing using the inter-cell dependency probability model 38 is included.

  The dependency structure analyzing apparatus 42 further stores, as a history for each clause, information on the dependency destination obtained for the final sentence of each clause by the inter-node dependency analysis processing by the inter-node dependency analysis processing unit 70. Inter-node connection destination temporary storage unit 74, counter storage unit 76 for storing variables used as counters, intra-node analysis results stored in analysis result storage unit 66, inter-node connection destination temporary storage unit 74 The inter-node relationship history stored in the memory and the counter storage unit 76 are used, and the destination of the last clause of the clause remains constant for the number of times determined by the predetermined value stored in the predetermined-number storage unit 68. Is determined in response to the completion of the analysis by the inter-part dependency analysis processing unit 70, and the destination of the final clause of the relevant section is specified according to the result, Intersection dependency on clauses Receiving internode dependency for outputting a dependency relation 46 a relationship and a determination processing unit 72. In this embodiment, the inter-node dependency determination processing unit 72 stores the inter-cell dependency destination temporary storage unit 74 in order to compare with a new inter-node relationship destination at the next determination after the above determination. Stores information related to inter-node relationships.

  FIG. 3 shows a detailed configuration of the inter-node dependency analysis processing unit 70. Referring to FIG. 3, inter-node dependency analysis processing unit 70 detects a node from node determination processing unit 60 and outputs a node input signal. In response to the node input signal from the detection unit 90, the storage region for the newly input node is stored in the node connection temporary storage unit 74, and the counter region is stored in the counter storage unit 76. In response to the node input signals from the reception memory initialization unit 96 and the node input detection unit 90, the inter-node dependency probability model 38 for the dependency analysis results of each node stored in the analysis result storage unit 66. The inter-node dependency analysis processing using the clause is performed, and the clause final clause dependency destination analysis processing unit 92 for performing the processing for estimating the dependency destination of the final clause of each clause, and the section final clause dependency destination analysis processing unit 92 perform the estimation Depending on the destination of the last sentence of each section Te, and a dependency destination update processing unit 94 for updating the internodal dependency destination history of each section stored in the internode relates destination temporary storage unit 74.

  The details of the dependency analysis method will be described below among the processes of the above-described units.

-Sentence analysis based on clause boundaries-
In the dependency analysis in the present embodiment, a sentence subjected to morphological analysis, sentence grouping, and clause boundary analysis is input, and there are three types of dependency: backward modification of dependency, uniqueness of dependency, and non-crossing The property is an absolute constraint. The analysis procedure is as follows.

(1) Dependency analysis at the node level Analyze the dependency structure inside all the clauses in one sentence. This is a process executed by the intra-node dependency analysis processing unit 64 shown in FIG.

(2) Dependency analysis at the sentence level For all clauses in one sentence, analyze and estimate the destinations of the last sentence. This is a process executed by the inter-node dependency analysis processing unit 70 shown in FIG.

In the following, clauses constituting one sentence are C ₁ , C ₂ ,..., C _m , clause strings constituting clause C _i are b ₁ ⁱ ,..., B _ni ⁱ , and clause b _k ⁱ is a clause. The receiving relationship is represented by dep (b _k ⁱ ), and the dependency structure of one sentence is represented by {dep (b ₁ ¹ ),..., Dep (b _nm−1 ^m )}.

The dependency analysis section level dependency parsing node level, clause column b ₁ ⁱ in sections C _i, ..., when the b _ni ⁱ and B _i, P | relates to maximize (S _i B _i) The receiving structure Si (= {dep (b ₁ ⁱ ),..., Dep (b _ni-1 ⁱ )}) is obtained. However, the receiving clause of the final clause b _ni ⁱ (1 ≦ i ≦ m) of the clause is not determined.

  Assuming that the dependency relationships are independent of each other, P (Si | Bi) can be calculated by the following equation.

ここで、式（１）の右辺の各項は、入力文節列Ｂ_iが与えられたときに、文節ｂ_k ⁱがｂ_l ⁱに係る確率を表す。最尤の係り受け構造は、式（１）の確率を最大とする構造であるとして動的計画法を用いて計算する。

Here, each term on the right side of Equation (1) represents the probability that the phrase b _k ⁱ relates to b _l ⁱ when the input phrase string B _i is given. The maximum likelihood dependency structure is calculated by using dynamic programming, assuming that the maximum likelihood dependency structure is a structure that maximizes the probability of Equation (1).

Next, calculation of each term on the right side of Equation (1) will be described. The original form of the independent word in the dependency phrase is h _k ⁱ , its part of speech is t _k ⁱ , the type of the dependency is r _k ⁱ , the original form of the independent word in the reception phrase is h _l ⁱ , and its part of speech is t _l ⁱ . Also, e _l ⁱ indicates whether the received phrase is the last phrase in the section, and the distance between phrases is d _kl ⁱⁱ . Here, the type of relationship is the vocabulary, part of speech, or inflected form of the attached word when the related phrase accompanies the attached word, and the morphological part of speech or inflected form of the ending of the clause otherwise.

  Using the above attributes, the probability of forming each term on the right side of the probability formula (1) is calculated as follows.

ただしＦは共起頻度関数である。この計算は、図２に示す係り受け学習処理部３４が学習データ３２に基づいて行なう。

Where F is a co-occurrence frequency function. This calculation is performed based on the learning data 32 by the dependency learning processing unit 34 shown in FIG.

Sentence level dependency analysis In this process, the destination clause (receiving clause) of the final clause of the clause is identified. Dependent structure {dep (b _n1 ¹ ),..., Dep (b _nm-1 ^m-1 , where B (= B ₁ ... B _m ) is a sentence sequence of one sentence and the last phrase of the clause is a related phrase. )} when to the S _last, P (S _last | Request S _last to maximize B). P (S _last | B) can be calculated by the following equation.

ここで、式（３）の右辺の各項は、１文の文節ｂが与えられたときに、Ｃ_iの最終文節ｂ_ni ⁱがｂ_l ^jに係る確率を表し、式（２）と同様に計算する。この計算も、図２に示す係り受け学習処理部３４が学習データ３２に基づいて行なう。最尤の係り受け構造は、式（３）の確率を最大とする構造であるとして動的計画法を用いて計算する。

Here, each term on the right side of Equation (3) represents the probability that the final clause b _ni ⁱ of C _i is related to b _l ^j when one clause b is given, and is similar to Equation (2). To calculate. This calculation is also performed by the dependency learning processing unit 34 shown in FIG. The maximum likelihood dependency structure is calculated using a dynamic programming method as a structure that maximizes the probability of Expression (3).

  However, in the present embodiment, the receiving clause of the final clause of the clause is determined on the assumption of the dependency structure inside the clause analyzed earlier. That is, not all the clauses located behind are calculated as candidate phrases, but only those satisfying the non-intersection among the dependency candidates in the clause are taken as candidate phrases. In the case of the example shown in FIG. 1, the received clause of the phrase “I support” is calculated as being either “People” or “I am”.

Progressive Dependency Analysis As already described, the dependency structure analysis device 42 performs a gradual dependency analysis each time a node is detected by the node determination processing unit 60. That is, the node determination processing unit 60 determines node boundaries as needed for the input, and when a node is identified, dependency analysis is executed for the input up to that point.

  Regarding dependency analysis by the inter-node dependency analysis processing unit 70, it is not clear when the received clause can be determined. Therefore, the timing for determining it becomes a problem. In the present embodiment, as described above, the receiving clause is determined when the analysis of the subsequent clause progresses to some extent after the final clause of the clause is input. This focuses on the two facts that the dependency relationship between clauses does not cross sentences and that the distance does not become much longer.

  Specifically, whenever the clause boundary unit is input, the maximum likelihood dependency structure at that time is analyzed by the method described in the above-mentioned “sentence level dependency analysis”, and the relationship of the clause at that time is analyzed. The dependency relationship was analyzed, and the dependency relationship of the final clause of the clause did not change for a certain number of times of input (“predetermined value N” stored in the predetermined number storage unit 68) (this number is hereinafter referred to as “invariant number”). In this case, the received clause is determined as the destination of the final clause. In other words, the node destination is determined based on the history of the immediately previous destination destination estimation result.

The progressive dependency analysis algorithms this analysis, each time the node C _i is input, section C ₁ already entered, ..., each final clause of C _i b _ni ^i, ..., b relates for _ni ^j receiving structure D = {Dep (b _nj ^j ), k | 1 ≦ j ≦ i} is updated to determine the dependency between nodes. Here, k _represents the invariant number of dep (b _nj ^j ). The dependency analysis algorithm is shown below. The fixed value is a predetermined value N (N is a natural number).

(1) A node C _i whose internal dependency structure is determined is received.

  (2) Of the final clauses in the clause, for the clauses whose dependency destinations are not yet determined, the dependency relationship using the dependency clause as the dependency clause is obtained by the method described in the “sentence level dependency analysis”.

(3) Based on the dependency relationship dep (b _nj ^j ) generated in (2), the dependency relationship D for the final phrase is updated. Here, when dep (b _nj ^j ) is the same as the previous time, 1 is added to the invariant number, and when it is different, the invariant number is set to 1.

(4) With respect to the dependency relationship dep (b _nj ^j ) ∈D satisfying the invariant number = predetermined value N, dep (b _nj ^j ) is output assuming that the dependency destination of the clause b _nj ^j is determined.

(5) At the time when all the clauses are input, the dependency relationship dep (b _nj ^j ) is output for (dep (b _nj ^j ), k) εD where the invariant number <the predetermined value N.

In the present embodiment, the sentence ending is analyzed as having no dependency. Therefore, in the analysis at the end of the paragraph, no destination is included as a candidate. Specifically, in Equation (3), a clause without a relation is related to itself (that is, b _ni ⁱ = b _l ^j ), and the probability of having no relation is also calculated.

-Operation-
The dependency structure analysis system 30 according to the above embodiment operates as follows. There are two aspects to this operation. Referring to FIG. 2, the first aspect is an aspect of learning of the intra-node dependency probability model 36 and the inter-node dependency probability model 38 by the dependency learning processing unit 34. The second aspect is a progressive dependency analysis process by the dependency structure analysis device 42 using the intra-node dependency probability model 36 and the inter-node dependency probability model 38. The predetermined value N using the input / output device 44 is set by the operator at any time.

  In the first aspect, learning data 32 is first prepared. The learning data 32 is obtained by manually modifying the dependency analysis for a large number of sentences that have been subjected to the dependency analysis in advance by some method.

  The calculation method of the intra-node dependency probability model 36 and the inter-node dependency probability model 38 by the dependency learning processing unit 34 is performed according to the above-described calculation formula.

  If the linguistic resources such as the intra-clause dependency probability model 36 and the inter-node dependency probability model 38, and the dictionary used by the node determination processing unit 60 in the morphological analysis and the rules for detecting the node boundary can be prepared, the relationship to the utterance 40 will be described. Gradual dependency analysis by the receiving structure analysis device 42 becomes possible.

  First, the node determination processing unit 60 performs morphological analysis according to the method described in Patent Document 1 while accumulating the utterances 40 sequentially input in the utterance data temporary storage unit 62. The node determination processing unit 60 further detects node boundaries sequentially by applying a rule for node boundary detection to the morpheme string obtained by this processing. When detecting the node boundary, the node determination processing unit 60 gives the node including the morpheme sequence between the previous node boundary to the intra-node dependency analysis processing unit 64. At this time, a node identifier (hereinafter referred to as “node ID”) is assigned to the node. In subsequent processing, each section is distinguished by this section ID. As the node ID, a serial number starting from 1 is used in the present embodiment, but any method may be used as long as the node can be distinguished.

  When the intra-node dependency analysis processing unit 64 shown in FIG. 2 receives a node from the node determination processing unit 60, the intra-node dependency analysis processing unit 64 uses the intra-node dependency probability model 36 to perform dependency analysis between the clauses excluding the last clause in the clause. And the result is stored in the analysis result storage unit 66.

  Referring to FIG. 3, when a node is input from node determination processing unit 60, node input detection unit 90 of inter-node dependency analysis processing unit 70 converts the node input signal into inter-node dependency storage initialization unit 96 and This is given to the clause final sentence dependency destination analysis processing unit 92. The clause input detection unit 90 also supplies the morpheme sequence that constitutes the clause to the clause final clause relation destination analysis processing unit 92.

  The inter-node dependency memory initialization unit 96 secures and initializes a storage area for a new node in the inter-node dependency destination temporary storage unit 74 in response to the node input signal. The inter-node dependency storage initialization unit 96 also reserves a counter area for a new node in the counter storage unit 76 and initializes its value to zero.

  On the other hand, when the clause input signal and the morpheme sequence of the clause are given from the clause input detection unit 90, the clause final clause assignment destination analysis processing unit 92 is stored in the analysis result storage unit 66 and has been input so far. Using the intra-node analysis result and the inter-node dependency probability model 38, the destination of the last clause of the clause whose destination is not yet determined is estimated by maximum likelihood estimation. The clause final sentence dependency destination analysis processing unit 92 gives the result to the dependency destination update processing unit 94. The dependency destination update processing unit 94 stores the result in a storage area corresponding to the node in the inter-node relationship destination temporary storage unit 74. When the processing by the clause final sentence dependency destination analysis processing unit 92 is completed for all of the clauses for which the dependency destination has not yet been determined, the dependency destination update processing unit 94 performs all processing for the inter-node dependency determination processing unit 72. Notify that the estimation of the relation destination has been completed for the section in (1).

  In response to this notification, the inter-node dependency determination processing unit 72 executes the following processing. In other words, the inter-node dependency determination processing unit 72 stores the information on the dependency destination stored by itself for the node for which the dependency destination has not been determined, and the same clause stored in the inter-node dependency destination temporary storage unit 74. It is determined whether or not the information on the relationship is related. If they do not match, the inter-node dependency determination processing unit 72 sets the value of the counter corresponding to the relevant node in the counter storage unit 76 to 1 and the relationship stored in the inter-node relationship temporary storage unit 74 Store previous information. If the two match, the inter-node dependency determination processing unit 72 adds 1 to the value of the counter corresponding to the relevant node in the counter storage unit 76. In this case, the inter-node dependency determination processing unit 72 further determines whether or not the value of the addition result counter matches the predetermined value N stored in the predetermined number storage unit 68. If the two match, the inter-node dependency determination processing unit 72 determines an inter-relationship destination related to the node as the inter-relationship destination temporary storage unit 74, and the analysis result storage unit for the relevant node. Together with the intra-section dependency analysis result stored in 66, the dependency relationship 46 of that section is output. If the counter value does not match the predetermined value N (that is, less than N), the inter-node dependency determination processing unit 72 starts processing for the next clause.

  In this way, the inter-node dependency determination processing unit 72 repeats this process for all the nodes for which the dependency destination is not yet determined.

  The dependency structure analyzing apparatus 42 repeatedly executes the above-described processing on the entire utterance 40. As a result, the dependency relationship 46 of the node whose dependency destination is determined based on the history is sequentially output from the dependency structure analyzing device 42.

  If the predetermined termination condition is satisfied, the inter-node dependency determination processing unit 72 includes the intra-node dependency analysis results stored in the analysis result storage unit 66 for all the nodes for which the dependency destinations have not been determined. The estimation results of the connection destination immediately before the node stored in the inter-node connection destination temporary storage unit 74 are collected and output as a dependency relationship 46 for each node.

  Thus, the intra-section dependency analysis result and the inter-node dependency analysis result are obtained for all the nodes constituting the utterance 40. The inter-node dependency analysis results are sequentially determined together with the input of the utterance 40, so that even during the utterance, processing such as machine translation or subtitle generation using the dependency analysis result for the utterance can be appropriately performed. Although the inter-node dependency analysis result output at the end does not satisfy the determination condition, it is estimated by the maximum likelihood estimation by the inter-cell dependency analysis processing unit 70, so that a certain accuracy can be expected. .

-Realization by computer-
Software Configuration Each block shown in FIGS. 2 and 3 can be realized by computer hardware and software executed by the computer, that is, a computer program (hereinafter simply referred to as “program”). 4 and 5 show a flowchart of a program for realizing the processing by the inter-node dependency analysis processing unit 70 and the inter-cell dependency determination processing unit 72 among these blocks.

  Referring to FIG. 4, when this program is started, first, at step 110, initial setting is performed. In this initial setting, a predetermined value (predetermined value N stored in the predetermined number storage unit 68 shown in FIG. 2) previously set in the memory is read from the memory, a storage area used for work is initialized, A variable M indicating the number of nodes being processed is set to an initial value 0.

  In step 112, in response to the detection of the node boundary by the program that implements the node determination processing unit 60, the node sandwiched between the detected node boundary and the immediately preceding node boundary is read from the memory. .

  In step 114, a section ID for identifying this new section is assigned, and an area for temporarily storing the inter-node relation destination of this section (the sub-section destination of this section) and the inter-section relation destination of this section are: A counter area for counting how many times the same value is repeated for the dependency destination estimation (this number is hereinafter referred to as “continuation number”), and the internode relationship temporary storage unit 74 and the counter, respectively. Processing to be secured in the storage unit 76 is performed. In step 114, 1 is further added to the variable M representing the number of nodes being processed.

  In step 116, the dependency structure between nodes is analyzed for each node being processed. As a result, for each section being processed, the destination of the final phrase is estimated in consideration of the new section input in step 112. This process is performed using the inter-node dependency probability model 38 shown in FIG. The estimation result is stored in the inter-node connection destination temporary storage unit 74. In step 114, a correspondence relationship with the node ID of each node is given to the area in the internode connection destination temporary storage unit 74. Therefore, it can be determined by the clause ID in which area in the inter-node relationship temporary storage unit 74 the result is stored.

  In step 118, the continuation number of the last phrase is updated for all sections being processed. In the present embodiment, the continuation number is represented by C (J) (J = 1 to M). That is, in step 118, if the newly estimated destination for the last phrase of a section (referred to as the J-th section) in step 116 is the same as that previously estimated, the number of continuations of the section. 1 is added to C (J). When the newly estimated destination for this section is different from that previously estimated, 1 is set as the continuation number C (J) of the section. Details of the processing in step 118 will be described later with reference to FIG. It should be noted that each counter area for storing the number of continuations is also given a corresponding relationship with the node ID in step 114. Which counter should be incremented can be determined by the section ID of the section being processed.

  In step 120, it is determined whether or not there is a clause in which the continuation number C (J) is equal to or greater than a predetermined value N stored in the predetermined number storage unit 68 as a result of the continuation number update process in step 118. It is. If there is no such clause, control proceeds to step 126. If so, go to Step 122.

  In step 122, it is determined that not only the intra-section dependency but also the inter-node dependency has been confirmed for all the nodes whose continuation number is equal to or greater than the predetermined value N, and the node related to the relevant clause stored in the analysis result storage unit 66 is determined. The inner dependency and the inter-node dependency estimated for the relevant node in step 116 are collected and output as the dependency relationship of the node.

  In step 124, the storage area and the counter area secured in step 114 are released for the node for which the dependency relationship is output in step 122. Further, the variable M is subtracted by the number of clauses for which the dependency relationship is output.

  Thereafter, in step 126, it is determined whether or not the input of utterance data has been completed. This determination is performed, for example, by determining whether a predetermined time has passed without input or by detecting an end instruction from the operator. Control proceeds to step 128 if the input has been completed, and returns to step 112 otherwise.

  In step 128, the inter-node dependency relationship stored in the analysis result storage unit 66 and the inter-cell dependency destination temporary storage unit 74 are estimated for all of the undefined clauses regarding the inter-node dependency relationship. The inter-node dependency relationship is collected and output as the dependency relationship of each clause. When this process ends, the execution of this program also ends.

  FIG. 5 shows a more detailed flowchart of a program for realizing the processing executed in step 118 of FIG. In this process, for all the nodes being processed, the last clause dependency is estimated with reference to the inter-node dependency probability model 38 shown in FIG. 1, and the result and the previous iteration were obtained. This is a process for comparing the estimation result and updating the number of continuations of the relevant section.

  Referring to FIG. 5, first, at step 140, 0 is substituted for repeated control variable J. This variable J represents the order of the nodes to be processed.

  In step 142, 1 is added to the variable J. In step 144, it is determined whether or not the variable J exceeds the variable M representing the number of nodes being processed. If it exceeds, the process is terminated. If variable J is less than or equal to variable M, control proceeds to step 146.

  In step 146, it is determined whether or not the inter-node connection destination estimated for the J-th node is the same as the inter-node connection destination estimated in the previous iteration. In the configuration shown in FIG. 2, this determination is performed once for the same clause stored in the inter-node dependency determination processing unit 72 by the inter-node dependency destination stored in the inter-node dependency destination temporary storage unit 74. This is done by checking whether or not it matches the inter-node relationship estimated in the previous iteration. Control proceeds to step 148 if there is a match, otherwise to step 150.

  In step 148, 1 is added to the continuation number C (J) for the J-th clause. Thereafter, the control returns to step 142.

  On the other hand, in step 150, 1 is set to the continuation number C (J) for the J-th clause. Subsequently, at step 152, the final clause of the current J-th clause is read from the inter-node dependency destination temporary storage unit 74 and stored in the storage unit within the inter-cell dependency determination processing unit 72. Thereafter, control returns to step 142.

Hardware Configuration The dependency structure analyzing apparatus 42 according to the above-described embodiment can be realized by a computer system. FIG. 6 is an external view showing the overall configuration of a computer system 250 that implements the dependency structure analyzing apparatus 42 according to the above-described embodiment. Referring to FIG. 6, a computer system 250 includes a pair of a microphone 264 and a speaker 278, and a computer 260 having a CD-ROM (Compact Disc Read-Only Memory) drive 270 and an FD (Flexible Disk) drive 272. A monitor 262 connected to the computer 260, a keyboard 266, and a mouse 268 are included.

  The microphone 264 and the speaker 278 are used for inputting a speech for speech translation and outputting a translation result, if necessary, and do not constitute a part of the present invention. Accordingly, the details of the portion of the system relating to the microphone 264 and speaker 278 will not be described here.

  FIG. 7 is a hardware block diagram of the computer 260. Referring to FIG. 7, a computer 260 includes a CPU (Central Processing Unit) 340, a bus 342 connected to the CPU 340, a read only memory (ROM) 344 connected to the bus 342, and a bus 342. A CD-ROM drive 270 that is loaded with a random access memory (RAM) 346 connected to the CD-ROM, a hard disk 348 connected to the bus 342, and a CD-ROM (compact disk ROM) 360, and reads data from the CD-ROM. FD (flexible disk) 362 is mounted, FD drive 272 that reads data from FD and writes data, sound board 350 to which microphone 264 and speaker 278 are connected, and local area network connected to bus 342 War And a network board 352 that provides a function of connecting to a data communication network such as a LAN (LAN).

  As described above, the dependency structure analyzing apparatus 42 according to the embodiment described with reference to FIGS. 2 to 5 includes the hardware of the computer system 250, the program executed thereon, and the hard disk 348 of the computer system 250. This can be realized by data such as an intra-node dependency probability model 36, an inter-node dependency probability model 38, and a rule collection and dictionary for the node determination processing unit 60 stored in the RAM 346 or the like.

  A program for causing the computer system 250 to operate as the dependency structure analyzing apparatus 42 is stored in the CD-ROM 360 or FD 362 inserted in the CD-ROM drive 270 or the FD drive 272 and further transferred to the hard disk 348. . Alternatively, the program may be transmitted to the computer 260 through a network (not shown) and stored in the hard disk 348. The program is loaded into the RAM 346 when executed. The program may be loaded directly into the RAM 346 from the CD-ROM 360, from the FD 362, or via a network.

  This program includes a plurality of instructions for causing the computer 250 to operate as the dependency structure analyzing apparatus 42 of this embodiment. Some of the basic functions necessary to perform this operation are provided by operating system (OS) or third party programs running on the computer 250 or modules of various toolkits installed on the computer 250. Therefore, this program does not necessarily include all functions necessary to realize the system and method of this embodiment. This program calls only an instruction for executing the above-described operation as the dependency structure analyzing apparatus 42 by calling an appropriate function or “tool” in a controlled manner so as to obtain a desired result. It only has to be included. The operating principle of computer system 250 is well known and will not be repeated here.

[Example of analysis]
In the following, according to this embodiment, the state of analyzing the destination of the final sentence of each section of the utterance `` It is said that it is impossible to claim surrender even if the contract period expires unless there is a valid reason '' This will be described with reference to FIGS. 8 to 13 each show a dependency structure at the top and a dependency structure at the end of the last sentence of the section at the bottom. That is, ^{_{(dep (b nj j),}} k) ∈D of dep (b _nj ^j) is dependent bunsetsu and receiving clauses, k is unchanged number, corresponding respectively. Here, the description will be made assuming that the predetermined value N = 3.

  FIG. 8 shows a state when the first section “unless there is a valid reason” is input.

  FIG. 9 shows a state where the second section “contract period has expired” is input and the dependency structure {dep (limited)} is analyzed. Dep (limited) corresponds to the dotted arrow in the upper center of FIG. 9, and it is shown in the lower part of FIG. 9 that the destination of “limited” is “broken” and the invariant number is 1.

  Similarly, FIG. 10 and FIG. 11 show the maximum likelihood dependency structure {dep (limited), dep when the third section "I can't claim" and the fourth section "I can't claim surrender", respectively. (Broken)}, {dep (limited), dep (broken), dep (cannot be charged)} indicate states estimated by analysis.

  In FIG. 12, the node “when it is at a point” is newly input, and the maximum likelihood structure {dep (limited), dep (cut), dep (even), dep (cannot be charged)} is obtained. Indicates the state. At this time, as shown in the lower part of FIG. 12, the invariant number of the dependency relationship dep (broken) reaches a predetermined value 3. Therefore, it is determined that the destination of the clause “contract period has expired” is “even”, and the dependency relationship of this clause (including within and between clauses) is output.

  In FIG. 13, a new clause “I am called” is input, and the maximum likelihood dependency structure {dep (limited), dep (broken)}, {dep (limited), dep (broken), dep (all Even if) dep (if any)} is obtained. In the same manner as in FIG. 12, for the clauses “when there is no legitimate reason” where the number of invariants has reached the predetermined value 3 and “even if”, the destination of the clause is determined and dependency information is output.

[Analysis experiment]
In order to evaluate the effectiveness of the technique employed in the above embodiment, an analysis experiment was performed.

-Outline of the experiment-
In the experiment, NHK's commentary program “Read Asu” (length per program is about 10 minutes) was used. A summary of the data used is shown in Table 2.

テストデータとして、書起こしデータ（非特許文献２参照）に形態素解析、文節まとめ上げを施した７番組（４７０文）を用いた。節境界、及び、係り受けの正解は人手で作成した。一方、学習データとしては、形態素、文節まとめ上げ、節境界、係り受けに関する情報が与えられた９５番組(５，５３２文)を用いた。

As test data, seven programs (470 sentences) in which transcription data (see Non-Patent Document 2) was subjected to morphological analysis and sentence grouping were used. The node boundaries and the correct answers for the dependency were created manually. On the other hand, as learning data, 95 programs (5,532 sentences) to which information on morphemes, sentence grouping, clause boundaries, and dependency are given were used.

  Analysis was performed using these data, and the dependency correct answer rate and the analysis time were obtained. The analysis system was implemented as a GNU CommonLISP program, and was executed on a computer having a high-performance CPU with a clock frequency of 2.40 GHz and a memory capacity of 2 GB and running an open source operating system. In this experiment, the predetermined value N was changed from 1 to 12 in increments of 1, and a total of 12 experiments were performed.

-Experimental results-
Table 3 shows the dependency correct answer rate corresponding to each predetermined value N.

表３の中央の列は、番組末を除く全ての節境界単位末に対する正解率を、最右列は、番組末を除く全ての文節に対する正解率を、それぞれ示す。所定値Ｎが２のとき及び３のときに、節境界単位末に対する正解率が最も高く、そのとき、全体の正解率は７６．２％となった。なお、節末を除く節内に対する解析の正解率は８７．５％であった。

The middle column of Table 3 shows the correct answer rate for all clause boundary unit ends except the program end, and the rightmost column shows the correct answer rate for all phrases except the program end. When the predetermined value N was 2 and 3, the accuracy rate with respect to the end of the node boundary unit was the highest, and at that time, the overall accuracy rate was 76.2%. The accuracy rate of analysis for the inside of the node excluding the end of the node was 87.5%.

  Table 4 shows the result of evaluating the node boundary analysis accuracy of the node boundary detection program CBAP (similar to that described in Patent Document 1) used in the present embodiment by ignoring the label and only the position of the node boundary. Show. As is apparent from Table 4, according to the present embodiment, both the relevance rate and the recall rate are high, and there is not much influence on the analysis performed later.

  The relationship between the predetermined value N and the analysis time is shown in FIG. Referring to FIG. 14, the analysis time increases as the predetermined value N is increased. The analysis time was the shortest when the predetermined value N = 3, which was 12.5 seconds for all 7 programs and 1.8 seconds per program. This analysis time includes the time of node boundary analysis by CBAP. The average analysis time for node boundary analysis is about 0.3 seconds per program.

  In this method, analysis is performed assuming that there is no dependency at the end of the sentence. That is, the clause determined to have no relation is regarded as the end of the sentence. From this point of view, the end-of-sentence judgment performance of this method was evaluated. Table 5 shows the precision, recall, and F value of the sentence end determination.

表５を参照して、所定値Ｎ＝３のときに最も高いＦ値を示した。独話の文境界判定手法は既にいくつか提案されているが、本手法では漸進的係り受け解析と同時的に文末を判定できるという特徴がある。

Referring to Table 5, the highest F value was shown when the predetermined value N = 3. Several methods have already been proposed for determining the sentence boundaries of monologues, but this method is characterized by the ability to determine the end of a sentence simultaneously with progressive dependency analysis.

  From the above results, in this experiment, when the predetermined value N is 3, the highest performance is shown, and the conventional dependency analysis method using the sentence unit as an input (the accuracy rate is 79.0%, the processing time is 1). Compared with (approximately 2.1 seconds per program) (Non-Patent Document 2), the same analysis accuracy and analysis time are achieved.

[Modification]
In the system according to the first embodiment described above, a counter is used for counting the number of invariants during the analysis of inter-node dependency, and the result of the previous inter-cell dependency analysis is shown in FIG. This is held in the section 72 as a history. However, the present invention is not limited to such an embodiment. For example, the inter-node temporary storage unit 74 is a two-dimensional table, and the history of inter-cell dependency analysis results is stored for each node being processed by a predetermined value N stored in a predetermined number of storage units 68. You may make it do. In this case, when all the N analysis results in the history are equal, it is determined that the dependency relationship of the section is determined.

  Further, in the above-described embodiment, the inter-node dependency determination processing unit 72 shown in FIG. 2 uses the predetermined value N stored in the predetermined number storage unit 68 as a condition when determining the inter-cell dependency. The predetermined value N can be set by the input / output device 44. However, when carrying out the present invention, it is not necessary to make the predetermined value variable in this way. For example, a certain number may be set as a predetermined value, and the inter-node dependency determination processing unit 72 may use the number fixedly. From the results of the experiment described above, it is considered appropriate to set N = 3 in this case, but other values may be adopted. Also, this value may change depending on the content of the utterance to be processed.

  Furthermore, in the above-described embodiment, the intra-node dependency analysis processing unit 64 and the inter-node dependency analysis processing unit 70 both perform dependency analysis according to a probability model. However, the present invention is not limited to such. For example, one that performs dependency analysis by grammatical analysis, one that performs dependency analysis according to a previously prepared rule for dependency analysis, and the like can also be used.

  The embodiment disclosed herein is merely an example, and the present invention is not limited to the above-described embodiment. The scope of the present invention is indicated by each claim in the claims after taking into account the description of the detailed description of the invention, and all modifications within the meaning and scope equivalent to the wording described therein are intended. Including.

It is a figure which shows typically the dependency structure analysis performed by one embodiment of this invention. It is a block diagram which shows the structure of the dependency structure analysis apparatus 42 which concerns on one embodiment of this invention. It is a more detailed block diagram of the inter-node dependency analysis processing unit 70 shown in FIG. It is a flowchart of the program for implement | achieving the inter-node dependency analysis process part 70 and the inter-node dependency determination process part 72 shown in FIG. It is a detailed flowchart of a continuation number update process. It is a front view of the computer system which implement | achieves the dependency structure analysis apparatus 42 which concerns on one embodiment of this invention. It is a block diagram which shows the hardware constitutions of the computer shown in FIG. It is a schematic diagram which illustrates a mode that the destination of the last clause of each clause of an utterance example is analyzed. It is a schematic diagram which illustrates a mode that the destination of the last clause of each clause of an utterance example is analyzed. It is a schematic diagram which illustrates a mode that the destination of the last clause of each clause of an utterance example is analyzed. It is a schematic diagram which illustrates a mode that the destination of the last clause of each clause of an utterance example is analyzed. It is a schematic diagram which illustrates a mode that the destination of the last clause of each clause of an utterance example is analyzed. It is a schematic diagram which illustrates a mode that the destination of the last clause of each clause of an utterance example is analyzed. It is a graph which shows the relationship between the predetermined value N and analysis time in the experiment conducted using one Embodiment of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 30 Dependency structure analysis system 32 Learning data 34 Dependency learning processing part 36 Intersection dependency probability model 38 Internode dependency probability model 40 Utterance 42 Dependency structure analyzer 44 Input / output device 46 Dependency relation 60 Clause determination processing part 62 utterance data temporary storage unit 64 intra-node dependency analysis processing unit 66 analysis result storage unit 68 predetermined number storage unit 70 inter-node dependency analysis processing unit 72 inter-node dependency determination processing unit 74 inter-node dependency temporary storage unit 76 counter Storage section 90 Section input detection section 92 Section final sentence dependency destination analysis processing section 94 Relationship update processing section 96 Intersection dependency storage initialization section

Claims (7)

A dependency structure analysis device that progressively analyzes the dependency structure of utterances that are sequentially input,
A node boundary detecting means for detecting a node boundary of the utterance sequentially input based on local information of the utterance, and outputting a node boundary unit consisting of an utterance between the node boundary and the immediately preceding node boundary;
In response to detection of a node boundary by the node boundary detection means, a predetermined inter-node dependency analysis method is applied to a node boundary unit whose dependency is undetermined, and the obtained dependency destination information is output. Inter-node dependency analysis means,
In response to the output of the dependency destination information by the inter-node dependency analysis means, a history of dependency destination information obtained by the inter-node dependency analysis means for a node boundary unit whose dependency is not yet determined is retained, and the history And a dependency structure determining unit for determining and outputting a dependency point that satisfies a predetermined condition among the node boundary units for which the dependency point has not yet been determined. In response to detection of a node boundary by the node boundary detection unit, a predetermined intra-node dependency analysis method is applied to the node boundary unit output from the node boundary detection unit, and Further includes an intra-section dependency analysis means for storing the dependency results;
The inter-node dependency determining means is:
A history for holding a history of dependency information obtained by the inter-cell dependency analysis unit for a node boundary unit whose dependency is not yet determined in response to the output of dependency information by the inter-cell dependency analysis unit Holding means;
Based on the history held by the history holding means, among the node boundary units for which the dependency destination is undetermined, a relationship destination determining means for determining an engagement destination that satisfies a predetermined condition;
Dependency relationship information for the node boundary unit is determined by combining the dependency point determined by the node dependency destination determination unit and the intra-node dependency analysis result held in the intra-node dependency analysis unit for the node boundary unit. The dependency structure analyzing apparatus according to claim 1, further comprising means for outputting. In response to the output of dependency destination information by the inter-node dependency analysis unit, the history holding unit immediately before the dependency destination information obtained by the inter-cell dependency analysis unit for a node boundary unit whose dependency is not yet determined. Means for holding a predetermined number of histories for each clause boundary unit,
The node destination determination means responds to the fact that all the destination information held in the means for holding a certain node boundary unit matches, and determines the destination of the node boundary unit. 3. The dependency structure analyzing apparatus according to claim 2, further comprising means for determining a last obtained dependency by the inter-node dependency analysis means. The inter-node dependency determining means further includes a predetermined value storage means for storing a predetermined natural number,
The means for holding the dependency destination information obtained by the inter-node dependency analysis means for a node boundary unit whose dependency destination is undetermined in response to the output of the dependency destination information by the inter-node dependency analysis means. 4. The dependency structure analyzing apparatus according to claim 3, further comprising means for holding the history immediately before the number of the predetermined natural number stored in the predetermined value storage means for each node boundary unit. 5. The dependency structure analyzing apparatus according to claim 4, further comprising input means for inputting the predetermined natural number stored in the predetermined value storage means. The section destination determination means is
In response to the output of the dependency destination information by the inter-node dependency analysis means, the dependency destination information obtained by the inter-node dependency analysis means for the node boundary unit whose dependency is undetermined, and the above-mentioned node boundary unit A determination means for determining whether or not the last-mentioned dependency destination information held in the means for holding matches;
Counter means for counting the number of times that the result of matching is continuously obtained by the judging means for each of the node boundary units for which the relationship is undetermined;
In response to the count result of a certain node boundary unit reaching a predetermined value by the counter means, the dependency of the certain node boundary unit is changed to the inter-node dependency analysis means for the certain node boundary unit. 4. The dependency structure analyzing apparatus according to claim 3, further comprising means for determining the last obtained dependency point. A computer program that, when executed by a computer, causes the computer to operate as the dependency structure analyzing apparatus according to any one of claims 1 to 6.

Images