Typo Tolerance (Fuzzy Search)

What if the user makes a typo and searches for aple instead of apple? They get zero results! We need typo tolerance.

Trigram Indices

To do fast fuzzy searching, real engines build a secondary index of N-Grams.

An N-Gram is a sequence of characters. We will use Trigrams (3 characters). The word apple generates the following trigrams: app, ppl, ple.

Note

What about 1 and 2 letter words? A word like is or a physically cannot form a 3-letter sequence. In practice, search engines handle this in one of two ways:

• Padding: They pad the start and end of words with a special character (like $). So $a$ becomes a trigram, and $is$ becomes [$is, is$].
• Omission: Since 1-2 letter words are almost always stop words (a, is, to, of) that you filtered out in Stage 7, you can usually safely ignore them for fuzzy matching!

Your Task

1. Secondary Index: Build a secondary in-memory Hash Map mapping Trigrams to the actual Terms in your dictionary. (e.g., app -> [apple, application], ppl -> [apple]).
2. Querying: If a user queries a term that does not exist in your dictionary:
   • Break their query into trigrams (e.g., aple -> apl, ple).
   • Look up those trigrams in your secondary index to find candidate terms.
   • Pick the candidate term with the most matching trigrams.
   • Silently replace their typo with the corrected term and run the search!

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 fuzzy_search