Text search system

• US 4,823,306 A
• Filed: 08/14/1987
• Issued: 04/18/1989
• Est. Priority Date: 08/14/1987
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Barbic, Federico, Choy, David M.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/085,110
• Time in Patent Office: 613 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

In a searching for library documents that match the content of a given sequence of query words, a set of equivalent words are defined for each query word along with a corresponding word equivalence value assigned to each equivalent word. Target sequences of words in a library document which match the sequence of query words are located according to a set of matching criteria. The similarity value of each target sequence is evaluated as a function of the corresponding equivalence values of words included therein. Based upon the similarity values of its target sequences, a relevance factor is then obtained for each library document.

Claims

1. A method implemented in a data processing apparatus for retrieving from among more than one library document those matching the content of a sequence of query words, comprising the steps of:

(a) defining a set of equivalent words for each of the query words and assigning a word equivalence value to each of said equivalent words; and

(b) computing a relevance factor for a library document, comprising the steps of;

(i) locating target sequences of words in the library document that match the sequence of query words, and equivalence thereof, according to a set of matching criteria;

(ii) evaluating similarity values of said target sequences of words, each similarity value being evaluated as a function of the equivalence values of words included in the corresponding target sequence; and

(iii) said relevance factor being computed as a function of the similarity values of its target sequences.

2. A method according to claim 1 wherein said function of the equivalence values in step (ii) includes a weighting factor based upon positions in said document of words in said target sequence.

3. A method according to claim 1 wherein said matching criteria include the ordering of a sequence of words in the library document with respect to the sequence of query words.

4. A method according to claim 1 wherein said matching criteria include the completeness of a match between a sequence of words in the library document and the sequence of query words.

5. A method according to claim 1 wherein said matching criteria include the span of a sequence of words in the library document that matches the sequence of query words.

6. A method according to claim 1 comprising the additional step of preselecting a subset of library documents and computing the relevancy factors only for said subset of library documents.

7. A method according to claim 1 wherein said relevance factor of a library document is the similarity value of a target sequence having the highest similarity value.

8. A method according to claim 7 further comprising the step of ranking library documents in order of their respective relevance factors.

9. In a document retrieval system storing more than one library document, an apparatus for retrieving library documents matching the content of a sequence of query words, comprising:

(a) means for storing a set of equivalent words for each of the query words, each of said equivalent words being stored with a corresponding word equivalence value;

(b) means coupled to said storage means for computing a relevance factor for a library document, comprising;

(i) first means for receiving a set of matching criteria;

(ii) second means coupled to said first means for locating target sequences of words in a library document that match the sequence of query words, and equivalence thereof, according to said matching criteria;

(iii) third means coupled to said second means for evaluating similarity values of said target sequences of words, each similarity value being evaluated as a function of the equivalence values of words included in the corresponding target sequence; and

(iv) fourth means receiving said similarity values for computing said relevance factor.

10. The apparatus as in claim 9 wherein said function is said third means includes a weighting factor based upon positions in said document of words in said target sequence.

12. The apparatus as in claim 9 wherein said matching criteria include the completeness of a match between a sequence of words in the library document and the sequence of query words.

13. The apparatus as in claim 9 wherein said matching criteria include the span of a sequence of words in the library document that matches the sequence of query words.

14. The apparatus as in claim 9 wherein said relevance factor is the similarity value of a target sequence have the maximum similarity value.

15. The apparatus as in claim 14 further comprising means coupled to said fourth means for ranking library documents in order of their respective relevance factors.

16. The apparatus as in claim 9 further comprising means of preselecting a subset of library documents.

11. The apparatus as in 9 wherein said matching criteria include the ordering of a sequence of words in the library document with respect to the sequence of query words.

17. A method implemented in a data processing apparatus for retrieving from among more than one library document those matching the content of a sequence of query words, comprising the steps of:

defining a set of equivalent words for each query words and each of said equivalent words being assigned a word equivalence value; and

computing a relevance factor for a library document, comprising the steps of;

(a) locating target sequences of words in the library document that match the specified sequence of query words according to a set of matching criteria, said matching criteria comprising;

(i) the ordering of a sequence of words in the library document with respect to the specified sequence of query words;

(ii) the completeness of a match between a sequence of words in the library document and the specified sequence of query words; and

(iii) the span of a sequence of words in the library document that matches the specified sequence of query words;

(b) evaluating similarity values of said target sequences of words, each similarity value being evaluated as a function of the equivalence values of words included in the corresponding target sequence; and

(c) said relevance factor being computed as a function of the similarity values of its target sequences.

18. A method according to claim 17, wherein a similarity value S_xyz is being evaluated according to the equation:

##EQU7## where L1 represents the target sequence;

L2 represents the sequence of query words;

x represents said ordering matching criterion;

y represents said completeness matching criterion;

z represents said span matching criterion; and

##EQU8##

19. A method according to claim 17 wherein said relevance factor of a library document is the similarity value of a target sequence having the maximum similarity value.

20. A method according to claim 17 further comprising the step of ranking library documents in order of their respective relevance factors.