System and method for portable document indexing using n-gram word decomposition

• US 5,706,365 A
• Filed: 04/10/1995
• Issued: 01/06/1998
• Est. Priority Date: 04/10/1995
• Status: Expired due to Fees

• Current Assignee: Rebus Technology Incorporated
• Original Assignee: Rebus Technology Incorporated
• Inventors: Ravichandran, Natarajan, Rangarajan, Vijayakumar
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Johnson, Timothy M.
• Application Number:
  US08/419,126
• Time in Patent Office: 1,002 Days
• Field of Search: 382/224, 382/229, 382/230, 364/419.13, 364/419.19, 395/600
• US Class Current: 707/728
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06V 30/268 Lexical context
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and method provides for indexing and retrieval of stored documents using a decomposition of words in the documents in n-grams, or linear word subunits. The documents are indexed as pages in a number of banks. For each bank there is a bank index. The individual n-grams are identified for each page are stored in the bank index. Each bank index further contains an entry map that indicates whether a given n-gram is present in any of the pages of the bank, and then provides an index to a page map that further indicates which page in the bank contains the n-gram. When a search query is input, the query words are decomposed into their n-grams. The query word n-grams are compared first with entry maps to determine if the query word n-grams appear on any page in the bank. If so, the associated page map is traversed to determine which page in the bank contains the query word n-grams. The n-grams on the page are compared with the query word n-grams to determine the presence of an match therebetween. Matching pages are flagged. When all pages in all banks have been processed, the pages are consolidated with respect to the documents to which they belong, resulting in a list of documents that match the search query. The results are displayed to a user.

Claims

1. A computer-implemented method for indexing stored documents, each document containing at least one page and containing a plurality of words, and searching for at least one document matching an input search query containing at least one query word, comprising the steps of:

for each document;

identifying non-stop words on each page of the document;

determining for each non-stop word at least one n-gram;

for each n-gram, storing a map having a plurality of positions, each position corresponding to a page, and each position indicating whether or not the corresponding page contains the n-gram;

determining at least one query word n-gram for the at least one query word; and

is retrieving documents having n-grams that match selected ones of the query word n-grams, by performing the steps of;

determining a map corresponding to the query word n-gram;

determining from the map at least one page containing the query word n-gram; and

retrieving the page, and the document associated therewith.

2. A computer readable memory including a storage structure for indexing documents by n-grams, each document having a document number, and a document name, and at least one page, each page having a page number, comprising:

a bank comprising a list of page entries, each page entry identifying a page by the document number of the document containing the page, and a page number within the document; and

,

a bank index associated with the bank comprising;

i) a plurality of n-gram entry maps, each n-gram entry map associated with a single n-gram, selected n-gram entry maps having an index to an index entry map where at least one page identified in the bank includes the n-gram associated with the n-gram entry map;

ii) a plurality of index entry maps, each index entry map indexed by one of the n-gram entry maps, each index entry map having a plurality of positions, each position corresponding to a page entry in the bank, and each position indicating whether or not the corresponding page entry in the bank identifies a page containing the n-gram associated with the n-gram entry map that indexes the index entry map.

3. The computer readable memory of claim 2, wherein:

a) each page entry in the bank has an offset;

b) each index entry map includes a plurality of bit positions, each bit position associated with a page entry in the bank, each bit position having a first value where the page identified in the page entry associated with the bit position includes the n-gram associated with the n-gram entry map that indexes the index entry map, and a second value where the page identified in the page entry associated with the bit position does not include the n-gram associated with the n-gram entry map that indexes the index entry map.

4. The computer readable memory of claim 2, further comprising:

a) a drawer including;

i) a list of documents, each document uniquely identified in the list;

ii) a plurality of banks, and associated bank indices; and

iii) a bank list including for each of the plurality of banks a count of a number of empty page entries in the bank.

5. The computer readable memory of claim 2, wherein each bank further comprises:

a) a page key table including at least one page key, each page key uniquely associated with a page entry in the bank, and comprising;

b) for each word on the page, a list of the n-grams in the word.

6. A computer implemented method of retrieving a document, comprising:

a) storing the storage structure of claim 2 on a computer readable memory;

b) receiving a query term;

c) for each of a number of n-grams in the query term;

i) determining from the n-gram map in the bank index associated with the n-gram of the query term whether an index entry map exists for the n-gram;

ii) responsive to an existing index entry map, determining from the index entry map each page entry in the bank that identifies a page containing the n-gram associated with the index entry map; and

iii) incrementing for each page that contains the n-gram an n-gram counter;

d) for each page in the bank, determining whether the n-gram counter for the page is sufficiently similar to the number of n-grams in the query term to indicate that the page contains the query term; and

e) responsive to the n-gram counter for a page being sufficiently similar to the number of n-grams in the query term, retrieving the document containing the page for subsequent query analysis.

7. The computer implemented method of claim 6, wherein the n-gram counter for the page is sufficiently similar to the number of n-grams in the query term where:

##EQU5## wherein P is the page;

G is the n-gram match counter for page P;

K is the number of n-grams in the query term; and

E is a matching parameter selected to control the percentage of matches between the n-gram match counter and K.

8. A computer implemented method of indexing a plurality of documents, each document having at least one page, each page having less than a maximum amount of data, and having a plurality of words, comprising:

a) storing a list of pages, each page associated with a document;

b) determining a list of n-grams; and

c) for selected ones of the n-grams, storing a map of pages that contain the n-gram by;

i) retrieving a current page from the documents; and

ii) for each non-stop word of the current page;

1) determining the n-grams in the word; and

2) for each n-gram in the word;

in a map associated with the n-gram and having a plurality of positions, each position corresponding to a page, and each position indicating whether or not the corresponding page contains the n-gram, updating the position for the current page as indicating that the page contains the n-gram.

9. The computer implemented method of claim 8, for additionally retrieving a document including a query term, comprising:

d) receiving a query term;

e) for each of a number of n-grams in the query term;

i) determining whether a map exists for the n-gram;

ii) responsive to an existing map, determining from the map each page in the list that contains the n-gram associated with the map; and

iii) for each page in the list, determining whether the page contains a sufficient number of n-grams in the query term to indicate that the page contains the query term; and

f) responsive to each page containing the query term, retrieving the document containing the page for subsequent query analysis.

10. A computer readable memory including thereon a computer program configuring and controlling a processor to perform the steps of claim 8.

11. A computer readable memory for controlling a processor to index a plurality of documents, each document containing at least one page comprising:

a list of indexed pages;

a set of index maps, each index map associated with one n-gram and having a plurality of positions, each position uniquely associated with a page in the list of indexed pages, and each position indicating whether or not the corresponding page includes the n-gram associated with the index map; and

a page indexing module that;

i) receives a current page to be indexed;

ii) creates an entry for the current page in the list of indexed pages;

iii) stores for each non-stop word of the current page a list of n-grams in the word; and

iv) for each n-gram, updates in the index map associated with the n-gram, the entry for the current page to indicate that the current page includes the n-gram.

12. The computer readable memory of claim 11, wherein the page indexing module stores for a non-stop word of the current page a list of n-grams in the word by:

iii.1) determining an n-gram number for each n-gram in the word;

iii.2) storing the n-gram number of each n-gram in the word; and

iii.3) associating the stored n-gram numbers with the current page.

13. A computer readable memory for controlling a processor to index a plurality of documents, each document containing at least one page, the memory comprising:

a list of indexed pages;

a set of index maps, each index map associated with one n-gram and having a plurality of positions, each position uniquely associated with a page in the list of indexed pages, and each position indicating whether or not the corresponding page includes the n-gram associated with the index map; and

a page indexing module that;

i) receives a current page to be indexed;

ii) creates an entry for the current page in the list of indexed pages;

iii) stores for each non-stop word of the current page a list of n-grams in the word by;

iii.1) determining an n-gram number for each n-gram in the word by the equation;

##EQU6## where NG is the n-gram number of the word;

x is an n-gram character number of the i^th character of the word;

C_max is total number of indexable characters; and

N_p is the desired number of letters in the n-gram;

iii.2) storing the n-gram number of each n-gram in the word; and

iii.3) associating the stored n-grams numbers with the current page; and

iv) for each n-gram, updates in the index map associated with the n-gram, the entry for the current page to indicate that the current page includes the n-gram.

14. A computer readable memory for controlling a processor to index a document including a query term from a plurality of documents, each document containing at least one page, comprising:

a list of indexed pages, each page associated with a document;

a set of index maps, each index map associated with one n-gram and having a plurality of positions, each position uniquely associated with a page in the list of indexed pages, and each position indicating whether or not the corresponding page includes the n-gram associated with the index map; and

a search module that;

receives a query term;

for each of a number of n-grams in the query term;

determines whether there is an index map associated with the n-gram; and

responsive to an existing index map,

determines from the index map each page in the list of indexed pages that contains the n-gram associated with the map;

for each page in the list of indexed pages, determines whether the page contains a sufficient number of the n-grams in the query term to indicate that the page contains the query term; and

responsive to a page containing the query term, retrieves the document containing the page for subsequent query analysis.

15. The computer readable memory of claim 14, wherein the search module determines whether a page contains a sufficient number of the n-gram in the query term by the equation:

##EQU7## wherein;

P is the page;

G is the number of n-grams in the query term contained in page P;

K is the number of n-grams in the query term; and

E is a matching parameter selected to control the percentage of matches between the number of n-grams in the query term that are contained in the page P, and K.