JP5482165B2 - Program and information extraction device - Google Patents

Description

  The present invention relates to a program and an information extraction device.

  There is a technique called data mining that analyzes a large amount of data and extracts significant information. In such data mining, if the amount of data handled increases, the calculation cost increases exponentially, so redundant processing is omitted. For example, the following Patent Document 1 describes a pruning process in which a redundant pattern is omitted.

  In addition, with regard to sub-tree mining for extracting a tree structure pattern that frequently appears in a tree structure information (tree data) group such as XML, Induced Subtree Mining that obtains a tree structure pattern in which the parent-child relationship of elements exactly matches, When a common element can be added to the end of the tree structure pattern from the already searched range when extending the pattern (that is, when a new leaf node can be added), the tree structure pattern extension search process is performed. Some are omitted.

Japanese Patent Laid-Open No. 10-301942

  Extracted as the same tree structure pattern if the ancestor-descendant relationship is maintained even if the parent-child relationship between elements is not strictly maintained. In Embedded Subtree Mining, elements are added not only at the end of the tree structure pattern but also inside It is necessary to determine whether or not a redundant search is caused in consideration of the case where the search is performed.

  An object of the present invention is a program for determining a tree structure pattern that causes a redundant search when an element is added to the tree structure pattern in the process of searching while expanding the tree structure pattern that frequently appears in a plurality of tree structure information And providing an information extraction device.

  In order to achieve the above object, according to the first aspect of the present invention, a computer holds a tree structure pattern that is commonly included in a predetermined number of tree structure information among a plurality of tree structure information. An extension part for selecting a path based on a predetermined condition from a tree structure pattern held in the holding means and adding a component to the selected path to expand the tree structure pattern And selecting means for selecting any element included in the tree structure pattern, and the plurality of tree structure information based on the inspection target element and the extension location in the tree structure pattern A common pattern in which an element is added between the inspection target element and its child element in the tree structure pattern is detected from the inspection range determined for each of In case a program for functioning as a determination means not to perform a search pattern that adds a new element to the extension portion of the pattern of the tree structure.

  Further, the invention according to claim 2 is the program according to claim 1, wherein the determination means determines whether the inspection target element and its one child element in the pattern of the tree structure from the determined inspection range. When a common pattern with elements added between them is detected, it is determined not to search for a pattern in which a new element is added to the decompressed portion of the tree structure pattern.

  According to a third aspect of the present invention, in the program according to the first or second aspect, the determination means includes the inspection target element and the plurality of child elements in the tree structure pattern from the predetermined inspection range. When a common pattern in which an element connected to each of the patterns is added is detected, it is determined not to search for a pattern in which a new element is added to the extension portion of the tree structure pattern. .

  According to a fourth aspect of the present invention, in the program according to any one of the first to third aspects, the determination means further adds a new element to the inspection target element in the tree structure pattern from the determined inspection range. When a common pattern to which a child element is added is detected, it is determined not to search for a pattern in which a new element is added to the extension location of the tree structure pattern.

  The invention according to claim 5 is the program according to any one of claims 1 to 4, wherein the computer is further based on the element to be inspected and the extension location in the pattern of the tree structure. A program for causing each of a plurality of tree structure information to function as a setting unit that sets a reference position for detecting candidate elements added between the inspection target element and its child elements.

  The invention according to claim 6 is the program according to any one of claims 1 to 5, wherein the computer further adds a new element to the extension portion of the tree structure pattern by the determination unit. When it is determined that the expansion pattern is to be searched, search means for searching for the extension pattern candidate from the plurality of tree structure information, and a tree generated based on the extension pattern candidate searched by the search means A function for holding a structure pattern in the holding means; and a function for recursively executing a process of expanding the tree structure pattern held in the holding means by the selection means, the determination means, and the search means. It is a program.

  According to a seventh aspect of the present invention, there is provided a holding means for holding a tree structure pattern included in common to a predetermined number of tree structure information from among a plurality of tree structure information, and the holding means holding the tree structure pattern. Selecting a path based on a predetermined condition from the tree-structured pattern selected, and selecting means for adding an element to the selected path and selecting an extension location for extending the tree-structure pattern; Any element included in the tree structure pattern is an inspection target element, and from the inspection range determined for each of the plurality of tree structure information based on the inspection target element and the extension location in the tree structure pattern, The expansion of the tree structure pattern when a common pattern is detected in which an element is added between the inspection target element and its child elements in the tree structure pattern A determination unit not to perform the search of the added pattern a new element at an information extraction device which comprises a.

  According to the first and seventh aspects of the invention, a redundant search is caused when an element is added to the tree structure pattern in the process of searching while expanding the tree structure pattern that frequently appears in a plurality of tree structure information. A tree structure pattern can be determined.

  According to the second aspect of the present invention, the extended search can be omitted when the pattern to be searched overlaps with the pattern in which the element is added between the inspection target element and its one child element in the tree structure pattern.

  According to the third aspect of the present invention, the extension search is omitted when the pattern to which the branch element provided between the inspection target element and the plurality of child elements in the tree structure pattern is added overlaps with the searched pattern. it can.

  According to the fourth aspect of the present invention, the extension search can be omitted when the pattern to be searched overlaps with the pattern in which a new child element is added to the inspection target element in the tree structure pattern.

  According to the fifth aspect of the present invention, it is possible to improve the efficiency of determining whether or not the search is redundant as compared with the case where the present configuration is not provided.

  According to the sixth aspect of the present invention, it is possible to reduce the number of steps of redundant decompression search processing when decompressing so that a tree structure pattern that frequently appears in a plurality of tree structure information has more elements.

It is a functional block diagram of the information extraction device concerning this embodiment. It is the figure which showed an example of tree data. It is the figure which showed an example of the tree structure pattern searched. It is the figure which showed an example of the expansion | extension location set on RMP. It is the figure which showed the test | inspection range regarding a test object node in a 1st redundancy determination part. It is the figure which showed the test | inspection range regarding a test object node in a 2nd redundancy determination part. It is a figure which shows an example of the tree data in which both the 1 edge upper node and the branch point node are contained. It is the figure which showed an example of the total reference position set when there is an inspection object node in the upper part of the extension part. It is the figure which showed an example of the total reference | standard position set when an expansion | extension location and a test object node correspond. It is the figure which showed an example of the total reference position set when an inspection object node is located in the lower part of an extension part. It is the figure which showed the example of the pattern searched from tree data. It is a flowchart of an information extraction process. It is a flowchart of an expansion search process. It is a flowchart of a redundancy determination process.

  Hereinafter, embodiments for carrying out the present invention (hereinafter referred to as embodiments) will be described with reference to the drawings.

  FIG. 1 shows a functional block diagram of an information extraction apparatus 10 according to the present embodiment. As shown in FIG. 1, the information extraction apparatus 10 includes a tree data holding unit 12, a pattern candidate searching unit 14, a pattern information holding unit 16, a pattern appearance information holding unit 18, a pattern expansion location selection unit 20, an extended pattern existence range. A management unit 22 and a redundancy determination unit 24 are included. The functions of the above-described units are such that a computer having a control unit such as a CPU, a storage unit such as a memory, and an input / output unit that transmits and receives data to and from an external device reads a program stored in a computer-readable information storage medium. It may be realized by executing. The program may be supplied to the information extraction apparatus 10 that is a computer by an information storage medium, or may be supplied via data communication means such as the Internet. Hereinafter, functions of each unit included in the information extraction apparatus 10 will be described in detail.

  The tree data holding unit 12 includes a storage device such as a semiconductor memory or a magnetic disk device, and holds a plurality of tree structure information (hereinafter, tree data). Tree data is data in which a plurality of elements (hereinafter, nodes) are connected based on their parent-child relationships. In the tree data, the node located at the apex is the root node, the node located at the end is the leaf node, the line connecting the nodes is the edge, the path from the root node to the leaf node is the path, and each node corresponds to each node The target information is called a label. The tree data held in the tree data holding unit 12 may be input from a user via an input device (not shown), or may be acquired by data transfer from another device.

  FIG. 2 shows an example of tree data held in the tree data holding unit 12. The tree data shown in FIG. 2 is a part of a plurality of tree data held in the tree data holding unit 12. In the present embodiment, a process of extracting a tree structure pattern that satisfies a predetermined condition from among a plurality of tree data held in the tree data holding unit 12 is performed. The above condition is, for example, a tree structure pattern that is common to a predetermined number (or percentage) of tree data among a plurality of tree data and that has an identical ancestor-descendant relationship (that is, using Embedded Subtree Mining). Good. The tree data to be extracted from the tree structure pattern may be all of the tree data held in the tree data holding unit 12, or a part thereof may be selected.

  The pattern candidate search unit 14 searches for candidates that match a specified pattern from among a plurality of tree data held in the tree data holding unit 12. Specifically, the pattern candidate search unit 14 searches each tree data for candidates corresponding to a pattern obtained by adding an element to the tree structure pattern obtained at the time of processing, and the searched candidates are determined in advance. If a predetermined condition (for example, a predetermined number or more) is satisfied, search processing for adding the candidate to the tree structure pattern is performed. Note that the pattern candidate search unit 14 may search for an extension pattern by searching a node that is a candidate for an extension location from each tree data. The pattern candidate search unit 14 may start the search process based on the initial pattern when there is an initial pattern specified for a tree structure pattern that frequently appears in each tree data. If there is no pattern, the search process may be started with one node as an initial pattern.

  The pattern information holding unit 16 holds the tree structure pattern searched by the pattern candidate search unit 14. The pattern information holding unit 16 may hold all the tree structure patterns sequentially searched by the pattern candidate searching unit 14, or may selectively hold a part thereof.

  The pattern appearance information holding unit 18 holds pattern appearance information indicating where the tree structure pattern searched by the pattern candidate search unit 14 appears in each tree data held in the tree data holding unit 12. .

  The pattern expansion location selection unit 20 selects a location to be expanded by adding a node to the tree structure pattern held in the pattern information holding unit 16. In this embodiment, the tree structure pattern is searched with depth priority (depth priority search), and the pattern expansion location selection unit 20 performs the right end path (hereinafter referred to as RMP (Right Most Path) of the tree structure pattern to be expanded. )) May be selected, and the selected RMP node or edge may be selected as an extension location to which a new node is to be added. Depth-first search is a path that follows the path from the node that starts the search, and in a node that branches into multiple paths, the left node is selected and searched until it reaches the leaf node. This is a search that repeats the process of returning to the branch point with another path, following the other path from the branch point, and again selecting the left node at the branch point and searching for the leaf node. is there.

  FIG. 3 shows an example of a tree structure pattern to be searched, and FIG. 4 shows an example of a decompression location set on the RMP. FIG. 3 is an example of a tree structure pattern that is commonly included in the tree data, and the rightmost path is RMP.

  As shown in FIG. 4, the addition of a node to the RMP may be added as a new child node of each node of the RMP as shown in FIG. 4A, or as shown in FIG. It is good also as what includes a node on the edge between nodes.

  The expansion pattern existence range management unit 22 manages the existence range on the tree data in which a partial tree structure in which a node is added to the expansion point selected by the pattern expansion point selection unit 20 exists. The expanded pattern existence range management unit 22 may identify and manage the existence range based on the appearance location on the tree data of the tree structure pattern before adding the expansion node. Information managed by the extension pattern existence range management unit 22 may be used when narrowing down the extension pattern existence range when an extension location is selected, and also when searching for extension pattern candidates. .

  The redundancy determination unit 24 includes an inspection target node selection unit 26, a first redundancy determination unit 28, a second redundancy determination unit 30, a third redundancy determination unit 32, and a total reference position setting unit 34. It is determined whether or not a pattern in which a node is added to the extension location selected by the selection unit 20 is a redundant search. When it is determined that the search is redundant, the search process for the pattern is omitted. Details of the determination process performed by the redundancy determination unit 24 will be described below.

  The inspection target node selection unit 26 sequentially selects one of the nodes included in the pattern in which the decompression location is selected as the inspection target node. The selection order of the inspection target nodes by the inspection target node selection unit 26 is not particularly limited. For example, the inspection target node selection unit 26 may select the inspection target nodes sequentially from the upper node of the left path, or may be a sibling node, a parent node, and a child node at the decompression point It is good also as selecting in order from the node in the circumference | surroundings. By using the latter method, inspecting from a node around the extended part where the same label as the extended part is likely to appear in data whose structure is defined, such as XML data, compared to the case of inspecting from other parts This improves the efficiency of the pruning process.

  The first redundancy determining unit 28 determines whether or not a pattern obtained by adding a new leaf node to the inspection target node selected by the inspection target node selecting unit 26 is a redundant search. Specifically, the first redundancy determining unit 28 determines whether a pattern search has already been performed based on the pattern expansion location and the inspection target node, or a search range for other patterns including the pattern. If there is a new leaf node having a common label for the node to be inspected, it is determined that there is redundancy.

  FIG. 5 shows the inspection range related to the inspection target node in the first redundancy determination unit 28. FIG. 5 shows an example in which the inspection target node in the pattern is associated with its child node on the tree data. As shown in FIG. 5, as the inspection range for the inspection target node, first, an area on the left side of each child node connected to the inspection target node is selected, whether the inspection target node is in the RMP, and an extension location The region on the right side of the rightmost child node is also selected as the inspection range according to the positional relationship between the node and the inspection target node. When a node having the same label is detected from the inspection range defined for each tree data, it is determined that there is redundancy. The first redundancy determination unit 28 may also determine whether or not a pattern obtained by adding a new root node to the root node is a redundant search when the node to be inspected is a root node. .

  The second redundancy determining unit 30 performs a search in which a pattern in which a new node (upper edge node) is added between the inspection target node selected by the inspection target node selection unit 26 and its one child node is redundant. It is determined whether or not. Specifically, the second redundancy determining unit 30 determines whether a pattern search has already been performed based on the pattern expansion location and the inspection target node, or a search range for other patterns including the pattern. If there is a new node on one edge having a common label for the node to be inspected, it is determined that there is redundancy. Note that when there is no child node in the node to be inspected, there is no node on one edge, so the redundancy determination by the second redundancy determination unit 30 may be omitted.

  FIG. 6 shows the inspection range related to the inspection target node in the second redundancy determining unit 30. FIG. 6 shows an example in which the inspection target node in the pattern and its child node are associated on the tree data. As shown in FIG. 6, the inspection range related to the inspection target node is an area between the inspection target node and its child nodes. When a node having the same label is detected from the inspection range defined for each tree data, it is determined that there is redundancy. However, as illustrated in FIG. 7, the inspection target node has a plurality of child nodes, and a node that is a branch point node of the inspection target node and some of the child nodes does not correspond to a node on one edge. These nodes are excluded from label detection targets.

  The third redundancy determination unit 32 has a pattern in which a new node (branch point node) connected to each node is added between the inspection target node selected by the inspection target node selection unit 26 and the plurality of child nodes. It is determined whether or not the search is redundant. Specifically, the third redundancy determination unit 32 determines whether the pattern search has already been performed based on the pattern expansion location and the inspection target node, or the search range of other patterns including the pattern. If there is a new branch point node having a common label for the node to be inspected in a certain range, it is determined that there is redundancy. The branch point node corresponds to the node La in FIG. 7, and the node La becomes the inspection range. Note that when there are no plurality of child nodes in the node to be inspected, there is no branch point node, so the redundancy determination by the third redundancy determination unit 32 may be omitted.

  Note that the third redundancy determining unit 32 determines the inspection range for each possible combination of child nodes of the inspection target node, and inspects the existence of a branch point node having a common label.

  The total reference position setting unit 34 uses the new leaf node, one edge, and the common label when determining whether or not the pattern obtained by extending the extension part is a redundant search based on the inspection target node and the extension part. A position (aggregation reference position) on the tree data serving as a reference for counting the presence of the upper node or the branch point node is set. The tabulation reference position setting unit 34 sets the tabulation reference position based on the inspection target node and the extension location when there are a plurality of nodes corresponding to the extension location of the pattern on the tree data. For example, the total reference position may be a position selected in accordance with the relationship between the inspection target node, the extension location, and the child node of the inspection target pattern from the path where the inspection target node exists. A specific example of setting the total reference position will be described below.

  FIG. 8 shows an example of the total reference position that is set when there is a node to be inspected at the upper part of the extension part. As shown in FIG. 8A, when there are a plurality of nodes corresponding to the expansion locations on the tree data, and there are also a plurality of appearance locations of the nodes to be inspected, the node is at the top of the nodes that can be the aggregation reference position. A thing may be set as the total reference position.

  Also, as shown in FIG. 8B, when there are a plurality of nodes corresponding to the expansion location on the tree data and there are a plurality of locations where the inspection target node appears on a path different from the expansion location, the expansion location The position at which the paths where the nodes to be inspected each intersect on the upper side may be set as the total reference position.

  FIG. 9 shows an example of the total reference position that is set when the extension location matches the inspection target node. As illustrated in FIG. 9, when the extension location matches the inspection target node and there are a plurality of nodes corresponding to the extension location on the tree data, the aggregation reference position is the highest position of the extension location. It may be set as

  FIG. 10 shows an example of the total reference position that is set when the inspection target node is positioned below the extended portion. As shown in FIG. 10, the aggregation reference position may be set according to the position of the child node located at a lower position among the child nodes at the expansion location on the tree data.

  The redundancy is determined by recording a flag indicating whether or not there is a common label with other tree data for the aggregation reference position set for each tree data, and there is a common label with other tree data for all the aggregation reference positions. It may be determined by determining that there is redundancy when the flag is recorded, and otherwise determining that there is no redundancy. The redundancy determination unit 24 determines that there is redundancy when any of the first to third redundancy determination units 32 determines that there is redundancy.

  The pattern candidate search unit 14 does not perform a search process for a pattern obtained by extending the extension portion when the redundancy determination unit 24 determines that the extension portion of the pattern to be processed is redundant. Search processing is performed only for patterns determined to have no redundancy. The new tree structure pattern searched based on the pattern expanded by the pattern candidate search unit 14 is stored in the pattern information holding unit 16. Then, the information extraction apparatus 10 recursively repeats the process of searching for a pattern, selecting an extension location of the searched pattern, determining the redundancy of the selected extension location, and searching for a pattern based on the extension pattern having no redundancy. Thus, a tree structure pattern having a larger number of elements is extracted.

  FIG. 11 shows an example of a pattern searched from the tree data shown in FIG. When the patterns P1 and P1 shown in FIG. 11 are already searched for in the order in which the extended patterns are searched, and the other patterns P2 to P4 are to be expanded, the following redundancy determination is performed. Is done.

  First, assuming that the label A node of the pattern P2 is the extension location and the label B node is the inspection target node, the first redundancy determination unit 28 makes the node of the label D that is a child node of the inspection target node common from the inspection range. Therefore, it is determined that the extension pattern obtained by adding a node to the extension part of the pattern P2 is a redundant search.

  Next, assuming that the node of the label C of the pattern P3 is an expanded portion and the node of the label A is a node to be inspected, the node on one edge provided between the node to be inspected and its child node K by the second redundancy determining unit 30 Since the node with the label J is found in common, it is determined that the extension pattern in which the node is added to the extension part of the pattern P3 is a redundant search.

  Further, assuming that the node of label C in pattern P4 is the extension location and the node of label A is the node to be inspected, a branch point node provided between the node to be inspected and its child nodes D and E by the third redundancy determining unit 32 Since the node with the label B is found in common, it is determined that the extension pattern in which the node is added to the extension part of the pattern P4 is a redundant search.

  Next, an example of the flow of processing performed by the information extraction device 10 will be described with reference to the flowcharts shown in FIGS. 12, 13, and 14.

  FIG. 12 is a flowchart illustrating an example of information extraction processing performed by the information extraction device 10. As shown in FIG. 12, the information extraction apparatus 10 searches for frequently appearing nodes (frequent nodes) in the tree data held in the tree data holding unit 12 (S101), and when an unprocessed frequent node remains. (S102: Y), an unprocessed frequent node is selected (S103), pattern data is created (S104), and pattern expansion search processing is performed (S105). Details of the pattern expansion search processing will be described later. When the pattern expansion search process ends, the process returns to S102, and when there are no unprocessed frequent nodes remaining (S102: N), the process ends.

  FIG. 13 is a flowchart illustrating an example of pattern expansion search processing. As shown in FIG. 13, the information extraction apparatus 10 selects an RMP from the pattern (S201), and determines whether or not there is an unprocessed decompression location on the selected RMP (S202). Here, when the information extraction apparatus 10 determines that there is an unprocessed decompression location (S202: Y), it selects one of the unprocessed decompression locations (S203) and adds a node to the decompression location. A decompression pattern redundancy determination process is performed (S204). Details of the redundancy determination process will be described later.

  When it is determined that there is redundancy in the redundancy determination process (S205: Y), the information extraction apparatus 10 records the determination result, returns to process S202, and repeats the subsequent processes. On the other hand, when it is determined by the redundancy determination process that there is no redundancy (S205: N), the information extraction apparatus 10 searches the tree data for an expansion pattern candidate in which a node is added to the expansion location (S206). ).

  If there is an unprocessed pattern candidate for the searched pattern candidate (S207: Y), the information extraction apparatus 10 selects one unprocessed pattern candidate (S208) and recursively performs the pattern expansion search process. (S209). When there is no unprocessed pattern candidate (S207: N), the information extraction apparatus 10 returns to S202 and repeats the subsequent processing. If it is determined in S202 that there is no unprocessed decompression location (S202: N), the process returns to the parent process.

  FIG. 14 shows a flowchart illustrating an example of the redundancy determination process. As shown in FIG. 14, when there is an unprocessed inspection target node from the pattern in which the decompression location is selected (S301: Y), the information extraction apparatus 10 adds one unprocessed inspection target node. Select (S302).

  The information extraction apparatus 10 determines whether or not a pattern in which a new leaf node is added to the inspection target node is a redundant search (first redundancy determination) (S303), and when it is determined that the pattern is a redundant search (S303: Y), it records that there is redundancy (S306), and returns. In addition, when the redundancy is not determined by the first redundancy determination (S303: N), the information extraction apparatus 10 determines that the pattern obtained by adding the node on one edge provided between the inspection target node and the child node is redundant. It is determined whether or not the search is to be performed (second redundancy determination) (S304). If it is determined that the search is to be redundant (S304: Y), it is recorded as being redundant (S306), and the process returns. . Furthermore, when the redundancy is not determined by the second redundancy determination (S304: N), the information extraction apparatus 10 adds a branch point node provided between the inspection target node and the plurality of child nodes. Is determined to be a redundant search (third redundancy determination) (S305), and if it is determined to be a redundant search (S304: Y), it is recorded as redundant (S306), Return. When there is no unprocessed node to be inspected (S301: N), the information extraction apparatus 10 records that there is no redundancy (S307) and returns.

  In the above redundancy determination process, the first redundancy determination to the third redundancy determination are executed in this order. However, the redundancy determination order is not limited to this. Further, in the above redundancy determination processing, unnecessary redundancy determination processing is omitted from the first redundancy determination to the third redundancy determination depending on the presence / absence of child nodes of the node to be inspected and the number of child nodes. As good as

  In the information extraction apparatus 10 according to the above-described embodiment, in the embedded subtree mining, before starting the search for the expanded pattern obtained by expanding the searched pattern, when the node is embedded in the pattern, Since it is determined whether or not the search is redundant according to the relationship and the search is not performed for the extension pattern determined to be redundant, the tree that appears more frequently in the tree data than in the case without such a configuration. The number of processing steps required to extract the structural pattern is reduced.

  The present invention is not limited to the above-described embodiment. For example, in the above-described embodiment, the decompression location is selected from the RMP, but if the pattern search algorithm is appropriately set, the leftmost path (LMP) or other It is also possible to select from the paths selected based on the above condition.

  DESCRIPTION OF SYMBOLS 10 Information extraction device, 12 Tree data holding part, 14 Pattern candidate search part, 16 Pattern information holding part, 18 Pattern appearance information holding part, 20 Pattern expansion | extension location selection part, 22 Expansion | extension pattern existence range management part, 24 Redundancy determination part , 26 inspection target node selection unit, 28 first redundancy determination unit, 30 second redundancy determination unit, 32 third redundancy determination unit, 34 total reference position setting unit.

Claims (6)

Computer
A tree structure that indicates the ancestor-descendant relationship between elements included in a predetermined number of tree structure information among a plurality of tree structure information configured by connecting a plurality of elements based on a parent-child relationship . Holding means for holding the pattern,
Extension that selects a path from a single tree structure pattern held in the holding means based on a predetermined condition and adds an element to the selected path to expand the one tree structure pattern A selection means for selecting a location,
Search means for searching for candidate elements to be added to the extension location of the one tree structure pattern from the plurality of tree structure information; and
Wherein one of the elements included in the pattern of a single tree is inspected element is determined on the basis of said extension portion and the inspection target element in the pattern of said one of the tree, is held by the holding means In the inspection range included in another tree structure pattern, when the inspection target element and its child element in the one tree structure pattern are included, and an element is included between the inspection target element and its child element , program for functioning as a determination means not to perform a search by said searching means with the extension portion of the pattern of one of the tree. The determining means is the inspection range in which the determined, said comprising one of the inspection target element in the pattern of the tree structure and its one child element contains elements between said object element and one child element that case, the program according to claim 1, wherein the determining not to perform the search by said one of said search means with said extension portion of the pattern of the tree structure. The determination means includes the inspection target element and the plurality of child elements thereof in the one tree structure pattern in the defined inspection range , and the inspection target is between the inspection target element and the plurality of child elements. claims when containing the elements to be connected to each element and the plurality of child elements, wherein the determining not to perform the search by said one of said search means with said extension portion of the pattern of the tree structure The program according to 1 or 2. Said determining means further, in the inspection range in which the determined, if the include the inspected elements in the pattern of one of the tree include child elements connected to the test target element, the pattern of said one of the tree structure the program according to any one of claims 1 to 3, with the extended portion, wherein the determining not to perform the search by said search means. The computer further,
Pattern before Symbol candidate elements to be added to the extension portion, which is searched by the search means, in advance when others above defined, the elements of the candidate one tree in the plurality of tree structure information Means for causing the holding means to hold a new tree structure pattern added to the stretched portion of
Said selecting means the pattern of the tree structure which is held by the holding means, the determining means, according to any one of claims 1 to 4 for operating the process of decompressing as a means for performing recursively by said searching means program. A tree structure that indicates the ancestor-descendant relationship between elements included in a predetermined number of tree structure information among a plurality of tree structure information configured by connecting a plurality of elements based on a parent-child relationship . Holding means for holding the pattern;
Extension that selects a path from a single tree structure pattern held in the holding means based on a predetermined condition and adds an element to the selected path to expand the one tree structure pattern A selection means for selecting a location;
Search means for searching for candidate elements to be added to the extension location of the one tree structure pattern from the plurality of tree structure information;
Wherein one of the elements included in the pattern of a single tree is inspected element is determined on the basis of said extension portion and the inspection target element in the pattern of said one of the tree, is held by the holding means When the inspection range included in another tree structure pattern includes the inspection target element and its child element in the one tree structure pattern, and an element is included between the inspection target element and its child element , a determination unit not to perform the search by the searching means with the extension portion of the pattern of one tree,
An information extraction apparatus comprising:

Images