JPH0773202A - Digraph reconstituting method - Google Patents

Abstract

PURPOSE:To speed up retrieval processing speed by integrating the sides having the same lavel originating from the same node into one and reconstituting a digraph composed of sub graph groups, for a converted sub-digraph group. CONSTITUTION:The number of a prescribed label division is fixed every depth from the starting node of a digraph. For a digraph to be the object of a reconstituion, a bit string composing the label 23 of each side 22 of a side set originating from a node 21 is divided by this label division number. The digraph is converted into the sub-digraph group where the side 22 in which each divided bit string is defined as the label 23 is serially connected. In this case, for the converted sub-digraph group, further, the sides 22 having the same label 23 originating from the same node 21 are integrated into one and are reconstituted into the digraph composed of sub-digraph groups. Therefore, the number of times of comparison of the label 23 of the sides 22 of the sub-digraph group can be a fewer by the number of the label 23 of the integrated sides 22.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a directed graph reconstructing method, and reconstructs a directed graph based on a sub-directed graph obtained by dividing edge labels in a directed graph so that edge labels in the directed graph can be searched at high speed. The present invention relates to a method for reconstructing a directed graph.

[0002]

2. Description of the Related Art In a directed graph, since a tree structure and a network structure can be expressed as they are by using this as an element, in a recent data processing system, data which efficiently represents the data can be expressed. It has been widely used as a structure. For example, when constructing a database, a database schema is created with a tree-structured data structure and used for hierarchical search processing. Further, in the database thus constructed, it becomes possible to retrieve even the related data related by the representation of the network structure.

By the way, when searching a data group having a data structure represented by a directed graph, a search method for a label of an edge of a directed graph, which has been generally used in the past, is based on an edge set generated from each node of the directed graph. On the other hand, looking at the value of the label on each edge, if the condition is met, follow the edge to move to the node pointed to by the edge, and if the condition is not met, move to the next node in the edge set. There is a search method for checking whether or not an edge is a condition. The data search of the database is performed by such a search method.

According to such a search method, for example, if the data to be searched here is the data of the label of the edge where the i-th element of the edge set originating from one clause matches the condition, Regarding the search for the edge of the clause, the comparison of whether or not the condition is met is repeated i times up to the i-th time. Therefore, many comparison processes must be repeated for each edge set of each clause, and the number of comparisons of data search becomes enormous in a database having a data structure represented by a directed graph.

[0005]

In the above-described search method for a directed graph, the edge to be searched next is found by searching the edge label in each clause, and the movement to the next clause is performed. Assuming that the number of elements in the edge set of each node of the target directed graph is n, obviously (n + 1) / 2 edge label comparisons are required for one node in the search of the directed graph.

For this reason, when performing a search process for a directed graph having a data structure in which a network is constructed by a large-scale directed graph, the number of labels on the edges to be compared also increases according to the number of the edges. . Therefore, when searching a network of a large-scale directed graph, the number of edges to be compared also increases according to the number of edges, and when searching from the data of the data structure represented by such a directed graph. In order to perform comparison processing on many sides,
A large load is imposed on the processing speed.

The present invention has been made to solve the above problems, and an object of the present invention is to obtain a data search when a data structure of a network is represented by a directed graph. It is an object of the present invention to provide a directed graph reconstruction method for reconstructing a directed graph having a structure capable of increasing the search speed.

[0008]

In order to achieve the above-mentioned object, a directed graph reconstruction method, which is the first feature of the present invention, provides a predetermined number of label divisions for each depth from the start node of a directed graph. Determine the number of label divisions, and divide the bit string that constitutes the label of each edge of the edge set originating from the node,
Convert the edges with the respective divided bit strings as labels into a series of connected sub-directed graphs, combine the edges of the converted sub-directed graphs that have the same label from the same clause into one, and then convert them from the sub-directed graphs It is characterized in that it is reconstructed into a directed graph.

The directed graph reconstruction method, which is the second feature of the present invention, divides the bit string constituting the label of each edge of the edge set originating from the node by a predetermined number of label divisions, and dividing each divided bit string. Convert the edges to be labels into sub-directed graph groups that are connected in series, and for the converted sub-directed graph groups, set 1 to the edge with the same label that originates from the same clause.
In summary, the sub-directed graph group is reconstructed, and it is determined whether or not the average value of the number of comparisons in the edge set is smaller than that of the original untransformed directed graph for the reconstructed sub-directed graph group. If the average value of is less than the directed graph before conversion, the reconstructed sub-directed graph group is retained, and if the average value is greater than or equal to the average number of comparisons in the edge set of the original directed graph, the sub-directed graph group is discarded. Then, perform the conversion that leaves the original directed graph,
It is characterized by reconstructing a directed graph.

[0010]

In the directed graph reconstruction method of the first feature of the present invention, first, a predetermined number of label divisions is determined for each depth from the start node of the directed graph. With respect to the directed graph to be reconstructed, the number of label divisions divides the bit string forming the label of each side of the side set originating from the node. Then, it is converted into a sub-directed graph group in which the edges having the respective divided bit strings as labels are connected in series.
Here, with respect to the converted sub-directed graph group, edges having the same label, which are emitted from the same clause, are further combined into one and reconstructed into a directed graph including the sub-directed graph group.

As a result, the reconstructed directed graph is
With respect to the sub-directed graph group of the element, the label of each edge of the sub-directed graph group is divided into bit strings that constitute the label before reconstruction, and the labels of the same bit string in the division unit are combined to form one edge. Has become the label. For this reason, the number of times the labels of the edges of the sub-directed graph group are compared can be as small as the number of labels of the edges that are collected.

In the directed graph reconstructing method of the second aspect of the present invention, first, the bit string constituting the label of each side of the side set emitted from the node is divided by a predetermined number of label divisions. Next, it is converted into a sub-directed graph group in which the edges having the respective divided bit strings as labels are connected in series.
Then, for the converted sub-directed graph group, the edges having the same label, which are emitted from the same clause, are further combined into one to reconstruct the sub-directed graph group.

Here, the reconfigured sub-directed graph group is verified whether or not it has been reconfigured into a preferred state directed graph because the number of label comparisons at the time of retrieval is small, and conversion is performed to a favorable directed graph. Therefore, subsequently, it is determined whether or not the average value of the number of comparisons in the edge set of the reconstructed sub directed graph group is smaller than that of the original directed graph before conversion. As a result of this determination, when the average value of the number of comparisons in the edge set is smaller than the original directed graph before conversion, conversion that leaves the reconstructed sub directed graph group is performed. If the average value of the number of comparisons in the edge set is greater than or equal to the average value of the number of comparisons in the edge set of the original directed graph, the sub-directed graph group is discarded and the original directed graph is converted.

As a result, the reconstructed directed graph is
Regarding the sub-directed graph group of the element, the label of each edge of the sub-directed graph group is divided into bit strings that compose the label before reconstruction, and the labels of the same bit string in the division unit are grouped into one edge. Has become the label. For this reason, the number of comparisons of the labels of the edges of the sub directed graph group can be reduced by the number of the labels of the collected edges.

Here, the bit string of the original label is divided, and as the new label, the labels of the same bit string are grouped in the unit of division, but there are few newly formed labels and the labels are grouped sufficiently. There are cases where it does not exist. In this case, since the label is increased by the number of label divisions for one label comparison of the original directed graph,
The number of new label comparisons increases. For this reason, it is verified whether the reconfigured sub-directed graph group is reconfigured into an optimal directed graph because the number of label comparisons at the time of retrieval is sufficiently small, and conversion is performed to the optimal directed graph. In that case, the number of label divisions is changed, the directed graph is reconstructed in each case, and the directed graph in the optimum state is reconstructed by the determination of the number of comparisons.

[0016]

Embodiments of the present invention will be specifically described below with reference to the drawings. FIG. 1 is a PAD (Problem Analysis Diagra) for explaining the processing flow of the directed graph reconstruction method of the present invention.
m) It is a figure. In this process, for each node of the directed graph to be processed, for each edge that originates from that node, the bit string of the edge label is divided, and the sub-directed graph is created as a new edge of the bit string of the divided edge. To reconstruct the directed graph.

The flow of the process of the directed graph reconstruction method will be described with reference to FIG. 1. When the process starts, first, in the iterative process control block 11, for each element (section) of all the node sets of the directed graph. Control for performing the iterative processing is further performed, and the next iterative processing control block 12 is further performed.
In, control of iterative processing is performed for all elements (edges) emitted from the target node. As a result, the processing from the next processing block 13 to the processing block 18 is performed for each element (section) of all the node sets, for the node of each element, and for all edges originating from that node. Control is performed to sequentially execute the processing, and the processing is performed for each edge.

In the processing for each edge, first, in the processing block 13, the bit string forming the edge label is divided, and in the next processing block 14, the edges labeled with the divided bit string are connected in series. To the restructured structure (edge-series sub directed graph). Next, in processing block 15, edges having the same label that originate from the same node of the reconstructed directed graph (sub-directed graph) are combined into one, and then in determination processing block 16, processing block 17, and processing block 18, here Evaluate the sub-directed graph reconstructed in.

In the processing for evaluating the directed graph, the judgment processing block 16 judges whether the average value of the number of comparisons in the reconstructed edge set is smaller than the original one. If the result of this determination is that the average number of comparisons in the edge set is less than the original, then in the next processing block 17, the reconstructed edge set is left and the processing for that edge originating from one clause is performed. finish. If the average value of the number of comparisons in the edge set is not smaller than the original one in the determination of the determination processing block 16, the original edge set is left in the processing block 18, and the edge generated from one clause is processed. The process ends.

In this way, when the processing for the edge generated from one node is completed, the edge is changed under the control of the iterative processing control block 12, and the processings from the processing block 13 to the processing block 18 are repeatedly performed. Performs processing for all edges originating from the target node. When the processing for all the edges originating from one node is completed, the process returns to the control of the iterative process control block 11, the node is changed, and the process from the iterative process control block 12 to the process block 18 is repeated and the process is repeated. Perform processing on the target clause. When the processing for each element (section) of all the clause sets is completed, the series of processing here is completed.

2 to 5 are diagrams for explaining the directed graph to be reconstructed by the directed graph reconstructing method according to this embodiment, based on specific data examples. FIG. 2 is a diagram for explaining the notation of the directed graph according to the present embodiment,
FIG. 3 is a diagram for explaining label comparison when the bit string of the side label is not divided. FIG. 4 is a diagram for explaining label comparison when a bit string of side labels is divided into two. FIG. 5 is a diagram for explaining label comparison when a bit string of side labels is divided into four.

As shown in FIG. 2, the directed graph is composed of a set of nodes 21 and a set of edges 22 originating from each node. A label 23 is provided on each side 22. In the graph notation 20 expressed in the graph format,
As shown in the upper side of FIG. 2, the joint 21 is represented by a circle, and the side 22 emanating from the joint 21 is represented by an arrow. The value of the label 23 of the side is added to the vicinity of the arrow on that side.

Here, in order to prevent the figure from becoming complicated,
In the directed graph shown in FIG. 2, only a part of the directed graph is shown, and there are no multiple edges pointing to the same node (tree structure).
The directed graph of is displayed. However, it is obvious that the directed graph reconstruction method of the present embodiment described below can be applied to a directed graph having a plurality of edges pointing to the same node (network structure).

In the example of the process of the directed graph reconstructing method of the present embodiment described below, the processing target is a tree-structured directed graph. Further, the graph notation 20 of such a tree-structured directed graph is simplified and easy to see. In order to express this, the table notation 24 is expressed in a table format as shown in the lower side of FIG. The graph notation 20 and the table notation 24 here represent a directed graph having the same content. That is, in the table notation 24, each rectangular block 25 represents a side, and a label is displayed in the side, and the right line (right side) of the rectangular block 25 corresponds to the node here.

Next, when comparing the labels of the edges of the directed graph expressed in this way, according to the present invention, the bit string of the label of each edge is divided and reconstructed into a sub-directed graph for comparison, and the label of each edge is compared. Will be described in comparison with the case where the bit string is compared without being divided. In the following description, it is assumed that the directed graph is expressed in table notation.

FIG. 3 is a diagram for explaining label comparison when the bit string of the edge label is not divided. The directed graph in this table notation shows 22 edges emanating from a certain clause. In order to specify each of the 22 sides, numbers 1 to 22 are given to the left side here. The bit string of the label of each side is expressed by a hexadecimal number, and is written as A4, B0, ... In the rectangular block of the side.

The number of comparisons when the label of each side is the search target is shown on the right side of the rectangular block of each side. If the label “A4” on the first side here is the search target, the search is performed by matching the comparison with the label “A4” on the first side, so the number of comparisons is once. However, for example, when the label “B4” on the third side is the search target, the mismatch in comparison with the label “A4” on the first side and the label “B0” on the second side Therefore, the number of comparisons in this case is 3 because the comparison does not match and the comparison with the label “B4” on the third side occurs.
Times.

In this way, when the number of comparisons of the labels of each side is obtained for the case where the label of each side is the search target, it is as shown on the right side of the rectangular block of each side. It is the number of comparisons. Therefore, in this case, the total number of comparisons is 253 for the edge set that originates from one node of the directed graph, and the average number of comparisons of the edge labels is 11.50 (= 253 ÷ 22).

An example of label comparison when the directed graph reconstruction method according to the present invention is applied to a directed graph having the same contents as the directed graph of FIG. 3 will be described. When the bit string of the side label is divided into two, it becomes as shown in FIG. In FIG. 4, the bit string of the label of each side of the directed graph is divided into two, and is reconfigured as labels of two new sides of the divided side 1 and the divided side 2. As described above, in this case, the same labels originating from the same node in the new edge are combined into one.

That is, the bit string of the label "A4" on the first side before reconstruction is divided into two, and the divided side 1 of the label "A" and the divided side 2 of the label "4" (new (Via nodes) connected in series. The label “B0” on the second side before reconstruction is divided into two bit strings, and the divided side 1 of the label “B” and the divided side 2 of the label “0” are serialized (via a new section). The structure is connected to. Similarly, the label “B4” on the third side before reconstruction
Divides the bit string into two, and divides edge 1 with label "B" and edge 2 with label "4" (via a new section).
The structure is such that they are connected in series. Here, the label “B” of the divided side 1 of the third side is the same as the label “B” of the divided side 1 of the second side, and the label “B” originates from the same section. The divided side 1 of the side and the divided side 1 of the second side are combined into one. In the same manner, when the sides from the fourth side to the 22nd side are divided into two and reconstructed, a directed graph (table notation) as shown in FIG. 4 is obtained.

In this way, in order to evaluate the directed graph reconstructed by dividing it into two, the number of comparisons when the labels of the respective sides are the retrieval targets is calculated, as in the case described with reference to FIG. Ask. The number of comparisons when the label of each side is the search target is shown on the right side of the rectangular block of each divided side 2. In this case, the edge series method is used for comparison. That is, the label “A4” on the first side
Is a search target, the search is performed by matching the comparison with the label “A” of the first divided edge 1 and the comparison with the label “4” of the first divided edge 2. The number of comparisons is twice. When the label “B0” on the second side is the search target, there is a mismatch in comparison with the label “A” on the first side 1 and the label “B” on the second side 1. Since the comparison matches and the comparison with the label “0” on the second divided side 2 is performed, the number of comparisons in this case is three.

When the label "B4" on the third side is the search target, a mismatch in comparison with the label "A" on the first divided side 1 and the label on the second divided side 1 There is a match in comparison with “B”, a mismatch in comparison with the label “0” on the second divided side 2, and a match with comparison with label “4” on the third divided side 2. Therefore, the number of comparisons in this case is four. Thereafter, similarly, the number of comparisons is calculated until the label “CF” on the 22nd side is the search target.

In this way, when the label of each side is the search target, the number of comparisons of the labels of each side is obtained, and the result is shown on the right side of the rectangular block of each divided side 2. The number of comparisons is obtained. In this case, 1 of the directed graph having the same contents as the directed graph shown in FIG.
The total number of comparisons for an edge set originating from one clause is 1
This is 84 times, and the average number of comparisons is 8.36 (= 184 ÷
22). Obviously, the average number of comparisons is reduced when the side bit string is divided (FIG. 4) compared to when the side bit string is not divided (FIG. 3). Therefore, in this way, by dividing the bit string on the side of the directed graph and reconstructing it into the sub-directed graph, the search processing in the directed graph can be speeded up.

FIG. 5 is a view for explaining label comparison when the side bit string is further divided and the side label bit string is divided into four. A directed graph when the bit string of the edge label is divided into four and reconstructed is as shown in FIG.
In FIG. 5, the bit string of the label of each edge of the directed graph is divided into four and reconstructed as a sub-directed graph composed of a set of edges each having a label of 2 bits. That is, the bit string of the label of each side is reconfigured as a label of four new sides of the divided side 1, the divided side 2, the divided side 3, and the divided side 4. As in the previous case, new edge labels originate from the same section, and the same ones are grouped together.

In the hexadecimal notation "A4" of the label of the first side before reconstruction, the bit string is divided into 4 and 2
It becomes four labels of a bit string for each bit (in the following description, the 2-bit notation of each label is expressed by a quaternary number, but also the bits are appropriately expressed in parentheses). In this case, as shown in FIG. 5, the label “A4 (1
The bit string “0100100)” is divided into four, and the divided side 1 of the label “2 (10)” and the label “2 (1
0) "divided side 2 and label" 1 (01) "divided side 3
And the divided side 4 of the label “0 (00)” are connected in series (each via a new node).

Similarly, the bit string with the label "B0 (1010000)" on the second side before reconstruction is divided into four bit strings, and the divided side 1 with the label "2 (10)"
And the divided side 2 of the label “3 (11)” and the label “0
The divided side 3 of (00) "and the divided side 4 of the label" 0 (00) "are connected in series. In such a reconstruction, the label of the divided side 1 of the second side "2" and 1
The label “2” of the divided side 1 of the second side is the same as that of the label “2”, and since it originates from the same section, the divided side 1 of the second side is
And the divided side 1 of the first side are combined into one.

Also, the label "B on the third side before reconstruction"
4 (10110100) "is obtained by dividing the bit string into four, and the divided side 1 of the label" 2 (10) ", the divided side 2 of the label" 3 (11) ", and the label" 1 (01) ". The divided side 3 and the divided side 4 of the label “0 (00)” are connected in series. In this reconstruction, the label “2” of the divided side 1 of the third side is the first side. Is the same as the label “2” of the divided side 1 of the side, and since it originates from the same section, the divided side 1 of the third side and the divided side 1 of the first side are combined into one. And the divided side 2 of the third side
Label "3" is the label "3" of the second divided edge 2
, And both originate from the same clause, so that the divided side 2 of the third side and the divided side 2 of the second side are combined into one.

In this way, the edges of the labels having the same contents, which originate from the same section, are put together. In the same way, the edges from the 4th edge to the 22nd edge are divided into 4 parts and reconstructed, and the edges with the same content that originate from the same clause are combined into one and re-created in the sub directed graph. When configured, a directed graph (table notation) as shown in FIG. 5 is obtained.

Similarly, in order to evaluate the reconstructed directed graph divided into four, the number of comparisons when the labels of the respective sides are the search targets is determined as in the case described with reference to FIG. Then, the average number of comparisons is calculated. The number of comparisons when the label of each side is the search target is shown on the right side of the rectangular block of each divided side 4. Similar to the case described above, the comparison in this case is performed by the edge series method. That is, the label “A4” on the first side
Is a search target, the comparison using the bit string as the edge label is performed by the edge serial method, and the comparison of the comparison with the label “2” of the first divided edge 1 and the edge of the first divided edge 2 are performed. The search is performed by the matching match with the label “2”, the matching match with the label “1” of the first divided edge 3, and the matching match with the label “0” of the first divided edge 4. Therefore, the number of comparisons is four.

When the label "B0" on the second side is the search target, the comparison is coincident with the label "2" on the first divided side 1 and the label "2" on the first side 2 is divided. Disagreement in comparison with "," comparison in comparison with the label "3" of the second division edge 2, comparison with comparison with the label "0" in the second division edge 3, and second division edge 4 Therefore, the number of comparisons in this case is five.

When the label "B4" on the third side is the search target, the comparison is coincident with the label "2" on the first divided side 1 and the label "2" on the first divided side 2 Disagreement in comparison with the label “3” of the second divided edge 2, mismatch in comparison with the label “0” of the second divided edge 3, and the third divided edge 3 In this case, the number of comparisons in this case is 6 since the comparison with the label “1” of “3” and the comparison of the label “0” of the third divided side 4 are performed.
Times. Thereafter, similarly, by comparing the divided bit strings by the edge serial method, the label “C” of the 22nd edge is compared.
The number of comparisons is calculated until F ″ is the search target.

As described above, when the number of comparisons of the labels of each side is calculated for the case where the label of each side is the search target, it is shown on the right side of the rectangular block of each divided side 4. The number of comparisons is obtained. In this case, the total number of comparisons when the edge label is divided into four is 162 times for the edge set generated from one clause of the directed graph having the same content as the directed graph shown in FIG. 3, and the average number of comparisons is
It becomes 7.36 (= 164 ÷ 22). Apparently, the average number of comparisons when the side bit string is divided (FIG. 5) is significantly reduced compared to the case where the side bit string is not divided (FIG. 3). That is, by dividing a bit string on the edge of such a directed graph into a directed graph and reconstructing it into sub-directed graphs, the search processing in the directed graph can be speeded up.

In the directed graph reconstructing method described here, the case where the bit string of the edge label is divided into two and the case where the bit string of the edge label is divided into four are explained. As for the number of divisions, the optimum number of label divisions is determined according to the data content (bit width) of the label of each edge, the number of edges (edge set) that originate from the same node, and the directed graph is reconstructed. . In the evaluation, as described with reference to FIGS. 3 to 5, in the comparison of the labels of the edge set, each case where the number of label divisions of the sides is different is evaluated, and the one having the smallest average comparison number is selected. I will choose.

In the case of this embodiment, since the average number of comparisons is the smallest in the case of four divisions shown in FIG. 5, the directed graph reconstructed by the four divisions is selected. Such a directed graph is reconstructed for an edge set originating from one clause, its evaluation is performed, each clause of the directed graph is evaluated, and this work is repeated over the entire clause set. As a result, a directed graph reconstructed to speed up the edge label search process can be obtained.

As described above, according to the directed graph reconstruction method of this embodiment, starting from the starting node of the directed graph, the number of label divisions is set for each edge set of each node, for example, for each number of edges. Decide and divide the bit string that composes the label of each side of the set of edges emanating from the node according to the number of divisions,
The edges having the plurality of divided bit strings as labels are reconfigured into a structure in which they are connected in series. Furthermore, the original ones are reconstructed by combining the edges with the same labels that originate from the same clause into one.

Also, a bit string constituting a label of each side of an edge set emitted from a node is divided into a structure in which edges having a plurality of divided bit strings as labels are connected in series, and the same label emitted from the same node. If the average of the number of comparisons of label search in the reconstructed edge set is smaller than the original one, the reconstructed edge is left and more or equal to the original one. In case you leave the original one. This operation is performed for all edge sets that make up the directed graph.

As a result, the reconstructed directed graph is
In an edge set of a certain clause, a directed graph including a part in which edges having a plurality of divided bit strings as labels are connected in series is provided.
The average number of comparisons is reduced in a portion in which edges having a plurality of divided bit strings as labels are connected in series as compared with the original edge set. Therefore, the average number of comparisons is reduced even when looking at the entire directed graph. For this reason,
When the data structure of the network is expressed by the reconstructed directed graph to perform the search, the directed graph has a structure in which the processing speed for comparison is increased.

[0048]

As described above, according to the directed graph reconstruction method of the present invention, a predetermined number of label divisions is set for each depth from the start node of the directed graph, and the directed graph to be reconstructed is determined. Then, the number of label divisions divides the bit string that constitutes the label of each side of the side set originating from the node. Then, it is converted into a sub-directed graph group in which the edges having the respective divided bit strings as labels are connected in series. Here, with respect to the converted sub-directed graph group, edges having the same label, which are emitted from the same clause, are further combined into one, and reconstructed into a directed graph including the sub-directed graph group.

As a result, the reconstructed directed graph is
Regarding the sub-directed graph group of the element, the label of each edge of the sub-directed graph group is divided into bit strings that compose the label before reconstruction, and the labels of the same bit string are grouped by the division unit to label one edge. Has become.
For this reason, the number of times the labels of the edges of the sub-directed graph group are compared can be as small as the number of labels of the edges that are collected. Therefore, when the network data structure is represented by the reconstructed directed graph and a search is performed, a directed graph having a structure in which the processing speed for comparison is increased can be realized.

[Brief description of drawings]

FIG. 1 is a PAD diagram illustrating a processing flow of a directed graph reconstruction method of the present invention,

FIG. 2 is a diagram illustrating a notation of a directed graph according to the present embodiment,

FIG. 3 is a diagram for explaining label comparison when a bit string of edge labels is not divided;

FIG. 4 is a diagram for explaining label comparison when a bit string of edge labels is divided into two;

FIG. 5 is a diagram for explaining label comparison when a bit string of edge labels is divided into four.

[Explanation of symbols]

11 to 18 ... PAD processing block, 20 ... Graph notation, 21 ... Section, 22 ... Side, 23 ... Label, 24 ... Table notation, 25 ... Side rectangular block.

Claims (2)

[Claims] 1. A predetermined number of label divisions is determined for each depth from a start node of a directed graph, and the bit sequence that constitutes a label of each side of an edge set originating from the node is divided by the number of label divisions and divided. Converted to a sub-directed graph group in which the edges having the respective bit strings as labels are connected in series, and the converted sub-directed graph groups are merged into edges having the same label, which are emitted from the same clause, to form a sub-directed graph group. A directed graph reconstruction method characterized by reconstructing a directed graph. 2. A bit string constituting a label of each edge of an edge set emitted from a node is divided by a predetermined number of label divisions, and is converted into a sub-directed graph group in which edges each having the divided bit string as a label are connected in series. , For the transformed sub-directed graph group, the edges with the same label that originate from the same clause are combined into one, and the sub-directed graph group is reconstructed. For the reconstructed sub-directed graph group, the average value of the number of comparisons in the edge set. Is smaller than the original digraph before conversion, and if the average number of comparisons in the edge set is less than the digraph before conversion, the reconstructed sub-directed graph group is left and the average value of the original digraph is If the number of comparisons in the edge set is greater than or equal to the average value, the sub-directed graph group is discarded, the original directed graph is retained, and the directed graph is reconstructed. Digraph reconstruction method which is characterized in that.