The Inverted Index

Now lets start thinking about how we can improve the search performance from the previous linear scan approach. Instead of scanning through all the documents, we can use an Inverted Index.

An Inverted Index maps Word -> Document IDs.

When a document comes in, we chop it up into individual words (tokens), and for each word, we record that this document contains it.

Your Task

1. Ingest Endpoint: When you receive text, tokenize it by splitting on spaces (whitespace). Maintain a global Inverted Index: a map where the key is a Term (string), and the value is a Set (or List) of DocIds.

   The Inverted Index would look like this:

   Apple       -> { green_apple.txt }
   Green       -> { green_apple.txt }
   The         -> { green_apple.txt, red_apple.txt, rolling.txt }
   a           -> { red_apple.txt }
   apple       -> { red_apple.txt }
   apple.      -> { red_apple.txt }
   apples      -> { rolling.txt }
   are         -> { rolling.txt }
   is          -> { green_apple.txt, red_apple.txt }
   red         -> { red_apple.txt, rolling.txt }
   rolling.    -> { rolling.txt }
   sour!       -> { green_apple.txt }
   sweet       -> { red_apple.txt }
   

2. Search Endpoint (GET /search?q={term}&limit={k}): When a query comes in for a single term, simply look up that term in your Inverted Index Map. Return the Set of Document IDs as a comma-separated list, up to the maximum limit. If the term isn’t in the map, return an empty response.

Tip

Keep it simple. We are still not worrying about lowercasing or punctuation. Just split by the space character and use those exact tokens as keys.

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 inverted_index