Query-Time Inverse Document Frequency (TF-IDF)

The Term Frequency model has a massive blind spot: it doesn’t know which words actually matter.

If a user queries for the apple, the word apple carries all the meaning. The word the is just grammar noise.

But your engine just counts hits. If you have a massive, unrelated document that happens to use the word the 10,000 times, its score will be 10,000! It will completely bury a short apple pie recipe document that mentions apple 10 times.

This is absurd. We need to mathematically penalize useless, common words, and boost words that are rare and meaningful.

Enter TF-IDF (Term Frequency - Inverse Document Frequency).

The Intuition

How do we teach a computer that apple is important but the is garbage?

We look at how rare the word is across our entire dataset.

If we have 1,000 documents, and the appears in 999 of them, it is completely useless for finding specific information.
If apple appears in only 5 documents, it is a highly specific, valuable signal.

Therefore, a term’s weight should be inversely proportional to how many documents it appears in.

The Math

Instead of just using Term Frequency (TF), we multiply it by the Inverse Document Frequency (IDF).

$$ \text{TF}(t, d) = \text{Count of term } t \text{ in document } d $$ $$ \text{IDF}(t) = \ln \left( \frac{N}{\text{df}(t)} \right) $$

N: The total number of documents in your index.
df(t): The Document Frequency (how many unique documents contain term t).

Let’s break down why this formula is brilliant:

N / df(t): If a word t appears in every single document (N == df(t)), the fraction is exactly 1. If a word is incredibly rare and only appears in, say, 2 (out of 1000) documents, the fraction is huge (1000 / 2 = 500).
ln(N / df(t)): If we just multiplied by 500, extremely rare words would completely break the scoring scale. The natural logarithm smooths this out, reigning in massive spikes (ln(500) ≈ 6.215).
ln(1): What is the logarithm of 1? It’s zero. If a word like the appears in every single document (N == df(t)), its IDF is exactly 0. When you multiply TF * 0, the score for that useless word is completely destroyed!

NOTE:

the actual IDF formula used in most production systems is slightly different. And it is the one this course recommends!

$$ \text{IDF}(t) = 1 + \ln \left(\frac{N}{\text{df}(t) + 1} \right) $$

df(t) + 1: Adding 1 to the denominator (often called Laplace smoothing) prevents a fatal division by zero error if a queried term doesn’t exist in any document at all.
1 + ln(...): If a word like the appears in almost every document, N / (df(t) + 1) approaches 1. The natural logarithm of 1 is 0. By adding a base of 1, we ensure that the IDF never drops to exactly zero. Even extremely common words will contribute a tiny amount to the final score rather than completely zeroing out the Term Frequency.

Critical Architecture Note: Why Query-Time?

You might be tempted to calculate the final TF-IDF score for every word when you POST a document, and store that float in your Inverted Index. Do not do this.

Why? Because N (total docs) and df (document frequency) change every single time you add a new document. If you store the final score in your index during ingest, you would have to recalculate and rewrite the score for every single document in the entire system whenever a new document is added.

Real engines like Apache Lucene never do this. Instead, during ingest (POST), you only store the raw, static statistics: Term Frequency (TF), Document Frequency (DF) and the raw text.

The actual math (calculating the IDF and multiplying it by TF) happens on-the-fly during the GET request.

Your Task

Track N (the total number of documents).
Track df(t) (how many documents contain term t).
When a GET request arrives, for each term in the query, calculate its TF-IDF score dynamically for each matching document: score = TF * IDF.
If a query has multiple terms, sum the TF-IDF scores for the document.
Return the Document IDs sorted descending by this new TF-IDF total score.

For example, applying this to our index (N = 3):

the     -> df = 3; IDF = 1 + ln(3 / (3 + 1)) ≈ 0.712
apple   -> df = 2; IDF = 1 + ln(3 / (2 + 1)) = 1

Query: "the apple"
red_apple.txt   -> (tf(the) * idf(the)) + (tf(apple) * idf(apple)) = (1 * 0.712) + (2 * 1) = 2.712
green_apple.txt -> (tf(the) * idf(the)) + (tf(apple) * idf(apple)) = (1 * 0.712) + (1 * 1) = 1.712
rolling.txt     -> (tf(the) * idf(the)) + (tf(apple) * idf(apple)) = (1 * 0.712) + (0 * 1) = 0.712

Warning

Because floating-point math can be slightly imprecise across languages, our tests do not assert exact float values. We only assert the relative ordering of the results. As long as your formula is correct, the documents will sort perfectly!

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until tf_idf