Build a real search engine from scratch

Type two words into a search box and a good engine returns the most relevant document out of millions, in the time it takes the page to paint. It does that with four parts, and you will build each one:

• A corpus: the set of documents you search. Step 2 gathers one.
• Tokenisation: turning each document's text into a clean list of index terms. Step 3.
• The inverted index: a lookup from each term to the documents that contain it, so a query reads a few short lists instead of every document. Step 3.
• Ranking: scoring the matches so the best one comes first. Counting word matches is the naive way; BM25 is the way real engines do it. Step 4.

Two of those words carry the whole idea. To index a corpus is to read every document once, up front, and build the lookup structure. To crawl is to gather the documents in the first place (following links, fetching pages). You crawl once to get a corpus, index it once, then answer many queries fast against the index.

Why not loop over every document for each query and count the matches? That is a full scan, and it is what grep or SQL LIKE do. It is fine for a folder of notes and hopeless for a million documents: the work grows with the size of the corpus, on every single query. An inverted index moves that work to indexing time, so a query touches only the terms it asks about. Ranking is the second half of the problem: once you have the matches, which one is actually most relevant?

Set up a folder and grab the kit. Every file is in search-engine.zip (2MB), including a ready-made corpus so you can see the goal straight away:

mkdir search-engine
cd search-engine
# unzip search-engine.zip into this folder (the files sit directly inside it)

Run the finished engine once, to see what you are building. It loads the corpus, indexes it, and answers a fixed set of queries:

python engine.py demo

indexed 5,264 documents, 16,464 unique terms, avg length 85.5 tokens, in 1870 ms

query: 'white whale'   terms=['white', 'whale']   scorer=BM25
  1. [ 8.797] Moby Dick #353
  2. [ 8.119] Moby Dick #851
  3. [ 7.943] Moby Dick #400
  4. [ 7.563] Moby Dick #379
  5. [ 7.413] Moby Dick #918
  (936 ranked, 49.98 ms)

That is the destination: 5,264 documents indexed in under two seconds, and a two-word query ranked across all of them with real relevance scores. Now close the kit and build it yourself, one part at a time. You can always compare against the kit's version.