System and method for compressing inverted index files in document search/retrieval system

• US 5,953,723 A
• Filed: 04/02/1993
• Issued: 09/14/1999
• Est. Priority Date: 04/02/1993
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: TM Patents LP
• Inventors: Linoff, Gordon S., Stanfill, Craig W.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/042,357
• Time in Patent Office: 2,356 Days
• Field of Search: 395/600, 707/102, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A document query processing system comprising a document database and a document query processor. The document database includes a document text base, an encoded index file, and a dictionary. The document text base includes document text in which each have an associated location identifier in the document. The encoded index file including a plurality of encoded records, each for a different word in the document text base. Each record has a locator entry associated with each instance in the document text base of the word associated with the record, the locator entries containing encoded locator values identifying locations of instances of the word in the document text base. The dictionary includes record location identifiers pointing to the location in the encoded index file of each encoded record. The query processing element includes a dictionary lookup element to identify the locations of records in the dictionary corresponding to each query word, and an encoded index file processing element for using the record location identifier identified by the dictionary to locate a record in the encoded index file for the query words and decoding the encoded locator values in the locator entries of the record to generate pointers each identifing locations in the document text base of instances of the the query word. An encoding arrangement for generating the encoded index file is also disclosed.

Claims

1. A document database generator for use in connection with a document query processing system, the document database generator generating an encoded index file and a dictionary in response to a document text base, the document text base including a plurality of words organized into at least one document, each word having an associated location identifier identifying the location of the word in the at least one document, the location identifier having a series of location identifier entries for identifying the location in the at least one document of the associated word in a location hierarchy, the document database generator comprising:

A. an index file generating element for generating an index file including a plurality of records each associated with a unique word in the document text base, each records having at least one locator entry, with each locator entry identifying a location of the word in the at least one document, each locator entry having a series of locator fields containing locator values according to a location hierarchy;

B. an encoded index file generating element for generating, in response to the index file generated by the index file generating element, an encoded index file, the encoded index file generating element in generating the encoded index file selecting locator entries in a record in the index file which have a series of locator fields which contain corresponding locator values, and substituting for the series in one of the selected locator entries an indicator indicating the correspondence of the locator fields to the other of the selected locator entries; and

C. a dictionary generating element for generating a dictionary field comprising a plurality of record location identifiers each identifying one of the words in the document text base and the location in the encoded index file of an encoded record associated with the identified word.

2. A document query processing system comprising:

A. a document database including;

i. a document text base including a plurality of words organized into at least one document, each word having an associated location identifier in the at least one document;

ii. an encoded index file including a plurality of encoded records, each associated with a unique word of the document text base,

each record having a locator entry that is associated with each instance of the word that is associated with the record in the document text base, with records associated with words having a plurality of instances in the document text base having a series of locator entries,

each locator entry storing location information identifying a location of a word associated with the locator entry in the document text base, the location information of successive locator entries in a record being encoded such that, for a selected locator entry in a record which is directed to a word which has a location in the document text base with a selected correspondence to a location of a word associated with a preceding locator entry in the record, the location information comprises a correspondence reference to the preceding locator entry; and

iii. a dictionary including a plurality of record location identifiers each identifying one of the words in the document text base and the location in the encoded index file of an encoded record associated with the identified word;

B. a query processing element comprising;

i. a query processing element for receiving a query, said query comprising at least one query word;

ii. a dictionary lookup element for using the query word to identify a record location identifier in said dictionary corresponding to said query word; and

iii. an encoded index file processing element for using the record location identifier identified by the dictionary to locate a record in the encoded index file and for decoding the encoded locator values in the locator entries in the record to generate pointers each identifying locations in the document text base of instances of the query word, the encoded index file processing element, in decoding the encoded index file, determining for a selected locator entry which contains a correspondence reference, the location information from the preceding locator entry, the encoded index file processing element using the location information from the preceding locator entry in generating the pointer for the selected locator entry.

3. A document query processing system as defined in claim 2 in which words in the document text are organized into a document hierarchy having a plurality of levels, each locator entry comprising a plurality of fields each associated with a level in the hierarchy, each correspondence reference further containing level information identifying the number of levels in the hierarchy for which the location information for the selected location entry has the selected correspondence with the location information for the preceding location entry.