Part 7 · 1 chapters · ~8 min

Capstone: A Small Search Engine

Building a search engine: an analyser with ASCII folding, an inverted index with positions, BM25 scoring, phrase queries, prefix typeahead with a trie, a judged query set with NDCG, and a hybrid mode with embeddings and reciprocal rank fusion.

The build

code

mini-search/
  analyse.ts       tokenise, lowercase, fold diacritics (normalize('NFD') + strip marks), optional English stemmer
  index.ts         postings: Map<term, {docId, tf, positions[]}[]>; doc lengths; persisted to disk as JSON segments
  bm25.ts          score(query) with k1 = 1.2, b = 0.75; top-k with a heap (DSA P4)
  phrase.ts        positional intersection for "mama put"
  typeahead.ts     a trie of popular queries with top-5 completions per node (DSA P3)
  eval.ts          20 queries × graded judgements → NDCG@10; run on every change
  hybrid.ts        embeddings from a local model or API; cosine top-50; RRF with BM25
corpus: 5,000 merchant names and descriptions (synthetic), including Yoruba, Igbo and Hausa names with and without diacritics
goal: NDCG@10 above the BM25 baseline with hybrid; typeahead under 5 ms