Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 43 ยท Projects

Project: Build a Mini Search Engine

Build a tiny search engine in Node: a tokenizer, an inverted index with positions, BM25 ranking and phrase search, the same ideas Lucene uses inside Elasticsearch.

You have read about inverted indexes, analysis and BM25. In this project you build all three yourself, in about 80 lines of Node. At the end you have a working engine that indexes documents, ranks them by relevance and finds exact phrases. It is the same recipe Lucene follows inside Elasticsearch, only without compression, segments, disks or concurrency.

The code is a stand-in. Real Elasticsearch is not running on this site, and Lucene's implementation is vastly more optimized. But the pipeline is real: text goes through analysis, the terms go into an index with positions, and a query is scored with BM25. If you need a refresher, see The Inverted Index, Analysis, Tokenizers and Analyzers and Relevance Scoring with BM25.

Four steps to a search engine

Tokenize Lowercase and split text into terms.
Index Map each term to documents and positions.
Rank Score matches with BM25.
Phrases Check that positions are consecutive.

Each step is one small function.

1 / 2

Step 1: the tokenizer

Analysis turns raw text into terms. Our analyzer is the simplest useful one: lowercase everything, then keep runs of letters and digits. Punctuation disappears and "Search" and "search" become the same term. This is close to what the standard analyzer does for English text (the real one follows Unicode word-boundary rules, so it handles many more languages).

We also keep the position of every term. Position is the token's index in the text: the first token is 0, the second 1, and so on. Positions are what make phrase search possible later.

Node.js Tokenizer with positions

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 node:readline or process.stdin), it gets the next line from this box.

The first sentence gives six tokens at positions 0 to 5: the, quick, brown, fox, in, 2024. The three spellings of search all become the same term, and a string with only punctuation yields no tokens. Because we do not remove stop words, the and in are indexed as normal terms. BM25 handles them well anyway: a term that appears in almost every document gets a very low weight.

Step 2: the inverted index

The index is a map from a term to its postings: for each document, the list of positions where the term occurs. We also store each document's length (the number of tokens) and the total of all lengths. BM25 needs those two numbers to judge whether a document is long or short compared to the average.

Node.js Build the index and inspect it

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 node:readline or process.stdin), it gets the next line from this box.

You should see that index occurs in document 1 at positions 4 and 6, while documents appears in both documents, and missing has no postings, so a query for it costs a single dictionary lookup. This is the key property: the work depends on the postings of the query terms, not on the size of the corpus.

Step 3: BM25 ranking

Matching is not enough. A search engine has to put the best document first. BM25 gives every (term, document) pair a score from three ingredients:

  • Inverse document frequency (IDF). A rare term is more informative than a common one. With N documents and a term that appears in n of them, Lucene uses ln(1 + (N - n + 0.5) / (n + 0.5)).
  • Term frequency (TF), with saturation. More occurrences help, but with diminishing returns. The parameter k1 (1.2 by default) controls how fast the gain flattens.
  • Length normalization. A match in a short document means more than the same match in a long one. The parameter b (0.75 by default) controls how strongly length counts.

The score of one term in one document is idf * tf * (k1 + 1) / (tf + k1 * (1 - b + b * len / avgLen)). A document's total score for a multi-term query is the sum over its query terms.

To find the phrase "search engine", we need documents where search appears at some position p and engine at p + 1. Positions make this a cheap check: take the positions of the first term in a document and test whether every later term sits at the expected offset.

Here is the complete engine. It indexes five small documents, runs ranked queries and runs phrase queries.

Node.js The complete mini 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 node:readline or process.stdin), it gets the next line from this box.

Read the output carefully, because it shows relevance at work:

  • "search engine" ranks document 3 first. Its title is Search engine basics and it is short, so both terms count strongly. Document 1 comes second, and document 2 matches only the word search and scores lowest.
  • "lemon" puts document 2 (the term twice in the body) ahead of document 4 (once). The title word lemons is a different term, because we do no stemming.
  • IDF shows that lemon (in 2 of 5 documents) is worth more than search (in 3 of 5).
  • Phrases: "search engine" matches documents 1 and 3, but "engine search" matches none, because the order matters. Document 2 contains both search and pantry, but never the two words side by side.

Where to go from here

You now have the skeleton of a real engine, and the gaps are the interesting part of Lucene and Elasticsearch:

Missing here What the real engine does
Stemming (lemons vs lemon) Language analyzers and stemmer filters (Custom Analyzers, Synonyms and Stemming)
Fields (title vs body) Separate indexes per field, with boosts for important ones
Everything in memory Immutable segments on disk, merged in the background (Segments, Refresh and Near-Real-Time Search)
Scanning all postings of a term Skip lists and block-max algorithms that skip documents that cannot reach the top 10
One machine Shards and replicas (Shards, Replicas and Clusters)
IDF computed over the whole corpus Per-shard statistics, which can differ slightly between shards

Try extending the project yourself: add a title boost (count title tokens twice), add a must_not word, or return a short snippet around the first match.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the engine store token positions in the postings?

    Positions let the engine check that the words of a phrase appear next to each other and in order. IDF needs only document counts.
  2. 2. A term appears in almost every document. What does BM25 do with it?

    IDF shrinks toward zero when n is close to N, so common words add little to the score without any special stop-word list.
  3. 3. In the stand-in, what does the query cost depend on?

    Only the postings lists of the query terms are read. Terms that are not in the dictionary cost one lookup.
  4. 4. Why does the phrase "engine search" match nothing in the demo?

    The phrase check requires consecutive positions in the given order. Both words occur, but never as engine followed by search.

Summary

  • A search engine is analysis + an inverted index + a scoring function.
  • Positions in the postings enable phrase queries.
  • BM25 combines IDF (rarity), saturating term frequency (k1) and length normalization (b).
  • Query cost depends on the postings of the query terms, not on the corpus size.
  • The mini engine is a stand-in: Lucene adds stemming, fields, compression, immutable segments, skipping and distribution.

Next lesson: Practice Exercises with Solutions.