Method and apparatus for rapid full text index creation

Claim 1

A computer system for creating a full text index associated with a source text including one or more documents, each document comprising one or more granules, each granule defining an indexing unit of text including one or more words, the computer system comprising: (a) a first storage for storing the source text; (b) memory coupled to a processor for storing data used to create the full text index; (c) a second storage for storing the full text index; wherein the processor is associated with the first and second storage for creating the full text index in two phases, said processor performing the steps of: i. in the first phase, reading the source text; creating a word list comprising an entry for each unique word in the source text; and creating a non-repeating word number stream comprising a single entry for each unique word in each granule of the source text; and ii. in the second phase, creating an array in the memory comprising an entry for each unique word in the source text, said entry including a reference to a location in an uncompressed index, said uncompressed index associating a granule reference with each of said unique words; creating said uncompressed index as a function of the non-repeating word number stream; compressing the uncompressed index into the full text index; and storing the full text index in said second storage.

Claim 22

A method in a computer system for creating in first and second phases a full text index associated with a source text including one or more documents, each document comprising one or more granules, each granule defining an indexing unit of text including one or more words, the method comprising the steps of: parsing the source text into one or more granules, a granule number being associated with each granule; in the first phase, i. reading words from the source text, assigning a word number to each unique word, and creating a word list with an entry for each such unique word and associated word number; ii. creating a non-repeating word number stream comprising a sequence of said word numbers and a boundary demarcation for each said granule for recording the granule number in which each word occurs, wherein each unique word number appears at most once between each said granule boundary demarcation; iii. creating an alphabetically ordered list of unique words in the source text, wherein the alphabetically ordered list includes the word number associated with each unique word; in the second phase, i. determining memory requirements for an in-memory index comprising a granule reference list for each unique word in the source text, and allocating a portion of the memory for each said granule reference list; ii. creating an array comprising an entry for each unique word in the source text wherein each said entry contains data fields for the location in the in-memory index and the full text index associated with the unique word; iii. creating the granule reference list for each unique word in the source text by sequentially reading the non-repeating word number stream and, for each granule boundary demarcation in the stream, incrementing a granule number counter and, for each word number in the stream, recording the value of the granule number counter in the portion of the memory allocated for the unique word in the source text associated with the word number; iv. compressing the in-memory index; v. alphabetically ordering the compressed in-memory index and storing the compressed in-memory index; and vi. storing the compressed in-memory index and data used to create the full text index.

Claim 23

A method in a computer system for creating in first and second phases a full text index associated with a source text including one or more documents, each document comprising one or more granules, each granule defining an indexing unit of text including one or more words, the method comprising the steps of: parsing the source text into one or more granules, a granule number being associated with each granule; in the first phase, i. reading words from the source text, assigning a word number to each unique word, and creating a word list with an entry for each such unique word and associated word number; ii. creating a non-repeating word number stream comprising a sequence of said word numbers and a boundary demarcation for each said granule for recording the granule number in which each word occurs, wherein each unique word number appears at most once between each said granule boundary demarcation; iii. creating an alphabetically ordered list of unique words in the source text, wherein the alphabetically ordered list includes the word number associated with each unique word; in the second phase, i. determining memory requirements for an in-memory index comprising a granule reference list for each unique word in the source text, and allocating a portion of the memory for each said granule reference list; ii. creating an array comprising an entry for each unique word in the source text wherein each said entry contains data fields for the location in the in-memory index and the full text index associated with the unique word; iii. creating the granule reference list for each unique word in the source text by sequentially reading the non-repeating word number stream and, for each granule boundary demarcation in the stream, incrementing a granule number counter and, for each word number in the stream, recording the value of the granule number counter in the portion of the memory allocated for the unique word in the source text associated with the word number; iv. compressing the in-memory index; v. alphabetically ordering the compressed in-memory index and storing the compressed in-memory index; and vi. storing the compressed in-memory index and data used to create the full text index.

Claim 32

A method in a computer system for creating in two phases a full text index associated with a source text including one or more documents, each document comprising one or more granules, each granule defining an indexing unit of text including one or more words, the method comprising the steps of: i. in the first phase, (a) reading the source text; (b) creating a word list comprising an entry for each unique word in the source text; and (c) creating a non-repeating word number stream comprising a single entry for each unique word in each granule of the source text; and ii. in the second phase, (a) determining an amount of memory necessary to contain an uncompressed index: (b) creating an array comprising an entry for each unique word in the source text, said entry including a reference to location in the uncompressed index, said uncompressed index associating a granule reference with each of the unique words; (c) creating the uncompressed index based on the non-repeating word number stream; (d) compressing the uncompressed index into the full text index; and (e) storing the full text index.

Claim 33

A method in a computer system for creating in two phases a full text index associated with a source text including one or more documents, each document comprising one or more granules, each granule defining an indexing unit of text including one or more words, the method comprising the steps of: i. in the first phase, (a) reading the source text; (b) creating a word list comprising an entry for each unique word in the source text; and (c) creating a non-repeating word number stream comprising a single entry for each unique word in each granule of the source text; and ii. in the second phase, (a) determining an amount of memory necessary to contain an uncompressed index: (b) creating an array comprising an entry for each unique word in the source text, said entry including a reference to location in the uncompressed index, said uncompressed index associating a granule reference with each of the unique words; (c) creating the uncompressed index based on the non-repeating word number stream; (d) compressing the uncompressed index into the full text index; and (e) storing the full text index.

Claim 36

A method for creating a full text index of a source text, the source text including one or more documents, each document having one or more granules, each granule defining an indexing unit of text including one or more words, the steps comprising: a) reading the source text; b) creating a word list having an entry for each unique word in the source text, each entry including a unique word number associated with the respective unique word, c) forming a non-repeating word number stream comprising a word reference for each unique word in each granule of the source text by: i) referencing the word list; ii) obtaining from the word list a word reference associated with the respective unique word; iii) inserting the word reference in the non-repeating word number stream; and d) creating an array comprising an entry for each unique word in the source text, each said entry including an index reference to an index associated with the unique word, each said index operative to contain references to granules in which the associated unique word exists.

Claim 37

A method for creating a full text index of a source text, the source text including one or more documents, each document having one or more granules, each granule defining an indexing unit of text including one or more words, the steps comprising: a) reading the source text; b) creating a word list having an entry for each unique word in the source text, each entry including a unique word number associated with the respective unique word, c) forming a non-repeating word number stream comprising a word reference for each unique word in each granule of the source text by: i) referencing the word list; ii) obtaining from the word list a word reference associated with the respective unique word; iii) inserting the word reference in the non-repeating word number stream; and d) creating an array comprising an entry for each unique word in the source text, each said entry including an index reference to an index associated with the unique word, each said index operative to contain references to granules in which the associated unique word exists.