Patent ID: 8392433

Claim:
A self-indexing software product comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to index a data collection comprising a plurality of documents wherein the data collection is represented by a word-based wavelet tree comprising a plurality of nodes and node levels, and to further index a data array comprising at least one element, wherein each of the at least one element corresponds to a document within the data collection with a uniform resource identifier (URI) address, wherein said self-indexing software product comprises: rank function software code for returning a number of occurrences of a symbol within a sequence of symbols in the word-based wavelet tree; select function software code for returning a position of the jth occurrence of a symbol within a sequence of symbols in the word-based wavelet tree; display function software code for returning a symbol at a position in the word-based wavelet tree; count function software code for returning a number a of occurrences of a symbol in the word-based wavelet tree; locate function software code for returning a position of an occurrence of a symbol in the word-based wavelet tree; find function software code for caching a last found position and occurrence count of a symbol on each node level of the word-based wavelet tree for a particular symbol lookup and using said select function software code to call only on data to the right of the last found position; URI efficiency function software code: wherein each of the at least one element comprises a start position of the document within the data collection, a length of the document, and a URI of the document; wherein the data array is sorted based on the start positions of each of the at least one element; and wherein execution of said URI efficiency function software code at a position in the word-based wavelet tree provides access to the at least one element of the data array that corresponds to the position in the word-based wavelet tree at execution; and hash table decoding function software code for decoding a document from the word-based wavelet tree back into its original representation, said hash table decoding function software code comprising a hash table: wherein a key of said hash table is a pointer value of a node and a corresponding value of said hash table is a rank at the pointer value; wherein each time a node is traversed for decoding, said hash table is consulted; wherein if the traversed node is indicated in the key of said hash table, then the rank in the corresponding value of said hash table is increased by one; and wherein if the traversed node is not indicated in the key of said hash table, then a new entry in the key of said hash table is created for a pointer value of the traversed node and the rank at the pointer value is calculated and stored in the value of said hash table corresponding to said new entry in the key of said hash table.