hOOt - full text search engine

Download Hoot_v1.0.zip - 52.78 KB Download Hoot_v1.1.zip - 75.21 KB   Download SampleApp_EXE_v1.1.zip - 41.36 KB Download Hoot_v1.2.zip - 54.09 KB   Download SampleApp_EXE_v1.2.zip - 42.16 KB Download Hoot_v1.3.zip - 54.15 KB   Download SampleApp_EXE_v1.3.zip - 42.26 KB Download Hoot_v1.4.zip - 55.98 KB   Download SampleApp_EXE_v1.4.zip - 42.57 KB

Introduction Why the name 'hOOt'? What is full text searching? Why Another Full Text Indexer? Features Limitations Performance Tests Using the Sample Application Code Behind the Sample Application Using hOOt in your Code How It Works Some Statistics... Index Engine Query Engine What's an inverted index? The power of bitmap indexes Files generated File Formats : *.WORDS File Formats : *.DOCS File Formats : *.BITMAP File Formats : *.DELETED File Formats : *.REC File Formats : *.IDX History

Introduction

• WAH compressed BitArray found here (WAHBitArray.aspx)
• mini Log4net replacement found here (http://www.codeproject.com/KB/miscctrl/minilog4net.aspx)
• MurMur2 hash index and storage file from RaptorDB found here (RaptorDB.aspx)
• fastJSON serializer found here (http://www.codeproject.com/KB/IP/fastJSON.aspx) 
• IFilter without COM by Eyal Post found here (http://www.codeproject.com/KB/cs/IFilter.aspx) for the sample application
  

Why the name 'hOOt'?

What is full text searching?

1. Existence : means finding words that exist in the many blocks of texts stored (e.g. 'bob' is in the PDF documents stored).
   
2. Relevance : meaning the text blocks returned are delivered by a ranking system which sorts the most relevant first.
   

As you can see the indexing engine is blazing fast going through 632mb of text in 57secs, the difference in time to the total 22 minutes is to do with the IFilter extraction time. On the query side for the above document count all queries perform in about 1 ms on the engine side and as you can see in the sample picture a search for "microsoft" gives back 208 items which took 0.151 seconds, again the difference is to do with the document deserialization time.

By comparison lucene.net has the following :

Performance Tests v1.2

Using a better word extractor the index size is reduced by about 19% to 24Mb.

Using the Sample Application

1. Set the index storage directory in the (1) group box, this will store all the index information.
2. Choose a folder where you want to crawl for content in the (2) group box.
   
3. In the (3) group box you can do the following :
1. Load hOOt : This will load

   hOOt

   so you can query an existing index.
   
2. Start Indexing : This will load

   hOOt

   and start indexing the directory you specified.
   
3. Stop Indexing : This will come active after you have started indexing so you can stop the process.
   
4. Count Words : This will show the number of words in hOOts dictionary
   
5. Save Index : This will save anything in memory to disk.
   
6. Free memory : This will call the internal free memory method on hOOt (this will only free the bitmap storage and not release the cache).
   
4. You can search for content in the (4) group box, the label will show the count and time taken.
1. To open the file just double click on the file path in the list box.
   

hOOt

• Foxit PDF filter found here (http://www.foxitsoftware.com/) [never use Adobe as it is dismally slow]. 
• Microsoft Office 2010 IFilter found here (http://www.microsoft.com/download/en/details.aspx?displaylang=en&id=17062)

Code Behind the Sample Application

private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
{
	string[] files = e.Argument as string[];
	BackgroundWorker wrk = sender as BackgroundWorker;
	int i = 0;
	foreach (string fn in files)
	{
		if (wrk.CancellationPending)
		{
			e.Cancel = true;
			break;
		}
		backgroundWorker1.ReportProgress(1, fn);
		try
		{
			TextReader tf = new EPocalipse.IFilter.FilterReader(fn);
			string s = "";
			if (tf != null)
				s = tf.ReadToEnd();

			h.Index(new Document(fn, s), true);
		}
		catch { }
		i++;
		if (i > 300)
		{
			i = 0;
			h.Save();
		}
	}
	h.Save();
        h.OptimizeIndex();
}

// specify the index folder to store information and the file name for the index files
Hoot hoot = new Hoot("d:\\IndexFolder" , "documents"); 

hoot.FreeMemory(false); // will free bitmap memory

// database mode of operation
hoot.Index(10, "some string from a database"); // index the contents of rec# 10 

// document indexing mode of operation
hoot.Index(new Document("d:\\filename.ext",string_from_file));  

// optimize the bitmap index size
hoot.OptimizeIndex(); 

public class myDoc : Hoot.Document
{
	public string Extension {get;set;}
	// any other properties you need
} 

Because hOOt uses

fastJSON

New in v1.2

foreach(string filename in hoot.FindDocumentNames("microsoft"))
{
   // a faster way to get just the filename instead of a Document object
}

How It Works

hOOt operates in the following 2 modes :

1. Database mode : where you want to index columns in a database and you supply the row number yourself from the database.
   
2. Document mode : where you give hOOt a document file which will be serialized and stored and document numbers generated for it.
   

1. Indexer Engine : is responsible for updating and handling the index generated.
   
2. Query Engine : is responsible for parsing the query text and generating an execution plan.

1. Compress bitmap indexes in memory and free the BitArray storage.
2. Unload cached word bitmap indexes completely.
   

Some Statistics...

• There are about 250,000 English words of which around 175,000 are in use (Oxford English Dictionary). 
• The maximum length of a word in English is 28 characters.

After going through the words extracted from the IFilters it is easy to see that there a problems with some document formating as some sentences don't have spaces and the words are stuck together. Also for programming documents CamelCase words are prevelent. 

For this reason as of version 1.2 the word extractor in hOOt will do the following: 

• CamelCase words are broken up.
• Word lengths greater than 60 characters are ignored
• Word lengths less than 2 are ignored

Index Engine

• Load words into memory.
• Load bitmap index data on demand.
  
• Extract word statistics from the input text.
• Update the word bitmap index.
• Free memory and bitmap cache.
  
• Write the words to disk.
• Write the bitmap index to disk.
  

Query Engine

1. Parse the input string of what to search for into words
2. Extract the bitmap index for all those words used in the search string
3. Execute the bitmap arithmetic logic
4. AND the result with the NOT of the deleted documents bitmap, to filter out deleted documents.
5. Enumerate the resulting bitmap
• in the case of database mode give you a list of record numbers
• in the case of document mode seek the document number and give you a list of documents from the documents storage.
  

What's an inverted index?

• Document number 1 : "to be or not to be, that is the question ..."
  
• Document number 2 : "Romeo! Romeo! where art thou Romeo! ..."

GenerateWordFreq

• words : {"to" count=2, doc#=1 }, {"be" count=2, doc#=1}, {"or" count=1, doc#=1} ....
• words : {"romeo" count=3, doc#=2}, {"where" count=1, doc#=2} ...

• to : 1000000...
  
• be : 1000000...
• or : 1000000...
• romeo : 0100000...
• where : 0100000...
  

The power of bitmap indexes

• The filter parser extracts the words "alice", "in", "wonderland".
• Seek the associated bitmap indexes for the words.
• Execute the query arithmetic logic in this case a logical AND operation to yield a resulting bitmap index.

hOOt

Files generated

• filename.WORDS : stores the words extracted from the input text.
  
• filename.DOCS : stores the document information.
  
• filename.BITMAP : stores the bitmap information for the words stored.
  
• filename.DELETED : stores the deleted document indexes.
  
• filename.REC : stores the data file offsets for document numbers.
• filename.IDX : stores the mapping between document file names and document numbers
  
• log.txt : stores the logging debug and error messages.
  

File Formats : *.WORDS

File Formats : *.DOCS

File Formats : *.BITMAP

File Formats : *.DELETED

File Formats : *.REC

File Formats : *.IDX