Associative text search and retrieval system having a table indicating word position in phrases

• US 5,771,378 A
• Filed: 06/07/1995
• Issued: 06/23/1998
• Est. Priority Date: 11/22/1993
• Status: Expired due to Term

• Current Assignee: RELX Inc. (RELX PLC)
• Original Assignee: RELX Inc. (RELX PLC)
• Inventors: Doan, Minh, McBeath, Darin W., Leininger, Catherine, Graham, Richard G., Waddell, Dale, Weckesser, Franz, Sever, Stephen M., Miller, David James, Holt, John, Lu, X. Allan, Pease, Thomas, Daley, Ray
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/473,824
• Time in Patent Office: 1,112 Days
• Field of Search: 395/605, 395/792, 395/793, 395/603, 395/606, 395/795, 395/760, 364/419.19
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An associative text search and retrieval system uses one or more front end processors to interacting with a network having one or more user terminals connected thereto to allow a user to provide information to the system and receive information from the system. The system also includes storage for a plurality of text documents, and at least one processor, coupled to the front end processors and the document storage. The processor(s) search the text documents according to a search request provided by the user and provide to the front end processor a predetermined number of retrieved documents containing at least one term of the search request. The retrieved documents have higher ranks than documents not provided to the front end processor. The ranks are calculated using a formula that varies according to the square of the frequency in each of the text documents of each of the search terms.

Claims

1. A method of operating an associative text search and retrieval system, comprising the steps of:

allowing a user to provide a plurality of search terms;

using a table to detect phrases within the search terms provided by the user, the table containing entries which, for each word that can be part of a phrase, indicate a position that the word can occupy in any phrase;

performing a search of text documents using the plurality of search terms provided by the user and the phrases, if any, detected by the table;

calculating a score for each of the text documents containing at least one of the search terms;

ranking the text documents based on their scores; and

providing the user with a predetermined number of retrieved documents that are a subset of the text documents based on the documents'"'"' ranks.

2. A method of operating an associative text search and retrieval system, according to claim 1, wherein the table has a bitmap associated with each entry, the bitmap indicating possible locations in a phrase of the associated entry.

3. A method of operating an associative text search and retrieval system, according to claim 2, wherein each bitmap entry is one byte long, a value of one at a particular bit position in the bitmap entry indicates that the word associated with the bitmap could appear in the corresponding position in a phrase, and a value of zero at a particular bit position in the bitmap entry indicates that the word associated with the bitmap could not appear in the corresponding position in a phrase.

4. A method or operating an associative text search and retrieval system, according to claim 2, wherein the table further has an ID for compressing the representations of each of the words by assigning a unique arbitrary number to represent each word.

5. A method of operating an associative text search and retrieval system, according to claim 4, wherein the table uses a tree having nodes corresponding to the ID'"'"'s associated with words in a phrase, the nodes being connected according to the order that the words can appear in a phrase.

6. An associative text search and retrieval system, comprising:

front end processing means for interacting with a network having one or more user terminals connected thereto to allow a user to provide information to the system and receive information from the system;

storage means for storing a plurality of text documents;

processor means, coupled to the front end processing means and the storage means, for performing a search of the text documents using a plurality of search terms provided by the user, for calculating a score for each of the text documents containing at least one of the search terms, for ranking the text documents based on their scores, and for providing to the front end processing means a predetermined number of retrieved documents that are a subset of the text documents based on the documents'"'"' ranks; and

a table used to detect phrases, the table containing entries which, for each word that can be part of a phrase, indicate a position that the word can occupy in any phrase.

7. An associative text search and retrieval system, according to claim 6, wherein the table has a bitmap associated with each entry, the bitmap indicating possible locations in a phrase of the associated entry.

8. An associative text search and retrieval system, according to claim 7, wherein each bitmap entry is one byte long, a value of one at a particular bit position in the bitmap entry indicates that the word associated with the bitmap could appear in the corresponding position in a phrase, and a value of zero at a particular bit position in the bitmap entry indicates that the word associated with the bitmap could not appear in the corresponding position in a phrase.

9. An associative text search and retrieval system, according to claim 7, wherein the table further has an ID for compressing the representations of each of the words by assigning a unique arbitrary number to represent each word.

10. An associative text search and retrieval system, according to claim 9, wherein the table uses a tree having nodes corresponding to the ID'"'"'s associated with words in a phrase, the nodes being connected according to the order that the words can appear in a phrase.

11. An associative text search and retrieval system, comprising:

front end processing means for interacting with a network having one or more user terminals connected thereto to allow a user to provide information to the system and receive information from the system;

storage means for storing a plurality of text documents;

processor means, coupled to the front end processing means and the storage means, for performing a search of the text documents using a plurality of search terms provided by the user, for calculating a score for each of the text documents containing at least one of the search terms, for ranking the text documents based on their scores, and for providing to the front end processing means a predetermined number of retrieved documents that are a subset of the text documents based on the documents'"'"' ranks, the retrieved documents having higher ranks than text documents not provided to the front end processing means, wherein the ranks are calculated using a formula that varies according to the square of the frequency in each of the text documents of each of the search terms; and

a table used to detect phrases, the table containing entries which, for each word that can be part of a phrase, indicate a position that the word can occupy in any phrase.

12. An associative text search and retrieval system, according to claim 11, wherein the table has a bitmap associated with each entry, the bitmap indicating possible locations in a phrase of the associated entry.

13. An associative text search and retrieval system, according to claim 12, wherein each bitmap entry is one byte long, a value of one at a particular bit position in the bitmap entry indicates that the word associated with the bitmap could appear in the corresponding position in a phrase, and a value of zero at a particular bit position in the bitmap entry indicates that the word associated with the bitmap could not appear in the corresponding position in a phrase.

14. An associative text search and retrieval system, according to claim 12, wherein the table further has an ID for compressing the representations of each of the words by assigning a unique arbitrary number to represent each word.

15. An associative text search and retrieval system, according to claim 14, wherein the table uses a tree having nodes corresponding to the ID'"'"'s associated with words in a phrase, the nodes being connected according to the order that the words can appear in a phrase.