How a Search Engine Works: Building a Tiny Inverted Index

You open a movie app and search for space rescue. How does it find the right movies, and why does one appear above another? I built mini-search to understand that path. It has three main steps:

1. Process the text: Turn movie descriptions and search queries into consistent words.
2. Build an inverted index: Store which movies contain each word, then use it to find possible matches.
3. Score the matches: Put the strongest matches first with TF-IDF.

We will follow four made-up movies through all three steps. The real project gets movie data from TMDB; it does not crawl the web. In this example, we search descriptions only.

A basic search could read every description and check for the exact phrase space rescue. That finds D1 and D2, but misses D3, which mentions space without rescue. It also reads all four descriptions again for every new search. We can prepare the text once and keep a word lookup instead.

Step 1: Process the text

The Analyzer prepares text both when a movie is added and when someone searches. Both sides must follow the same rules. Otherwise, a query like SPACE, RESCUE! might miss descriptions containing space rescue.

The full pipeline has five stages, in this order:

1. Lowercase (LowercaseFilter.js): Space becomes space. Capitalization no longer changes whether two words match.
2. Remove punctuation (PunctuationFilter.js): rescue! becomes rescue. This project removes punctuation rather than replacing it with spaces, so movie-star becomes moviestar.
3. Tokenize (Tokenizer.js): Split the cleaned text into words. space rescue becomes ["space", "rescue"]. We need individual words to look them up separately.
4. Remove stop words (StopWordFilter.js): Drop very common words such as the. They tend to create large posting lists without helping much to tell movies apart. This is a tradeoff: removing a word can also make some searches less precise.
5. Stem (Stemmer.js): Trim word endings so different forms can match: running → run and runs → run. We do this to movie descriptions and search queries, so a search for run can find either form. The project uses the Porter stemmer from natural. It follows suffix rules, so it does not turn every related word into the same stem; ran is an example.

For D1, the first three stages give us:

"Space rescue finds a lost astronaut in space."
→ ["space", "rescue", "finds", "a", "lost", "astronaut", "in", "space"]

The output of the full pipeline is also a list of words, after stop-word removal and stemming. The interactive examples in this article deliberately stop after the first three stages. That keeps the words and counts visible: D1 has eight tokens, including a and in. The real project runs all five stages, so its token counts and scores may differ from the examples below.

Step 2: Build the inverted index

After text processing, we could store D1 → space, rescue, finds, …, space. But a person searching starts with a word, not a movie ID. We reverse the direction:

space  → D1 (2), D2 (1), D3 (1)
rescue → D1 (1), D2 (1)

Each row is a posting list. It says which movies contain the word. The number in parentheses is the raw count in that description: D1 says space twice. The InvertedIndex keeps that count and the field’s token length, which the scorer uses to calculate term frequency. The real index keeps postings by field, so a word in a title can be treated differently from one in a description.

When a movie is added, its fields go through the Analyzer, then each resulting word updates its posting list. At search time, space rescue goes through the same Analyzer. The engine looks up space and rescue and combines their lists:

• space finds D1, D2, and D3.
• rescue finds D1 and D2.
• Together they give D1, D2, and D3 as possible results. D4 is not a match.

This is an OR search: a movie can contain either word. An AND search would keep only D1 and D2. mini-search’s SearchEngine uses OR. Looking up a word avoids scanning every description for every query, although we still have to read its posting list and score the movies it names.

Step 3: Score the matches with TF-IDF

Finding D1, D2, and D3 does not tell us their order. D1 says space twice and includes rescue. D2 includes both words once. D3 only includes space. We want the result list to reflect that.

Term frequency (TF) measures how much of one movie’s text is the query word. Here we divide the word’s count by the description’s token count. D1 has space twice in eight tokens, so its TF for space is 2/8. Dividing by length keeps a long description from winning just because it has more room for words.

Inverse document frequency (IDF) measures how much a word helps distinguish movies. space appears in three of our four descriptions; rescue appears in two. A rescue match carries more weight because it narrows the search further. The project uses Math.log(total documents / documents containing the word). A word in every movie gets an IDF of zero; an unseen word has no posting list and contributes nothing.

For each query word, the TFIDFScorer multiplies TF × IDF × field weight, then adds the contributions. Field weights let the real project give a title match more importance than a description match. Our four-movie example searches only descriptions, so every match has the same field weight.

The app shows Lost in Orbit → Home from Mars → New Worlds. Blue Notes is not a candidate. Try other words in the lab below to see the posting lists, scores, and final order change.

That is the core of this search engine: analyze text the same way on both sides, use an inverted index to find candidates, and score those candidates to choose an order. The full code and API are in mini-search. This small TF-IDF example explains the idea; Elasticsearch uses BM25 by default.

References

• mini-search source and README