Text retrieval method and system using signature of nearby words

• US 5,542,090 A
• Filed: 07/27/1994
• Issued: 07/30/1996
• Est. Priority Date: 12/10/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Henderson, Richard D., Barbarino, Michael J.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/280,963
• Time in Patent Office: 734 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for searching a document corpus for query terms includes generating a list of document terms including a term signature for each term based upon characteristics of a number of adjacent terms. The term signatures can be generated by generating a bit vector for each term within a predetermined adjacent number of terms from each document term, such as through application of a hash function. The bit vectors can then be combined to form the term signature. The word signature alternatively can be generated using one or more morphological properties of the terms. The predetermined adjacent number of terms can be the number of search terms minus one, and may precede, follow, or both precede and follow the document term for which the term signature is generated. A search signature is generated for the query terms excluding a reference term, based upon the predetermined characteristics. The term signature of the reference term is compared with the search signature, and an indication is provided when the term signature of the reference term and the search signature match.

Claims

1. A method for retrieving relevant documents in a corpus of documents based on a search query, the method comprising the steps of:

storing the corpus of documents in a storage device;

inputting the corpus of documents and the search query on an input device;

generating an index term signature for each index term in the corpus of documents, the index term signature being based on a hash function of a predetermined number of adjacent terms adjacent to the index term;

generating a list containing the index terms in the corpus of documents, the list associating each index term with a document identifier and corresponding index term signatures occurring in the document;

generating a query signature for the search query excluding a reference term, the query signature being based on the hash function of the adjacent query terms adjacent to the reference term;

comparing the query signature to the index term signatures in the list to identify index term signatures that match the query signature, the reference term of the query signature being equivalent to a searched index term of the list; and

outputting a document list indicating the documents that contain the identified index term signatures on an output device.

2. The method of claim 1, wherein the index term signatures are combined to form a single index term signature for each index term in the document.

3. The method of claim 1, wherein said step of generating the index term signature for each index term in the document corpus, comprises:

generating a term vector based on each adjacent term within the predetermined number of adjacent terms; and

combining the generated term vectors to form the index term signature.

4. The method of claim 3, wherein the predetermined number of adjacent terms is at least equal to the number of search terms in the search query minus one.

5. The method of claim 3, wherein said predetermined number of adjacent terms precede the index term.

6. The method of claim 3, wherein said predetermined number of adjacent terms succeed the index term.

7. The method of claim 3, wherein said predetermined number of adjacent terms both precede and succeed the index term.

8. The method of claim 3, wherein said term vector for each adjacent term is generated by a hash function.

9. The method of claim 8, wherein the hash function is based on selected morphological characteristics of the terms.

10. The method of claim 9, wherein the selected morphological image characteristics include at least one of a dimension, font, typeface, number of ascender elements, number of descender elements, pixel cross-sectional characteristics, pixel density, and contour characteristic of said term.

11. The method of claim 8, wherein the hash function is based on the ASCII code of the letters in the term.

12. The method of claim 1, wherein said step of generating a query signature for the search query, comprises:

selecting a reference term in the search query;

generating a term vector for all terms within the search query except for the selected reference term; and

combining the generated term vectors to form the query signature of the reference term.

13. The method of claim 1, wherein said terms in said document corpus are words.

14. The method of claim 13, wherein the index words are uncommon words.

15. The method of claim 1, wherein said terms in said document corpus are language characters.

16. The method of claim 15, wherein said language characters are one of Kanji, Katakana, Hiragana and pictorial characters.

17. An apparatus for retrieving relevant documents from a corpus of documents based on a search query, the apparatus comprising:

storage means for storing the corpus of documents;

input means for inputting the corpus of documents and the search query;

a controller for retrieving relevant documents from the corpus of documents, the controller comprising;

index term signature generating means for generating an index term signature for each index term in the corpus of documents, the index term signature being based on a hash function of a predetermined number of adjacent terms adjacent to the index term;

list generating means for generating a list containing the index terms in the corpus of documents, the list associating an index term with a document identifier and corresponding index term signatures occurring in the document;

query signature generating means for generating a query signature for the search query excluding a reference term, the query signature being based on the hash function of the adjacent query terms adjacent to the reference term; and

comparing means for comparing the query signature to the index term signatures in the list to identify index term signatures that match the query signature of the reference term, the reference term of the query signature being equivalent to the index term of the list; and

output means for outputting a document list indicating the documents that contain the identified index term signatures.

18. The apparatus of claim 17, wherein the index term signatures are combined to form a single index term signature for each index term in the document.

19. The apparatus of claim 17, wherein the storage means is one of a ROM and an external storage device.

20. The apparatus of claim 17, wherein the input means is one of a keyboard, a touchscreen, an image scanner and a computer terminal.

21. The apparatus of claim 17, wherein the output means is one of a CRT display, a storage means, a photocopier, a facsimile machine and a printer.

22. The apparatus of claim 17, wherein the index term signature generating means further comprises:

term vector generating means for generating a term vector based on each adjacent term within the predetermined number of adjacent terms; and

combining means for combining the generated term vectors to form the index term signature.

23. The apparatus of claim 22, wherein the predetermined number of adjacent terms is at least equal to the number of search terms in the search query minus one.

24. The apparatus of claim 22, wherein said predetermined number of adjacent terms precede the index term.

25. The apparatus of claim 22, wherein said predetermined number of adjacent terms succeed the index term.

26. The apparatus of claim 22, wherein said predetermined number of adjacent terms both precede and succeed the index term.

27. The apparatus of claim 22, wherein said term vector for each adjacent term is generated by a hash function.

28. The apparatus of claim 27, wherein the hash function is based on morphological characteristics of the terms.

29. The apparatus of claim 27, wherein the hash function maps a location of each term within the document.

30. The apparatus of claim 17, wherein the term signature generating means comprises:

selecting means for selecting a reference term in the search query;

term vector generating means for generating a term vector for all terms within the search query except for the selected reference term; and

combining means for combining the generated term vectors to form the query signature of the reference term.

31. The apparatus of claim 17, wherein said terms in said document corpus are words.

32. The apparatus of claim 31, wherein the index words are uncommon words.

33. The apparatus of claim 17, wherein said terms in said document corpus are language characters.

34. The apparatus of claim 33, wherein said language characters are one of Kanji, Katakana, Hiragana and pictorial characters.