COMPUTER PRODUCT, INFORMATION RETRIEVING APPARATUS, AND INFORMATION RETRIEVING METHOD

• US 20100005058A1
• Filed: 09/15/2009
• Published: 01/07/2010
• Est. Priority Date: 03/27/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Asai, Tatsuya, Okamoto, Seishi, Inakoshi, Hiroya, TAGO, Shinichiro
• Granted Patent: US 8,190,632 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A computer-readable recording medium stores therein an information retrieving program that causes a computer to execute acquiring a document to be searched and having a hierarchical structure; generating a path schema related to the acquired document; receiving input of a retrieval keyword, a retrieval condition for the retrieval keyword, and a retrieval equation specifying a retrieval range for the retrieval keyword; generating a single automaton that includes a hierarchy retrieval automaton that retrieves a hierarchy of the generated path schema and a hit keyword retrieval automaton that retrieves a hit keyword satisfying the retrieval condition, the single automaton making state transition between a hit hierarchical node where the hit keyword in the hierarchy retrieval automaton is present and a set of nodes representing the hit keyword; retrieving, from the document and using the single automaton, the hit keyword within the retrieval range; and outputting a retrieval result.

Claims

1. A computer-readable recording medium storing therein an information retrieving program that causes a computer to execute:

acquiring a document to be searched and having a hierarchical structure;

generating a path schema related to the acquired document;

receiving input of a retrieval keyword, a retrieval condition for the retrieval keyword, and a retrieval equation specifying a retrieval range for the retrieval keyword;

generating a single automaton that includes a hierarchy retrieval automaton that retrieves a hierarchy of the generated path schema and a hit keyword retrieval automaton that retrieves a hit keyword satisfying the input retrieval condition for the retrieval keyword, the single automaton making state transition between a hit hierarchical node at which the hit keyword in the hierarchy retrieval automaton is present and a set of nodes representing the hit keyword;

retrieving, from the document and using the generated single automaton, the hit keyword within the retrieval range; and

outputting a retrieval result obtained at the retrieving.

2. The computer-readable recording medium according to claim 1, wherein the hierarchy retrieval automaton has a node representing a start symbol of a start tag between a superior hierarchical node as a transition origin and a subordinate hierarchical node as a transition destination for the superior hierarchical node, and if the start symbol is given when state transition has been made to the superior hierarchical node, the hierarchy retrieval automaton makes state transition to the node representing the start symbol.

3. The computer-readable recording medium according to claim 2, wherein the hierarchy retrieval automaton has a series of nodes representing the hierarchical name of the subordinate hierarchical node between the node representing the start symbol and the subordinate hierarchical node, and if a character string is given when state transition has been made to the node representing the start symbol, the hierarchy retrieval automaton makes state transition to the series of nodes until a hit-missing character appears.

4. The computer-readable recording medium according to claim 2 and storing therein the information retrieving program that causes the computer to further execute:

converting the hierarchical name of each hierarchical node making up the path schema into a unique character string, wherein

the generating of the single automaton includes generating the single automaton by using the converted unique character string to form the hierarchy retrieval automaton, and

the hierarchy retrieval automaton has a series of nodes between the node representing the start symbol and the subordinate hierarchical node, and if a character string is given when state transition has been made to the node representing the start symbol, the hierarchy retrieval automaton makes state transition to the series of nodes until a hit-missing character appears, the series of nodes representing the unique character string converted from the hierarchical name of the subordinate hierarchical node.

5. The computer-readable recording medium according to claim 3, wherein the hierarchy retrieval automaton makes state transition to the superior hierarchical node, when a hit-missing character appears.

6. The computer-readable recording medium according to claim 3, wherein the hierarchy retrieval automaton makes state transition to the subordinate hierarchical node, if an end symbol of the start tag is given when state transition has been made to an end node of the series of nodes.

7. The computer-readable recording medium according to claim 1, wherein the hierarchy retrieval automaton has a node representing a start symbol of an end tag between a subordinate hierarchical node as a transition origin and a superior hierarchical node as a transition destination for the subordinate hierarchical node, and if the start symbol is given when state transition has been made to the subordinate hierarchical node, the hierarchy retrieval automaton makes state transition to the node representing the start symbol.

8. The computer-readable recording medium according to claim 6, wherein

the hierarchy retrieval automaton has a series of nodes representing the hierarchical name of the subordinate hierarchical node between the node representing the start symbol and the superior hierarchical node, and if a character string is given when state transition has been made to the node representing the start symbol, the hierarchy retrieval automaton makes state transition to the series of nodes until a hit-missing character appears.

9. The computer-readable recording medium according to claim 7 and storing therein the information retrieving program that causes the computer to further execute:

converting a hierarchical name in the document into a unique character string, wherein

the generating of the single automaton includes generating the single automaton by using the converted unique character string to form the hierarchy retrieval automaton, and

the hierarchy retrieval automaton has a series of nodes between the node representing the start symbol and the superior hierarchical node, and if a character string is given when state transition has been made to the node representing the start symbol, the hierarchy retrieval automaton makes state transition to the series of nodes until a hit-missing character appears, the series of nodes representing the unique character string converted from the hierarchical name of the subordinate hierarchical node.

10. The computer-readable recording medium according to claim 4, wherein the unique character string has fewer characters than the hierarchical name has.

11. The computer-readable recording medium according to claim 8, wherein the hierarchy retrieval automaton makes state transition to the subordinate hierarchical node, when a hit-missing character appears.

12. The computer-readable recording medium according to claim 8, wherein the hierarchy retrieval automaton makes state transition to the superior hierarchical node, if an end symbol of the start tag is given when state transition has been made to the last node of the series of nodes.

13. The computer-readable recording medium according to claim 1, wherein the single automaton makes state transition to a node corresponding to the head character in the keyword retrieval automaton, if the head character of the hit keyword is given when state transition has been made to the hit hierarchical node in the hierarchy retrieval automaton.

14. The computer-readable recording medium according to claim 1, wherein the single automaton makes state transition to the hit hierarchical node, if a hit-missing character is given when state transition has been made to any node in the keyword retrieval automaton.

15. The computer-readable recording medium according to claim 1 and storing therein the information retrieving program that causes the computer to further execute:

extracting from the path schema, a partial path schema related to a retrieval range specified by the input retrieval equation, wherein

the generating of the single automaton includes generating the single automaton that includes the hierarchy retrieval automaton that retrieves a hierarchy of the extracted partial path schema and the hit keyword retrieval automaton that retrieves the hit keyword.

16. The computer-readable recording medium according to claim 1 and storing therein the information retrieving program that causes the computer to further execute:

converting a start tag representing each hierarchy in the document into a start tag that includes a hierarchy start indicator and a unique identifier assigned to each path making up the path schema, the converting further including converting an end tag representing each hierarchy in the document into an end tag that includes a hierarchy end indicator and a unique identifier assigned to each path making up the path schema, wherein

the generating of the path schema includes generating the path schema related to the document converted at the converting.

17. The computer-readable recording medium according to claim 1 and storing therein the information retrieving program that causes the computer to further execute:

converting a start tag representing each hierarchy in the document into a start tag that includes a hierarchy start indicator and a unique identifier assigned to each path making up the path schema, the converting further including converting an end tag representing each hierarchy in the document into a start tag that includes the hierarchy start indicator and the unique identifier assigned to a path whose end is a parent node to a hierarchical node specified by the hierarchical name of a start tag corresponding to the hierarchy start indicator and the end tag, wherein

the generating of the path schema includes generating the path schema related to the document converted at the converting.

18. An information retrieving apparatus comprising:

an acquiring unit that acquires a document to be searched and having a hierarchical structure;

a path schema generating unit that generates a path schema related to the acquired document;

an input unit that receives input of a retrieval keyword, a retrieval condition for the retrieval keyword, and a retrieval equation for the retrieval keyword;

an automaton generating unit that generates a single automaton that includes a hierarchy retrieval automaton that retrieves a hierarchy of the generated path schema and a hit keyword retrieval automaton that retrieves a hit keyword satisfying the input retrieval condition for the retrieval keyword, the single automaton making state transition between a hit hierarchical node at which the hit keyword in the hierarchy retrieval automaton is present and a set of nodes representing the hit keyword;

a retrieving unit that retrieves, from the document and using the generated single automaton, the hit keyword within the retrieval range; and

an output unit that outputs a retrieval result of the retrieving unit.

19. An information retrieving method comprising:

acquiring a document to be searched and having a hierarchical structure;

generating a path schema related to the acquired document;

receiving input of a retrieval keyword, a retrieval condition for the retrieval keyword, and a retrieval equation for the retrieval keyword;

generating a single automaton that includes a hierarchy retrieval automaton that retrieves a hierarchy of the generated path schema and a hit keyword retrieval automaton that retrieves a hit keyword satisfying the input retrieval condition for the retrieval keyword, the single automaton making state transition between a hit hierarchical node at which the hit keyword in the hierarchy retrieval automaton is present and a set of nodes representing the hit keyword;

retrieving, from the document and using the generated single automaton, the hit keyword within the retrieval range; and

outputting a retrieval result obtained at the retrieving.