Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 63 ยท Counting and Classic Representations

Building a Small Search Engine

Build a tiny search engine from scratch in Python. Create an inverted index, answer AND and OR queries, rank results with TF-IDF and handle empty queries.

Every search box, from a website's to a code editor's, answers the same question: which of these documents match what I typed, and in what order? The core data structure is surprisingly small. In this lesson you build it from scratch, in plain Python, and then rank the results with the TF-IDF weights you already know.

The trick that makes search fast is to do the work ahead of time. Reading every document for every query would take forever on a large collection. Instead, you build an inverted index once: a map from each word to the documents that contain it. A query then looks up a few words instead of scanning the whole collection. This is how Lucene, Elasticsearch, Meilisearch and the search on this very site work at heart.

The inverted index

A normal index (the "forward" index) maps each document to its words. An inverted index flips that around: each term points to a postings list, the documents where it appears. Alongside each document id we store the term frequency, which ranking needs later.

Forward versus inverted

Forward index Document leads to its words.
Inverted index Word leads to its documents.

Queries start from words, so the inverted form is the fast one.

1 / 2

The analyzer matters as much as the index. The same function must process documents when you build the index and queries when you search, otherwise Python in a query would never match python in the index. Here is the index for five short documents, followed by two ways to combine query words.

Python An inverted index with AND and OR queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The postings show the structure. text points to documents 1, 3 and 5, and document 3 contains it twice. An AND query intersects the postings sets: only document 4 contains both python and java. An OR query unions them: documents 1, 2 and 4 contain at least one. text java finds nothing with AND, because no document has both.

Real engines keep postings lists sorted by document id, so intersection becomes a fast merge of two sorted lists instead of a set operation; the logic is the same.

Boolean search is not enough

AND is too strict: add a typo or one unusual word and you get nothing. OR is too loose: it returns everything that has a single matching word, in no useful order. Users want ranked retrieval: return the documents that match best, best first.

The score for a document is the sum, over the query terms it contains, of that term's TF-IDF weight in the document. A rare query word counts more than a common one, and a document that mentions a term often counts more than one that mentions it once. Dividing the term frequency by the document length keeps long documents from winning by sheer size.

flowchart LR
    Q["Query text"] --> A["Analyze: tokenize, lowercase, stop words"]
    A --> L["Look up postings for each term"]
    L --> S["Add up tf x idf per document"]
    S --> R["Sort by score, return top k"]

Matching and ranking happen only on documents that appear in at least one postings list.

Now package it. The SearchIndex class below builds the index once and answers any number of queries. The IDF is the smoothed form that TfidfVectorizer uses, so unknown terms never cause a division by zero.

Python A ranked search engine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the results critically, as you would when debugging a real engine:

  • For python text, documents 1 and 6 tie at 0.579, because both contain each word once and have five terms. Document 4 has python only, so it scores lower. The tie is broken by document id, and a real engine would decide ties explicitly.
  • For large text, document 3 wins because it holds text twice and large once. Document 2 (only large) beats document 1 (only text), because large is rarer than text in this collection and so has a higher IDF.
  • java ranks document 4 above 2 because document 4 is shorter, which makes java a bigger share of it.
  • quantum is not in the index, so there are no postings and no results. The code handles it by returning an empty list instead of crashing.

We sort by (-score, doc_id) so that the output is deterministic. If you leave ties to dictionary order, tests of a search engine will be flaky.

Improving matching

The engine finds only exact word forms. Two cheap upgrades give the most benefit.

Normalize word forms. cats should find cat. A tiny suffix stripper, applied to documents and queries alike, merges the forms. (Real systems use stemming or lemmatization.)

Remember positions. If the postings list also stores the position of each occurrence, you can answer phrase queries: "cat owners" matches only if owners comes directly after cat.

Python Stemming and phrase search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without stemming, a search for cats finds only document 1, and cat finds only 2 and 4, so a user is missing a third of the relevant results either way. After stemming, all three are reachable under one term. Documents 2 and 4 both contain cat and garden, but only document 4 contains the phrase cat owners, and the reverse phrase garden cat matches nothing, because word order matters in a phrase even though it does not in a bag of words. Stemming is crude, though: the rule above would turn bus into bu, so real stemmers have more careful rules.

From toy to real engine

Our engine is the same design as the big ones, shrunk down. What the production versions add:

  • Better scoring. TF-IDF is the idea; the standard refinement is BM25, which saturates the effect of repeated words and treats document length more carefully. You will write it in Project: Document Search with Ranking.
  • Compact, on-disk postings with compression, so indexes fit on disk and in cache.
  • Fields and boosts, so a match in a title counts more than a match in the body.
  • Typo tolerance and prefix search, usually built from edit distance and character n-grams.
  • Evaluation: precision at k and recall on queries with known relevant results, because "looks right" is not a measurement.

Later, retrieval and RAG swaps the TF-IDF vectors for learned embeddings, but the shape of the problem (index ahead of time, look up, rank) stays the same.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an inverted index map?

    An inverted index stores a postings list per term, so a query can go straight from its words to candidate documents.
  2. 2. Why must the same analyzer be used for documents and queries?

    If documents are lowercased but queries are not, "Python" would never match "python". Both sides need identical tokenization and normalization.
  3. 3. In the ranked engine, why is a match on a rare query word worth more than a match on a common one?

    IDF grows as document frequency falls, so a term found in few documents contributes more to a document's score.
  4. 4. What extra information must postings lists store to answer phrase queries?

    To know whether one word immediately follows another, the index needs the position of each occurrence, not just which documents contain the word.

Summary

  • An inverted index maps each term to a postings list of documents (with term frequencies), built once ahead of time.
  • Documents and queries must go through the same analyzer: tokenizing, lowercasing, stop words and stemming.
  • AND intersects postings, OR unions them; both are boolean and give no ranking.
  • Ranked retrieval sums each query term's TF-IDF weight per document and sorts, with a deterministic tie-break.
  • Stemming improves recall, and storing positions enables phrase queries.
  • Production engines add BM25, compression, fields, typo tolerance and proper evaluation.

You now have the classic toolkit for turning text into numbers. Next, move from counting words to predicting them with N-gram Language Models.