Information search system, method and program

• US 8,171,052 B2
• Filed: 03/03/2009
• Issued: 05/01/2012
• Est. Priority Date: 03/03/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Takuma, Daisuke, Tsuboi, Yuta
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US12/396,876
• Publication Number:
  US 20090222407A1
• Time in Patent Office: 1,155 Days
• Field of Search: None
• US Class Current: 707/786
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/3344 using natural language analysis

Abstract

A system, method and computer program product for searching at high speed for documents matching a dependency pattern from document data containing a large volume of text documents. The system includes a storage device for storing, index storage means for storing in the storage device occurrence information, receiving means for receiving information, reading means for reading from the index storage means, and searching means for comparing occurrence information. The method and computer program product include the steps of storing in the storage device, receiving information, reading from the storage device, comparing occurrence information, and searching. The computer program product includes instructions to execute the steps of storing each of the plurality of document data in the storage device, storing in the storage device occurrence information.

Claims

1. An information search system for searching through a database having a plurality of document data each having a unique document ID added thereto, by use of a computer, the system comprising:

a storage device for storing the plurality of document data;

index storage means for storing in the storage device occurrence information for each word in each of the plurality of document data when each of the document data is parsed and is expressed in a form of a parse tree with a root node for bundling a plurality of sentences, the occurrence information including a document ID of the document data containing the word, a first order that indicates a sequence number of the word originating from a root node in a structural tree, and a second order that indicates a reverse sequence number of the word originating from a terminal node to the root node in the structural tree, wherein the first order sequence number decreases in value as position proximity of the word to the root node increases, and wherein the second order reverse sequence number decreases in value as position proximity of the word to the terminal node increases;

receiving means for receiving information on at least two words to be searched for;

reading means for reading from the index storage means the occurrence information on each of the words received; and

searching means for comparing occurrence information on a first word among the words received with occurrence information on a second word among the words received and for searching out a document ID of one of the two occurrence information which has the same document ID as the other occurrence information, the first order smaller than the other occurrence information, and the second order larger than the other occurrence information.

2. The information search system according to claim 1, wherein the occurrence information is sorted and listed in descending order of document frequency for each word ID.

3. The information search system according to claim 1, wherein:

the occurrence information further comprises information on a depth from the root node; and

the searching means returns the document ID of the occurrence information only when a difference in depth between the compared two kinds of occurrence information is not more than a predetermined value.

4. The information search system according to claim 3, further comprising:

specification means for specifying at least one word as a base node; and

means for reading the occurrence information on the word of the base node from the index storage means and for listing words having occurrence information which has the same document ID as a larger first order than, a smaller second order than and a depth difference not more than the predetermined value from the occurrence information on the word of the base node.

5. The information search system according to claim 4, wherein the words are listed in order of frequency of the occurrence information on the word.

6. An information search method for searching through a database having a plurality of document data each having a unique document ID added thereto, by use of a computer having a storage device, the method comprising the steps of:

storing each of the plurality of document data in the storage device in a form of a structural tree starting from a root node by parsing;

storing in the storage device occurrence information for each word in each of the plurality of document data when each of the document data is a parse tree with the root node for bundling a plurality of sentences, the occurrence information containing a document ID of the document data including the word, a first order that indicates a sequence number of the word originating from a root node in a structural tree, and a second order that indicates a reverse sequence number of the word originating from a terminal node to the root node in the structural tree, wherein the first order sequence number decreases in value as position proximity of the word to the root node increases, and wherein the second order reverse sequence number decreases in value as position proximity of the word to the terminal node increases;

receiving information on at least two words to be searched for;

reading from the storage device the occurrence information on each of the words received;

comparing occurrence information on a first word among the received words with occurrence information on a second word among the received words; and

searching out a document ID of one of the above two kinds of occurrence information which has the same document ID as the other occurrence information, the first order smaller than the other occurrence information, and the second order larger than the other occurrence information.

7. The information search method according to claim 6, wherein the occurrence information is sorted and listed in descending order of document frequency for each word ID.

8. The information search method according to claim 6, wherein:

the occurrence information further comprises information on a depth from the root node; and

in the searching step, the document ID of the occurrence

information is returned only when a difference in depth between the compared two kinds of occurrence information is not more than a predetermined value.

9. The information search method according to claim 8, further comprising the steps of:

specifying at least one word as a base node; and

reading the occurrence information on the word of the base node from the storage device and listing words having occurrence information which has the same document ID as, a larger first order than, a smaller second order than and a depth difference not more than the predetermined value from, the occurrence information on the word of the base node.

10. The information search method according to claim 9, wherein the words are listed in order of frequency of the occurrence information on the word.

11. A computer readable storage medium tangibly embodying a computer readable program code having computer readable non-transitory instructions which, when implemented, cause a computer to carry out the steps of a method for searching through a database having a plurality of document data each having a unique document ID, the method comprising:

storing each of the plurality of document data in a form of a structural tree starting from a root node by parsing;

storing occurrence information for each word in each of the plurality of document data when each of the document data is a parse tree with the root node for bundling a plurality of sentences, the occurrence information containing a document ID of the document data including the word, a first order that indicates a sequence number of the word originating from a root node in a structural tree, and a second order that indicates a reverse sequence number of the word originating from a terminal node to the root node in the structural tree,

wherein the first order sequence number decreases in value as position proximity of the word to the root node increases, and wherein the second order reverse sequence number decreases in value as position proximity of the word to the terminal node increases;

receiving information on at least two words to be searched for;

reading the occurrence information on each of the words received;

comparing occurrence information on a first word among the received words with occurrence information on a second word among the received words; and

searching out a document ID of one of the above two kinds of occurrence information which has the same document ID as the other occurrence information, the first order smaller than the other occurrence information, and the second order larger than the other occurrence information.

12. The computer readable storage medium according to claim 11, wherein the occurrence information is sorted and listed in descending order of document frequency for each word ID.

13. The computer readable storage medium according to claim 11, wherein:

the occurrence information further comprises information on a depth from the root node; and

in the searching step, the document ID of the occurrence information is returned only when a difference in depth between the compared two kinds of occurrence information is not more than a predetermined value.

14. The computer readable storage medium according to claim 13, wherein the method further comprises the steps of:

specifying at least one word as a base node; and

reading the occurrence information on the word of the base node and listing words having occurrence information which has the same document ID as a larger first order than, a smaller second order than and a depth difference not more than the predetermined value from the occurrence information on the word of the base node.

15. The computer readable storage medium according to claim 14, wherein the words are listed in order of frequency of the occurrence information on the word.