Document retrieval system

• US 5,168,565 A
• Filed: 01/13/1989
• Issued: 12/01/1992
• Est. Priority Date: 01/20/1988
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Morita, Tetsuya
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Von Buhr, Maria N.
• Application Number:
  US07/296,769
• Time in Patent Office: 1,418 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A document retrieval system employs a keyword connection table which contains relation information of keyword connections respectively coupling two arbitrary keywords which are used for retrieving registered documents. The relation information at least includes a relation name and a relationship describing the relation between the two arbitrary keywords. The relation information may dynamically change depending on a frequency of use of the keywords, that is, by a learning function.

Claims

1. A document retrieval system for retrieving one or more registered documents from a document database responsive to designated retrieval conditions including one or more designated keywords, said document retrieval system comprising:

(a) inverted file generating means supplied with the documents and keywords for generating an inverted file which indicates a relation between the keywords and each of the documents;

(b) table generating means supplied with the keywords for generating a keyword connection table containing keyword connections which describe relations between two arbitrary keywords in said inverted file, said keyword connection table containing relation information, the relation information including at least (1) a relation name and (2) a value of a relationship of the keyword connections, the value of the relationship indicating an amplitude of the relations between the two arbitrary keywords, the amplitudes of the relations between the two arbitrary keywords being dependent on whether the two arbitrary keywords are (1) directly coupled by a direct keyword connection or (2) are coupled indirectly by an indirect keyword connection through one or more keywords other than said two arbitrary keywords, the values of the relationships contained in said keyword connection table dynamically changing depending on (1) the direct keyword connection each time a document is registered in a storage means and (2) the indirect keyword connection;

(c) said storage means, said storage means for storing said inverted file, said keyword connection table, the keywords and the documents as registered documents, in a form of the document database;

(d) designating means for designating retrieval conditions including one or more designated keywords, said retrieval conditions determining one or more of said registered documents to be retrieved from said storage means;

(e) selecting means for looking up said keyword connection table by use of one or more of designated keywords and referring to said inverted file so as to select said one or more registered documents which satisfy said retrieval conditions, said selecting means including;

(1) a request processor for processing requests including a document retrieval request from said designating means;

(2) a first calculation part coupled to said storage means for calculating a relevance of keywords which indicate the amplitude of a relation between (1) a group of designated keywords from said designating means and (2) each of the keywords registered in said storage means, in response to the document retrieval request processed by said request processor;

(3) a second calculation part coupled to said storage means for calculating a relevance of text which indicates the amplitude of a relation between (1) the group of designated keywords from said designating means and (2) each of the documents registered in said storage means, in response to the document retrieval request processed in said request processor, said second calculation part calculating the relevance of text by (1) obtaining a sum of the values of the keyword connections between (i) the designated keywords and (ii) the keywords registered in said storage means, and (2) normalizing said sum; and

(4) a display controller, coupled to said first and second calculation parts, for providing information including the registered documents from said storage means to an output means, depending on calculation results obtained in said first and second calculation parts; and

(f) said output means, said output means coupled to said selecting means for outputting said one or more registered documents selected by said selecting means.

2. The document retrieval system as claimed in claim 1, wherein the table generation means includes means for dynamically changing the relation information contained in said keyword connection table from initial values depending on a frequency of use of the keywords.

3. The document retrieval system as claimed in claim 1 further comprising:

a sorter for sorting the calculation results which are supplied to said display controller from said first and second calculation parts, said sorter sorting the calculation results in a sequence dependent on values of the relationships between the designated keywords and the keywords registered in said storage means.

4. The document system as claimed in claim 3 wherein said sorter and said controller include means to cooperate, responsive to a garbage collection request processed in said request processor, to cause a garbage collection function, said garbage collection function including:

deleting from said storage means those keywords which have keyword connections such that (1) a sum of the values of the relationships with other keywords, (2) a maximum value of the values of the relationships with other keywords or (3) an average value of the values of the relationships with other keywords, is less than a predetermined threshold value.

5. The document retrieval system as claimed in claim 1 wherein:

said output means includes a display device.

6. The document retrieval system as claimed in claim 1 wherein the table generating means includes means for clusterizing a plurality of keywords and forming the keyword connections into a complete graph.

7. A document retrieval system for retrieving one or more registered documents from a document database responsive to designated retrieval conditions including one or more designated keywords, said document retrieval system comprising:

(a) inverted file generating means supplied with the documents and keywords for generating an inverted file which indicates a relation between the keywords and each of the documents;

(b) table generating means supplied with the keywords for generating a keyword connection table containing keyword connections which describe relations between two arbitrary keywords in said inverted file, said keyword connection table containing relation information, the relation information including at least (1) a relation name and (2) a value of a relationship of the keyword connections, the value of the relationship indicating an amplitude of the relations between the two arbitrary keywords, the amplitudes of the relations between the two arbitrary keywords being dependent on whether the two arbitrary keywords are (1) directly coupled by a direct keyword connection or (2) are coupled indirectly by an indirect keyword connection through one or more keywords other than said two arbitrary keywords, the values of the relationships contained in said keyword connection table dynamically changing depending on (1) the direct keyword connection each time a document is registered in a storage means and (2) the indirect keyword connection;

(c) said storage means, said storage means for storing said inverted file, said keyword connection table, the keywords and the documents as registered documents, in a form of the document database;

(d) designating means for designating retrieval conditions including one or more designated keywords, said retrieval conditions determining one or more of said registered documents to be retrieved from said storage means;

(e) selecting means for looking up said keyword connection table by use of one or more of designated keywords and referring to said inverted file so as to select said one or more registered documents which satisfy said retrieval conditions, said selecting means including;

(1) a request processor for processing request including a document retrieval request from said designating means;

(2) a first calculation part coupled to said storage means for calculating a relevance of keywords which indicate the amplitude of a relation between (1) a group of designated keywords from said designating means and (2) each of the keywords registered in said storage means, in response to the document retrieval request processed by said request processor;

(3) a second calculation part coupled to said storage means for calculating a relevance of text which indicates the amplitude of a relation between (1) the group of designated keywords from said designating means and (2) each of the documents registered in said storage means, in response to the document retrieval request processed in said request processor, said second calculation part calculating the relevance of text by (1) obtaining a sum of the values of the keyword connections between (i) the designated keywords and (ii) the keywords registered in said storage means, and (2l ) normalizing said sum; and

(4) a display controller, coupled to said first and second calculation parts, for providing information including the registered documents from said storage means to an output means, depending on calculation results obtained in said first and second calculation parts; and

(f) said output means, said output means coupled to said selecting means for outputting said one or more registered documents selected by said selecting means;

wherein;

(A) the amplitude of the relation between the two arbitrary keywords is dependent on whether;

(1) the two arbitrary keywords are directly coupled by a direct keyword connection or

(2) coupled indirectly by an indirect keyword connection through one or a plurality of keywords other than said two arbitrary keywords;

(B) the value of a relationship K_REL [K_p, K_q ] of a keyword connection (p, q) between two arbitrary keywords K_p and K_q is defined as

space="preserve" listing-type="equation">K.sub.REL [K.sub.p, K.sub.q ]=f[S.sub.ij, N.sub.ij, p, q]

by use of a relation name N_ij and a relationship value S_ij of a keyword connection (i, j)ε

UC_ALL between keywords K_i and K_j existing in a keyword layer;

wherein;

(1) UC_ALL denotes a set of keyword connections between the keywords K_i and K_j in the keyword layer; and

(2) K_p, K_q, K_i and K_j respectively denote keywords p, q, i and j;

(C) the function f[S_ij, N_ij, p, q] is equal to S_ij xA_MP [N_ij ] when a direct keyword connection exists between the two keywords K_p and K_q, where A_MP [N_ij ] denotes a weighting coefficient which varies depending on the relation name; and

(D) the function f[S_ij, N_ij, p, q] is equal to ##EQU5## when no direct keyword connection exists between the two keywords K_p and K_q but one or more indirect keyword connections exist between the two keywords K_p and K_q, wherein;

(1) C₁ through C_n denote numbers of indirect keyword connections;

(2) UC_k denotes a set of direct keyword connections constituting indirect keyword connections C_k ;

(3) Σ

denotes a sum total of the direct keyword connections (i, j) included in UC_k ; and

(4) MIN denotes a minimum value of the relationship values of the n indirect keyword connections C₁ through C_n.

8. The document retrieval system as claimed in claim 7, wherein:

the function f[S_ij, N_ij, p, q]=0 when no direct keyword connection exists between the two keywords K_p and K_q and no indirect keyword connection exists between the two keywords K_p and K_q.

9. The document retrieval system as claimed in claim 7, wherein:

(a) values of the relationships between two arbitrary keywords contained in said keyword connection table further dynamically change, depending on a frequency of use of the keywords in the calculation of the relevance of text;

(b) a learning coefficient is added to the value of the relationship between two arbitrary keywords depending on the frequency of use of the keywords;

(c) the relation information contained in said keyword connection table is renewed every time the registered document is retrieved, the renewing of said keyword connection table including an addition of new relation information of a new keyword connection; and

(d) said table generating means generates a keyword connection table which contains relation information including at least (1) a relation name and (2) a value of a relationship of the keyword connection, the value of the relationship of the keyword connection indicating an amplitude of the relation between the two arbitrary keywords, said table generating means assigning (1) a predetermined relation name to the relation name and (2) a predetermined value to the relationship of said keyword connection.