Today we're going to talking about indexing and search: what is it that allows you to search through thousands of documents in less than a second?
In order to understand how indexing works, we will use an example where we have the following three documents:
doc1.txt contains:
The Three Little Pigs
doc2.txt contains:
The Little Red Riding Hood
doc3.txt contains:
Beauty And The Beast
Now, let's say you want to find out which of these documents contain a particular word, e.g. "Little". The easiest way to do this would be to go through each word in each document, one by one, and see if the word "Little" is in that document. Conceptually, we're talking about this:
Doing this in C# is very easy:
String[] documents = { "doc1.txt", "doc2.txt", "doc3.txt" };
String keyword = Console.ReadLine();
foreach (String document in documents)
{
if (File.ReadAllText(document).Contains(keyword))
{
Console.WriteLine(document);
}
}
Console.ReadKey(true);
Remember to put in a using System.IO; at the top, to be able to use File. If you press F5 and test this program, you'll see that it works:
However, this method isn't good because it will take longer as the documents get larger (more words) and more numerous (more documents).
The proper way to process search requests quickly is to build an index. This would look something like this:
The index stores a list of all words, each with a list of documents that contain it. If you compare it with the first diagram, you'll notice that we reversed the mapping of words and documents; this is why we call this an inverted index.
We can do this in C# by first building the index (remember to add using System.Collections.Generic; at the top):
// Build the index
String[] documents = { "doc1.txt", "doc2.txt", "doc3.txt" };
Dictionary<String, List<String>> index = new Dictionary<String, List<String>>();
foreach (String document in documents)
{
String documentStr = File.ReadAllText(document);
String[] words = documentStr.Split();
foreach (String word in words)
{
if (!index.ContainsKey(word))
index[word] = new List<String>();
index[word].Add(document);
}
}
...and then using the index to search the documents quickly and efficiently:
// Query the index
String keyword = Console.ReadLine();
if (index.ContainsKey(keyword))
{
foreach (String document in index[keyword])
{
Console.WriteLine(document);
}
}
else
Console.WriteLine("Not found!");
Console.ReadKey(true);
In this way, there is no need to search every document for the keyword each time the user wants to search for a word. The keyword is simply located in the index (if it exists), and a list of documents that contain it is immediately available:
This was a simple proof of concept of how indexing and search works, but here are a few additional notes:
- The index is usually built as documents are added to it, and then stored in one or more files (unlike in this program, where the index is rebuilt every time the program is run - that's just to make the illustration easier).
- Words such as "and" and "the" which are very common are called stop words and are normally excluded from the index.
- It is common practice to make searches case insensitive, e.g. by converting indexed words and query keywords to lowercase.
This article presented the concept of indexing and how it is used to search for a single keyword. Although there are other techniques used in text search, indexing is definitely one of the most important, and has many applications including databases and text retrieval (e.g. search engines). A fundamental concept to remember is that the whole point of indexing is to make search fast!
Thanks for reading! :) Feel free to leave feedback (positive or negative) either in the comments or by contacting me. Remember to subscribe to the Programmer's Ranch Facebook page to stay up to date with articles as they are published!
