Term Frequency

Your search engine successfully finds documents containing the required words. But there is a massive problem: it returns them in an arbitrary order.

If users search for apple, a document that mentions apple exactly once is treated the same as a document that mentions apple 50 times.

Welcome to the world of Relevance Ranking.

The simplest heuristic for relevance is Term Frequency (TF): if a document uses a word frequently, it’s probably about that word.

Your Task

Update the Inverted Index to store term counts.

Instead of mapping Term -> Set<DocId>, map Term -> Map<DocId, Count>.

When you index a document, count how many times each token appears in that document. When a user searches for a term, return the Document IDs sorted descending by their Term Frequency count. (If you hit the limit={k}, return only the top k results).

The Inverted Index should now look like this:

a           -> { red_apple.txt: 1 }
apple       -> { green_apple.txt: 1, red_apple.txt: 2 }
apples      -> { rolling.txt: 1 }
are         -> { rolling.txt: 1 }
green       -> { green_apple.txt: 1 }
is          -> { green_apple.txt: 1, red_apple.txt: 1 }
red         -> { red_apple.txt: 1, rolling.txt: 1 }
rolling     -> { rolling.txt: 1 }
sour        -> { green_apple.txt: 1 }
sweet       -> { red_apple.txt: 1 }
the         -> { green_apple.txt: 1, red_apple.txt: 1, rolling.txt: 1 }

When querying for apple, your search endpoint should return red_apple.txt,green_apple.txt because red_apple.txt has a higher Term Frequency.

Multi-Term Queries

In the previous stage, you implemented multi-term queries by computing the intersection of document sets (returning only documents that contain every queried word).

Now that we are tracking Term Frequency, how do we rank a document when a user query contains multiple words, like the apple?

1. Find the intersecting documents just like before. A document must contain both the and apple to be considered a match.
2. To calculate the document’s total relevance score, sum its Term Frequencies for each of the queried words.

For example, for the query the apple:

the     -> { green_apple.txt: 1, red_apple.txt: 1, rolling.txt: 1 }
apple   -> { green_apple.txt: 1, red_apple.txt: 2 }

• The intersection is { green_apple.txt, red_apple.txt }.
• Calculate the total scores for the matching documents: { green_apple.txt: 1+1, red_apple.txt: 1+2 }

Since 3 > 2, your engine should return red_apple.txt,green_apple.txt.

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 term_frequency