JP4956503B2 - Graph integration apparatus and program thereof - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a graph integration device with a simple structure, capable of treating a plurality of integration graphs with less operational quantity. <P>SOLUTION: The graph integration device 1 configured to input a plurality of input graphs G each including nodes showing input elements and an edge which can be branched and combined between the nodes and integrate the input graphs G includes: a graph input means 11; an input graph storage means 12; a similarity calculation means 13 which calculates a similarity of each input graph G by DP matching; a similarity determination means 14 which determines whether each input graph G is similar or not based on the similarity; a graph integration means 15 which integrates each input graph G when the input graph G is similar; a graph addition means 16 which adds each input graph G as a new integration graph when the input graph G is not; and an integration graph storage means 17. <P>COPYRIGHT: (C)2010,JPO&amp;INPIT

Description

  The present invention relates to a graph integration device that integrates an input graph composed of nodes indicating input elements and edges indicating connections between nodes, branches between nodes, or merging between nodes, and a program thereof.

  Conventionally, for example, when a speech signal is used as a graph of recognition candidates such as phonemes and words in speech recognition, the accuracy of speech recognition is improved by recognizing this graph based on a plurality of language models. Has been done.

Here, in order to generate a more appropriate recognition result from a plurality of language models, this graph is integrated (see Patent Document 1). For example, the invention described in Patent Document 1 integrates this graph by reducing unnecessary paths from this graph.
JP 2003-15685 A

  However, in the invention described in Patent Document 1, when three or more graphs are integrated, it is necessary to compare the graphs by the number of times these graphs are combined, and the amount of calculation increases. For example, in the invention described in Patent Document 1, in order to integrate n graphs, it is necessary to compare the graphs n × (n−1) / 2 times, which is not convenient. Further, in the prior art, a plurality of graphs are only integrated into one graph, and cannot be integrated into two or more graphs.

  Therefore, an object of the present invention is to provide a graph integration apparatus and a program thereof that can handle a plurality of integrated graphs, have a small amount of calculation, and have a simple configuration.

  In order to solve the above-described problem, the graph integration apparatus according to claim 1 integrates a plurality of input graphs configured by nodes indicating input elements and edges capable of branching and joining at the nodes, and integrating the input graphs. The graph integration device includes a similarity calculation unit, a similarity determination unit, a graph integration unit, and a graph addition unit.

  In such a configuration, the graph integration apparatus obtains, as a result of DP matching, the node matching, insertion error, missing error, and substitution error of a plurality of input graphs using the DP matching method by the similarity calculation means. . Then, the graph integration device substitutes the DP matching result into a preset function by the similarity calculation means to calculate the similarity between the input graphs, and obtains the calculated DP matching result and the calculated input graph. Outputs the similarity between each other.

  Also, the graph integration device determines that the input graphs are similar when the similarity between the input graphs input from the similarity calculation unit is greater than or equal to a preset threshold by the similarity determination unit. Furthermore, when the similarity between the input graphs input from the similarity calculation unit is less than the threshold by the similarity determination unit, the graph integration apparatus determines that the input graphs are not similar and outputs the similarity determination result. Thereby, the graph integration device can reduce a situation where input graphs having low similarity are integrated.

  In the similarity determination result input from the similarity determination unit, when the input graphs are similar to each other, the graph integration device calculates the input graphs based on the DP matching result input from the similarity calculation unit by the graph integration unit. Integrate into an integrated graph. When the input graphs are not similar in the similarity determination result input from the similarity determination unit, the graph integration device adds each of the input graphs as a new integrated graph by the graph addition unit.

  Next, the graph integration device uses the DP matching method by the similarity calculation means to match and insert errors between the input graph and the integrated graph integrated by the graph integration means or the integrated graph added by the graph addition means. And a missing error and a substitution error are obtained as a result of DP matching. Then, the graph integration device calculates the similarity between the input graph and the integrated graph by substituting the DP matching result into a function, and calculates the similarity between the obtained DP matching result and the calculated input graph and the integrated graph. Is output.

  The graph integration apparatus determines that the input graph and the integrated graph are similar when the similarity between the input graph input from the similarity calculation unit and the integrated graph is greater than or equal to a threshold by the similarity determination unit. Furthermore, when the similarity input from the similarity calculation unit is less than the threshold by the similarity determination unit, the graph integration apparatus determines that the input graph and the integrated graph are not similar, and outputs this similarity determination result. As a result, the graph integration device can reduce a situation where an input graph having a low similarity and an integrated graph are integrated.

  In the similarity determination result input from the similarity determination unit, when the input graph and the integrated graph are similar, the graph integration device performs input based on the DP matching result input from the similarity calculation unit by the graph integration unit. Integrate the graph with the integrated graph.

  When the input graph and the integrated graph are not similar in the similarity determination result input from the similarity determination unit, the graph integration device adds the input graph as a new integrated graph by the graph addition unit. As a result, the graph integration device can integrate the input graph and the integrated graph, eliminating the need to perform similarity determination for the number of times the input graphs are combined, and handling a plurality of integrated graphs.

  In order to solve the above-described problem, the graph integration program according to claim 2 inputs a plurality of input graphs composed of nodes indicating input elements and edges that can branch and merge at the nodes. In order to integrate, the computer is configured to function as a similarity calculation unit, a similarity determination unit, a graph integration unit, and a graph addition unit.

  In such a configuration, the graph integration program uses the DP calculation method by the similarity calculation means to obtain node matches, insertion errors, missing errors, and substitution errors of a plurality of input graphs. Then, the graph integration program calculates the similarity between the input graphs by substituting the DP matching result into a preset function, and outputs the calculated DP matching result and the calculated similarity between the input graphs. To do.

  The graph integration program determines that the input graphs are similar when the similarity between the input graphs input from the similarity calculation unit is greater than or equal to a preset threshold by the similarity determination unit. Furthermore, the graph integration program determines that the input graphs are not similar when the similarity between the input graphs input from the similarity calculation unit is less than the threshold by the similarity determination unit. Thereby, the graph integration program can reduce the situation where input graphs with low similarity are integrated.

  In the similarity determination result input from the similarity determination unit, when the input graphs are similar, the graph integration program calculates the input graphs based on the DP matching result input from the similarity calculation unit by the graph integration unit. Integrate into an integrated graph. If the input graphs are not similar in the similarity determination result input from the similarity determination unit, the graph integration program adds each of the input graphs as a new integrated graph by the graph addition unit.

  Next, the graph integration program uses the DP matching method by the similarity calculation means to match and insert errors between the input graph and the integrated graph integrated by the graph integration means or the integrated graph added by the graph addition means. Find missing errors and substitution errors. Then, the graph integration program calculates the similarity between the input graph and the integrated graph by substituting the DP matching result into a function, and calculates the similarity between the obtained DP matching result and the calculated input graph and the integrated graph. Is output.

  The graph integration program determines that the input graph and the integrated graph are similar when the similarity between the input graph input from the similarity calculation unit and the integrated graph is greater than or equal to a threshold value by the similarity determination unit. Furthermore, the graph integration program determines that the input graph and the integrated graph are not similar when the similarity input from the similarity calculation unit is less than the threshold by the similarity determination unit. As a result, the graph integration program can reduce a situation where an input graph having a low similarity and an integrated graph are integrated.

  In the similarity determination result input from the similarity determination unit, when the input graph and the integrated graph are similar, the graph integration program is input based on the DP matching result input from the similarity calculation unit by the graph integration unit. Integrate the graph with the integrated graph.

  When the input graph and the integrated graph are not similar in the similarity determination result input from the similarity determination unit, the graph integration program adds the input graph as a new integrated graph by the graph addition unit. As a result, the graph integration program can integrate the input graph and the integrated graph, eliminating the need to perform similarity determination for the number of times the input graphs are combined, and handling a plurality of integrated graphs.

According to the present invention, the following excellent effects can be obtained.
According to the first and second aspects of the invention, it is not necessary to perform similarity determination for the number of combinations of input graphs, and a plurality of integrated graphs can be handled, so that the amount of calculation can be reduced, and graph integration The apparatus can have a simple configuration. Further, according to the first and second aspects of the present invention, it is possible to reduce the situation where the input graphs having low similarity and the input graph and the integrated graph are integrated, so that the graphs are more accurately integrated.

[Configuration of Graph Integration Device]
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings as appropriate.
With reference to FIG. 1, the structure of the graph integration apparatus which concerns on this embodiment of this invention is demonstrated. FIG. 1 is a block diagram showing a configuration of a graph integration apparatus according to this embodiment of the present invention.

  The graph integration device 1 in FIG. 1 integrates an input graph G by inputting a plurality of input graphs G composed of nodes indicating input elements and edges composed of edges that can branch and merge between the nodes. A graph input unit 11, an input graph storage unit 12, a similarity calculation unit 13, a similarity determination unit 14, a graph integration unit 15, a graph addition unit 16, and an integrated graph storage unit 17. . In FIG. 1, the input graph is indicated by a symbol G and the integrated graph is indicated by a symbol T.

  The graph input means 11 receives a plurality of input graphs G1, G2, G3, G4 (G) in FIG. For example, the graph input means 11 includes a communication port that receives the input graphs G1, G2, G3, and G4 (G) from the outside, or a reading device that reads the input graph G stored in a storage medium such as a magnetic disk. . Hereinafter, when the input graphs G1, G2, G3, and G4 are described without being distinguished, they are simply referred to as the input graph G. Details of the input graph G will be described later.

  The input graph storage unit 12 is a storage unit such as an HDD (Hard Disk Drive) that stores the input graph G input to the graph input unit 11.

  For example, if the integrated graph storage unit 17 (to be described later) does not store the integrated graph T, the similarity calculation unit 13 uses a DP matching method to store a plurality of input graphs G stored in the input graph storage unit 12 (for example, The node match, insertion error, missing error, and substitution error in the input graph G1 in FIG. 2A and the input graph G2 in FIG. 2B are obtained as a result of DP matching. Then, the similarity calculation unit 13 substitutes the DP matching result into a preset function, and calculates the similarity of each of the input graphs G.

  Here, the input graph storage unit 12 may store a calculation flag indicating whether or not the similarity of the input graph G has been calculated for each input graph G. In this case, the calculation flag is set as an initial value where the similarity is not calculated (for example, “0”). Then, the similarity calculation means 13 may set the calculation flag to “calculated” (for example, “1”) for the input graph G for which the similarity is calculated.

  In addition, the similarity calculation unit 13 uses, for example, the DP matching method to store the input graph G stored in the input graph storage unit 12 and the integrated graph storage using the DP matching method if the integrated graph storage unit 17 stores the integrated graph T. The node match with the integrated graph T stored in the means 17, the insertion error, the missing error, and the substitution error are obtained as DP matching results, and the result of the DP matching is substituted into a function to obtain the input graph G and the integrated graph T; The degree of similarity is calculated. The similarity calculation unit 13 outputs the obtained DP matching result and the calculated similarity to the graph integration unit 15 via the similarity determination unit 14 and the similarity determination unit 14.

  Here, the integrated graph storage means 17 to be described later may store an integrated flag indicating whether or not the similarity of the integrated graph T has been calculated for each integrated graph T. In this case, the integration flag is set as an initial value that has not been calculated (for example, “0”). Then, the similarity calculation unit 13 may set the integration flag to already calculated (for example, “1”) for the integrated graph T for which the similarity is calculated.

  For example, if the integrated graph storage unit 17 does not store the integrated graph T, the similarity determination unit 14 stores the input graph G when the similarity of each of the input graphs G is equal to or greater than a preset threshold value. It is determined that each of the input graphs G is similar, and when each similarity of the input graphs G is less than the threshold value, it is determined that each of the input graphs G stored by the input graph storage unit 12 is not similar.

  In addition, the similarity determination unit 14 includes, for example, an input graph G stored in the input graph storage unit 12 and an integrated graph T stored in the integrated graph storage unit 17 if the integrated graph storage unit 17 stores the integrated graph T. Are determined to be similar. Details of the calculation of similarity and similarity determination will be described later. Further, the similarity determination unit 14 outputs a similarity determination result indicating whether or not they are similar to the graph integration unit 15 and the graph addition unit 16.

  The graph integration unit 15 integrates each of the input graphs G into the integrated graph T based on the result of DP matching when the input graphs G are similar in the similarity determination result output by the similarity determination unit 14. is there. Further, the graph integration unit 15 determines that the input graph G and the integrated graph T based on the result of the DP matching method when the input graph G and the integrated graph T are similar in the similarity determination result output by the similarity determination unit 14. Are integrated and stored in the integrated graph storage means 17.

  The graph addition unit 16 adds each of the input graphs G as a new integrated graph T when the input graphs G are not similar in the similarity determination result output by the similarity determination unit 14. Further, the graph adding means 16 adds the input graph G as a new integrated graph T when the input graph G and the integrated graph T are not similar in the similarity determination result output by the similarity determining means 14, and the integrated graph storage means 17 to memorize.

  The integrated graph storage unit 17 stores the integrated graph T integrated by the graph integration unit 15 or the integrated graph T added by the graph addition unit 16. Here, the graph integration device 1 may output the integrated graph T stored by the integrated graph storage unit 17 in response to a request from an external speech recognition device (not shown). In FIG. 1, the input graph storage unit 12 and the integrated graph storage unit 17 are illustrated separately for the sake of explanation, but these may be configured by one storage unit (not illustrated).

<Details of input graph>
The details of the input graph will be described below with reference to FIGS. 2 and 3 (see FIG. 1 as appropriate). FIG. 2 is a diagram for explaining the input graph input to the graph input means of FIG. 1, and (a) to (d) are first to fourth examples of the input graph, respectively. FIG. 3 is a diagram for explaining an input graph input to the graph input means of FIG. 1, and (a) to (c) are a first example, a fifth example, and a sixth example of the input graph, respectively. Note that the input graphs shown in FIGS. 2A and 3A are the same.

  In FIG. 2, the head of the input graph G is illustrated as “head”, and the end of the input graph G is illustrated as “end”. The nodes are illustrated by rectangles, and the node names are shown inside the rectangles. Hereinafter, when a node is specified and described, the node name is described (for example, a node A1, a node C6, etc.). Further, the edge indicates connection between nodes, merging between nodes, and branching between nodes, and is illustrated by an arrow connecting the nodes and an arrow connecting the head or end of the input graph G and the node. did. As is clear from the direction of the arrow indicating the connection direction of the edge, the input graph G is a directed graph composed of nodes and edges.

  As shown in FIG. 2A, in the input graph G1, the node A1, the node A2, the node A3, the node A4, the node A5, and the node A6 are sequentially connected by edges from the head to the end. As shown in FIG. 2B, in the input graph G2, the nodes A1,..., The node A4, the node B5, and the node A6 are sequentially connected by edges.

  Further, as shown in FIG. 2C, in the input graph G3, nodes A1,..., Node A4, node B5, and node C6 are sequentially connected by edges. Further, as shown in FIG. 2D, in the input graph G4, the node A1, the node D2, the node D3, the node A4, the node B5, and the node C6 are sequentially connected by edges.

  As shown in FIG. 3B, in the input graph G5, nodes A1,..., Node A4 and node B5 are sequentially connected by edges. As shown in FIG. 3C, the input graph G6 has nodes A1,..., Node B5, node A6, and node A7 connected in order by edges.

<Details of Similarity Calculation and Similarity Determination: First Example>
Hereinafter, details of the calculation of the similarity and the similarity determination will be described with reference to FIG. 4 (see FIGS. 1 and 2 as appropriate). FIG. 4 is a diagram for explaining an integrated graph integrated by the graph integration unit of FIG. 1, and (a) to (c) are first to third examples of the integrated graph, respectively. Here, an example in which similarity is determined by calculating the similarity of the four input graphs G shown in FIG.

  First, the similarity calculation unit 13 calculates the similarity of the input graphs G1 and G2 in FIG. 2 using the DP matching method. Specifically, the similarity calculation means 13 obtains the node match (H), insertion error (I), missing error (D) or substitution error (S) of the input graphs G1 and G2 as a result, and this DP matching. The degree of similarity is calculated by substituting the result into the following formula (1). Here, the expression (1) corresponds to the function described in the claims.

  Similarity = (HI) / (H + S + D) Formula (1)

  In this case, the similarity calculation means 13 can obtain “HHHHSH” as a result that only the node A5 of the input graph G1 and the node B5 of the input graph G2 become substitution errors and the other nodes match. Then, the similarity calculation means 13 substitutes the result of this DP matching into the equation (1), and calculates the similarity as 5/6. Note that the similarity calculation means 13 may set the calculation flags of the input graphs G1 and G2 to have been calculated.

  The similarity determination means 14 compares the similarity (for example, 5/6) of the input graphs G1 and G2 with a preset threshold value (for example, 1/2), and since the similarity is equal to or greater than the threshold value, the input graph G1 , G2 are determined to be similar.

  Since the input graphs G1 and G2 are similar, the graph integration unit 15 integrates the input graphs G1 and G2 into the integrated graph T in FIG. 4A based on the result of the DP matching method. Here, the graph integration unit 15 may arrange the nodes as they are in the integrated graph T for the nodes whose DP matching results match. Further, the graph integration unit 15 may insert a node into the integrated graph T for a node in which the DP matching result is an insertion error. Further, the graph integration unit 15 may add an edge that directly connects the nodes before and after the node so that the node that skips the DP matching result is skipped. Then, the graph integration unit 15 may arrange nodes in the integrated graph T in parallel in the integrated graph T for the nodes whose DP matching result is an alternative error.

  Specifically, since the nodes A1 to A4 and the node A6 match in the input graphs G1 and G2, the graph integration unit 15 sequentially changes the node A6 from the “first” to the node A1. Immediately before the “end point”. In addition, in the input graphs G1 and G2, since the node A5 and the node B5 become substitution errors, the graph integration unit 15 makes the node A5 and the node B5 in parallel. Then, the graph integration unit 15 branches the edge from the node A4 located immediately before the nodes A5 and B5 that are substitution errors to the nodes A5 and B5 that are substitution errors. Further, the graph integration unit 15 merges edges from the nodes A5 and B5 that are substitution errors into the node A6 that is located immediately after the nodes A5 and B5 that are substitution errors.

  When the input graphs G1 and G2 are not similar, the graph adding unit 16 stores the input graphs G1 and G2 in the integrated graph storage unit 17 as new integrated graphs T, respectively. In this case, the graph integration device 1 can perform similarity determination using a plurality of integrated graphs T.

  Next, the similarity calculation means 13 uses the DP matching method to calculate the similarity between the input graph G3 in FIG. 2C and the integrated graph T in FIG. calculate. The similarity calculation unit 13 may set the calculation flag of the input graph G3 to “calculated” and set the integration flag of the integrated graph T to “calculated”.

  Here, a case where DP matching up to node A1... Node A4 is completed will be described as an example. Since the node A5 and the node B5 branch, the similarity calculation means 13 is (1) “HHHHD” for the node A5 in the integrated graph T, (2) “HHHHS” for the node A5 in the integrated graph T, (3) integration Five hypotheses are generated: “HHHHD” for the node B5 in the graph T, (4) “HHHHH” for the node B5 in the integrated graph T, and (5) “HHHHI” for the node B5 in the input graph G3.

  Further, since the similarity calculation means 13 joins at the node A6, (1) a missing error of the node A5 in the integrated graph T, (2) a substitution error of the node A5 in the integrated graph T, (3) a node in the integrated graph T The above hypotheses of B5 missing error, (4) node B5 match in the integrated graph T, and (5) node B5 insertion error in the input graph G3 are merged.

  Here, the similarity calculation means 13 calculates the similarity using the result that the node B5 matches because the hypothesis (4) is minimized. Therefore, the similarity calculation means 13 uses the result “HHHHH (B5) S” that results in the substitution error only in the node A6 of the integrated graph T and the node C6 of the input graph G3, and the other nodes match. Calculated as 5/6.

  The similarity determination unit 14 compares the similarity (for example, 5/6) between the integrated graph T and the input graph G3 with a threshold (for example, 1/2). It is determined that the input graph G3 is similar.

  Since the integrated graph T and the input graph G3 are similar, the graph integration unit 15 converts the integrated graph T and the input graph G3 into an integrated graph T ′ (T) in FIG. 4B based on the DP matching result. Integrate. Here, since the nodes A1 to A5 and B5 match in the integrated graph T and the input graph G3, the graph integration unit 15 sets the nodes A1 to A5 and B5 of the integrated graph T as they are.

  Specifically, in the integrated graph T and the input graph G3, since the node A6 and the node C6 are substitution errors, the graph integration unit 15 adds the node A6 and the node C6 in parallel. Then, the graph integration unit 15 connects the node A5 and the node A6, and branches the edge from the node B5 to the nodes A6 and C6.

  Finally, the similarity calculation means 13 calculates the similarity between the input graph G4 in FIG. 2D and the integrated graph T ′ in FIG. 4B by using the DP matching method. The similarity calculation unit 13 may set the calculation flag of the input graph G4 to “calculated” and set the integration flag of the integrated graph T ′ to “calculated”.

  At this time, similar to the above, the similarity calculation unit 13 calculates the similarity using the node B5 and the node C6. In this case, the similarity calculation means 13 uses “HSSH (B5) H (C6)” as a result that only the node A6 of the integrated graph T ′ and the node C6 of the input graph G3 become substitution errors and other nodes match. Thus, the similarity is calculated as 2/3.

  The similarity determination unit 14 compares the similarity (for example, 2/3) between the integrated graph T ′ and the input graph G4 with a threshold (for example, 1/2), and since this similarity is equal to or greater than the threshold, the integrated graph T It is determined that 'and the input graph G4 are similar.

  Since the integrated graph T ′ and the input graph G4 are similar, the graph integration unit 15 converts the integrated graph T ′ and the input graph G4 into the integrated graph T ″ (FIG. 4C) based on the DP matching result. T).

  Specifically, since the nodes A1 and A4 match in the integrated graph T ′ and the input graph G4, the graph integration unit 15 keeps the nodes A1 and A4 of the integrated graph T as they are. In addition, in the integrated graph T ′ and the input graph G4, the node A2 and the node D2, the node A3 and the node D3, the node A5 and the node B5, and the node A6 and the node C6 become substitution errors. Here, the graph integration unit 15 makes the node A2 and the node D2 parallel, and makes the node A3 and the node D3 parallel. Further, the graph integration unit 15 branches the edge from the node A1 located immediately before the nodes A2 and D2 that are substitution errors to the nodes A2 and D2 that are substitution errors.

  Further, since the nodes A2 and D2 and the nodes A3 and D3 that are substitution errors are continuous, the graph integration unit 15 connects the edge from the node A2 to the node A3, and connects the edge from the node D2 to the node D3. Then, the graph integration unit 15 merges the edges from the nodes A3 and D3 that are substitution errors into the node A4 that is located immediately after the nodes A3 and D3 that are substitution errors. Since the nodes A5 and B5 and the nodes A6 and C6 are the same as the integrated graph T ′, the description thereof is omitted.

  As described above, the similarity calculation unit 13 calculates the similarity using a path that matches the node N of the input graph G among the parallel nodes N, and thus conventionally n × (n−1) / 2 times. The number of graph comparisons that have been made can be reduced to n times.

  When the integrated graph T ′ and the input graph G4 are not similar, the graph adding unit 16 stores the input graph G4 in the integrated graph storage unit 17 as a new integrated graph T. In this case, the graph integration device 1 can perform similarity determination using a plurality of integrated graphs T.

<Details of Similarity Calculation and Similarity Determination: Second Example>
Hereinafter, returning to FIG. 3, the calculation of the similarity when a missing error and an insertion error occur will be described (see FIG. 1 as appropriate).

  For example, when comparing the input graph G1 in FIG. 3A with the input graph G5 in FIG. 3B, the similarity calculation unit 13 can obtain the result “HHHHSD” in which the node A6 has a missing error. Also, the similarity calculation means 13 calculates the similarity as 4/6 by substituting the DP matching result into the equation (1). In the same manner as described above, the similarity determination unit 14 determines similarity based on whether or not the similarity is equal to or greater than a predetermined threshold. Here, since the similarity is greater than or equal to a threshold value (for example, 1/2), the similarity determination unit 14 determines that the input graphs G1 and G5 are similar.

  Also, when comparing the input graph G1 in FIG. 3A and the input graph G6 in FIG. 3C, the similarity calculation means 13 can obtain “HHHHSHI” as a result of the insertion error in the node A7. Also, the similarity calculation means 13 calculates the similarity as 4/6 by substituting the DP matching result into the equation (1). In the same manner as described above, the similarity determination unit 14 determines similarity based on whether or not the similarity is equal to or greater than a predetermined threshold. Here, since the similarity is greater than or equal to a threshold (for example, 1/2), the similarity determination unit 14 determines that the input graphs G1 and G6 are similar.

[Operation of Graph Integration Device]
The operation of the graph integration apparatus according to this embodiment of the present invention will be described below with reference to FIG. 5 (see FIG. 1 as appropriate). FIG. 5 is a flowchart showing the operation of the graph integration apparatus of FIG. Here, description will be made assuming that the input graph G is stored in the input graph storage unit 12 and the integrated graph T is stored in the integrated graph storage unit 17.

  The graph integration device 1 refers to the calculation flag stored in the input graph storage unit 12 by the similarity calculation unit 13 and determines whether or not there is an input graph G whose similarity is not calculated (step S1). When there is an input graph G for which the similarity is not calculated (Yes in step S1), the graph integration device 1 initializes the maximum value of the similarity using the similarity calculation unit 13 (for example, initializes it to 0) ( Step S2).

  Following step S2, the graph integration device 1 refers to the integration flag stored in the integrated graph storage unit 17 by the similarity calculation unit 13 and determines whether there is an integrated graph T whose similarity is not calculated. (Step S3).

  When there is an integrated graph T whose similarity is not calculated (Yes in step S3), the graph integration device 1 uses the DP matching method by the similarity calculation unit 13 to determine the similarity between the integrated graph T and the input graph G. Is calculated (step S4). Then, the graph integration apparatus 1 determines whether or not the calculated similarity is equal to or greater than the maximum value of the similarity by the similarity calculation unit 13 (step S5).

  When the calculated similarity is equal to or greater than the maximum value (Yes in step S5), the graph integration device 1 updates the maximum value of the similarity with the calculated similarity by the similarity calculation means 13 (step S6), and step S3. Return to the process. On the other hand, when the similarity is less than the maximum value (No in step S5), the graph integration device 1 returns to the process of step S3 without updating the maximum value of the similarity.

  When there is no integrated graph T whose similarity is not calculated (No in step S3), the graph integration apparatus 1 determines that the similarity between the integrated graph T and the input graph G is greater than or equal to the threshold by the similarity determination unit 14. It is determined that T and the input graph G are similar, and if the similarity between the integrated graph T and the input graph G is less than the threshold value, it is determined that the integrated graph T and the input graph G are not similar (step S7).

  When the integrated graph T and the input graph G are similar (Yes in step S7), the graph integration device 1 integrates the integrated graph T and the input graph G by the graph integration unit 15 based on the result of the DP matching method. (Step S8). On the other hand, when the integrated graph T and the input graph G are not similar (No in step S7), the graph integrating device 1 adds the input graph G as a new integrated graph T by the graph adding unit 16 (step S9).

  Thereafter, the graph integration device 1 returns to the process of step S1 and refers to the calculation flag stored in the input graph storage unit 12 to determine whether or not there is an input graph G whose degree of similarity has not been calculated. Here, when there is an input graph G whose similarity is not calculated, the graph integration apparatus 1 repeats the above-described processing until there is no input graph G whose similarity is not calculated. If there is no input graph G whose similarity is not calculated (No in step S1), the graph integration device 1 ends the process.

  In the present embodiment, the graph integration apparatus according to the present invention has been described as an independent apparatus. However, in the present invention, a general computer can be operated by a program that functions as each of the above-described units. This program may be distributed via a communication line, or may be distributed by writing in a recording medium such as a CD-ROM or a flash memory.

It is a block diagram which shows the structure of the graph integration apparatus which concerns on this embodiment of this invention. It is a figure explaining the input graph input into the graph input means of FIG. 1, (a)-(d) is the 1st example-4th example of an input graph, respectively. It is a figure explaining the input graph input into the graph input means of FIG. 1, (a)-(c) is the 1st example, 5th example, and 6th example of an input graph, respectively. It is a figure explaining the integrated graph which the graph integration means of FIG. 1 integrated, (a)-(c) is the 1st example-3rd example of an integrated graph, respectively. It is a flowchart which shows operation | movement of the graph integration apparatus of FIG.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Graph integration apparatus 11 Graph input means 12 Input graph storage means 13 Similarity calculation means 14 Similarity determination means 15 Graph integration means 16 Graph addition means 17 Integrated graph storage means

Claims (2)

In a graph integration device that inputs a plurality of input graphs composed of nodes indicating input elements and edges capable of branching and joining at the nodes, and integrating the input graphs,
Using the DP matching method, the node matching, insertion error, missing error, and substitution error of the plurality of input graphs are obtained, and the result of the DP matching is substituted into a preset function to obtain a difference between the input graphs. Similarity calculation means for calculating similarity;
Similarity determination means for determining that the input graphs are similar when the similarity between the input graphs is equal to or greater than a preset threshold, and determining that the input graphs are not similar when the similarity is less than the threshold When,
Based on the result of the DP matching, when the input graphs are similar to each other, a graph integration unit that integrates the input graphs into an integrated graph;
If the input graphs are not similar to each other, a graph adding means for adding each of the input graphs as a new integrated graph, and
The similarity calculation means calculates the similarity between the input graph and the integrated graph integrated by the graph integration means or the integrated graph added by the graph addition means,
The similarity determination unit determines that the input graph and the integrated graph are similar when the similarity between the input graph and the integrated graph is equal to or greater than the threshold, and when the similarity is less than the threshold, the input Determining that the graph and the integrated graph are not similar,
The graph integration means integrates the input graph and the integrated graph when the input graph and the integrated graph are similar,
The graph adding unit adds the input graph as the new integrated graph when the input graph and the integrated graph are not similar. In order to integrate a plurality of input graphs composed of nodes indicating input elements and edges that can branch and merge at the nodes,
Using the DP matching method, the node matching, insertion error, missing error, and substitution error of the plurality of input graphs are obtained, and the result of the DP matching is substituted into a preset function to obtain a difference between the input graphs. Similarity calculation means for calculating similarity,
Similarity determination means for determining that the input graphs are similar when the similarity between the input graphs is equal to or greater than a preset threshold, and determining that the input graphs are not similar when the similarity is less than the threshold ,
If the input graphs are similar based on the result of the DP matching, a graph integration unit that integrates the input graphs into an integrated graph;
When the input graphs are not similar to each other, function as a graph addition unit that adds each of the input graphs as a new integrated graph,
The similarity calculation means calculates the similarity between the input graph and the integrated graph integrated by the graph integration means or the integrated graph added by the graph addition means,
The similarity determination unit determines that the input graph and the integrated graph are similar when the similarity between the input graph and the integrated graph is equal to or greater than the threshold, and when the similarity is less than the threshold, the input Determining that the graph and the integrated graph are not similar,
The graph integration means integrates the input graph and the integrated graph when the input graph and the integrated graph are similar,
The graph adding program, when the input graph and the integrated graph are not similar, adds the input graph as a new integrated graph.

Images