Places:Full Text Indexing: Difference between revisions

 

 

1) We might need a table or two more for efficiently ranking

 

Classes

There are essentially five classes for the back-end:

1) nsNavHistoryQuery

2) nsNavFullTextIndexHelper

3) nsNavFullTextIndex

4) nsNavFullTextAnalyzer

nsNavHistoryQuery.

 

nsNavFullTextIndex

Block is a struct used to encode and decode block. A block is variable length delta encoded. Variable Length delta Encoding, compresses very efficiently balancing speed and storage requirement.

struct Block {

//The width of the field is 255 bytes. The return value is an int indicating number of elements in the data that were encoded in the out byte array.

int encode(in int[] data, out byte[] encodedBlock) {

//How to encode more efficiently, any idea?

int[] bigEndian;

int k = 0;

data[i - 1] = 0;

for(int i = 0; i < data.length; i++) {

data[i] -= data[i - 1];

int j = 0;

while(data[i] != 0) {

bigEndian[j++] = data[i] % 128;

data[i] /= 128;

}

for( ; j > 0; j--, k++) {

encodedBlock[k] = (1 << 8) & bigEndian[j];

}

encodedBlock[k++] = bigEndian[0];

if (k > 255)  

return i - 1

}

}

void decode(in byte[] encodedBlock, out int[] data) {

int j = 0;

for(int i = 0; i < encodedBlock.length; i++) {

if (encodedBlock[i] && (1 << 8)) {

data[j] *= 128;

data[j] += encodedBlock[i] & ((1 << 8) - 1);

}

else {

data[j] += data[j - 1]; //Because it was delta encoded

data[j++] = encodedBlock[i];

}

}

}

}

AddDocument(connection, document, analyzer) {

AddDocument in two pass. Scan the document for terms and then invert. We have the doc id. We will require a hash map library to make it very efficient. Term is a hash map. Usage: term['termname'] = array of pos.

while(analyzer.hasTerms()) {

cTerm = analyzer.nextTerm();

term[cTerm.Name].add(cTerm.pos);

}

iterator i = term.iterator();

while(i.hasNext()) {

termName = i.next();

termPos[] = term[termName];

//hopefully sqlite caches query results, it will be inefficient otherwise.

 

    WHERE word = termName and flags < 128)");

AND firstdoc >= record.firstdoc AND flags >= 128

 

RemoveDocument() {

Inherently inefficient because of the structure that we have adopted. Needs to be optimized. The general algorithm revolves around finding the record whose firstDoc is immediately less or same as the docId we are searching for.

firstdoc < docIdWeAreSearchingFor

This returns a number of records with flag == 0 or 0 < flag < 128 or flag == 128 or flag > 128.

for each record we found do the following:

if no more docs left in this row, delete the row

when 0 < flag < 128, contains both document list and posting table

when flag >= 128 //only postings table

}

SearchDocument(terms) {

terms is something like: "mac apple panther". Basically a collection of terms

The ranking algorithm as described in this document is used.

}

nsNavFullTextIndexHelper

This class contains mechanism for scheduling documents for indexing. It works pretty much like nsNavHistoryExpire. The scheduling balances indexing with overall firefox performance. It has a timer which when expires picks an unindexed document from the history and calls nsNavFullTextIndex::addDocument to index. When and how the timer is set, dictates the overall efficiency. Whenever a user visits a page, the timer is triggered.  

 

TokenStream is an abstract class with three methods next, reset and close. The next method returns a token. Token is a class representing startoffset, endoffset and termtext. TokenStream needs input to tokenize. There are two concrete class for TokenStream:

1) Tokenizer: The input is an inputstream.

2) TokenFilter: The input is another TokenStream. This works like pipes.