How a Search Engine Works

Who can imagine a world without search engines? Certainly we, the CS people, cannot imagine it for some obvious reasons. Have you ever wondered, how Google reacts to your query and almost always gives you the relevant result? If you have wondered about this, then prepare to enter the world of search engines. The best method to understand a search engine is to make one. So, lets just do it! In this assignment, we'll develop a very basic search engine for your PC.

Lets call our search engine "Joojle" (FYI, this name is 100% unique and it is as creative as Bollywood movies).

In our search engine, there will be a huge role of Hash Table and a small but very useful role of Balanced Tree (which is a 2,3 Tree in our case).

The Fundamentals

There will be the following basic steps/components in our search engine:

• Reading data from files
• Case Folding
• Tokenizing
• Removing Stop Words
• Stemming
• Indexing
• Query and Result

Each step is explained in the following.

Reading Data

Your program will take a path of a folder as input and read data from all the files present in the folder. I would recommend reading one file at a time and process it and storing it in a temporary buffer. We need temporary buffers because we'll be performing a few actions before storing data in a proper way.

Case Folding

Convert all letters into one case (lower or upper). Because in our search engine upper and lower case is insignificant so converting all letters into one case will make or work easier.

Tokenizing

Now tokenize the data. Split the string into words by tokenizing it on the bases of white space. We'll call these words terms in the future. You can also filter the punctuation marks or any other special characters too.

Removing Stop Words

Very common words like "is", "are", "the", "these" and so on are also insignificant in our basic search engine because they are present in abundance in nearly every file and they can make our result biased. So, we'll just remove these words from the list of terms or we can choose to not include them in the list of terms while tokenizing. It's up to you what approach you use. A list of stop words is provided here.

Stemming

One word can have may forms, for example work, works, worked, working and so on. These are different forms of a single word. Usually when a person searches some term, the person doesn't care which form of word is present in the result; the person is mainly concerned about the main core word. So, we'll treat different forms of a term as a single term. But the main question is, how will we do that?

Well, here is good news for you. We'll use Porter Stemmer and it'll do that difficult task for you. There are some other stemmer software too but I recommend Porter. Its code is easily available on the web in nearly every programming language. You will just pass a term to the Porter Stemmer and it'll wave its wand and return you a term (that can be the same term that you passed to it or a slightly transformed one). After the stemming process, different forms of each word will be transformed into a unique form (that may not be a valid English word, but that's none of our concern so don't worry about that).

Indexing

Now is the most important part and the core of our search engine, the indexing. By now we should have a refined list of terms. Now, we'll store terms in a kind of an "inverted index" (each term will be present as a key and corresponding to each key there will be a list of documents in which that term is present). I hope you have studied Hash Tables by now because we will use them now in the core of our engine. Now we'll traverse through the list of terms and pass each term one by one to a hash function that will map each term to an entry in the hash table. But as we know, hash functions are never perfect, so there is a very probability that many terms will have collisions, in other words they will be mapped to the same location. You all may know the traditional way of resolving the conflicts by storing a linked list of all collided terms. But still there can be a very long linked lists and the traversal of the linked list will take O(n) time, n being the length of the linked list. Our great and robust Joojle can't afford that so we'll try to make this traversal quicker. So instead of Linked Lists we'll use 2,3 Trees. Each entry of Hash Table will point towards the root of the 2,3 Tree.

By now there might be many explosions in your mind. Don't worry! The following is the pictorial representation of the indexing method that hopefully will clarify many things.



Another important thing is to determine what each node of the 2,3 tree will look like. Well, it will consist of mainly the following 2 things: