Week 11 • Day 2Week 11

Day 2:Week 11, Day 2: Coding an Inverted Index & `Okapi BM25` Search Engine from Scratch

Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz

Week 11, Day 2: Coding an Inverted Index & Okapi BM25 Search Engine from Scratch


1. How an Inverted Index Works Under the Hood

How does Elasticsearch or Lucene score 10,000,000 documents with BM25 in 2 ms without scanning all 10,000,000 documents? It builds an Inverted Index (Posting Lists):

code
Forward Index (Doc -> Words): Doc 0: ["payments", "error", "err_502"] Doc 1: ["database", "failover", "pg_ctl"] Doc 2: ["payments", "rollback", "kubectl"] Inverted Index (Word -> Posting List of (doc_id, term_freq)): "payments" ──► [(Doc 0, tf=1), (Doc 2, tf=1)] "err_502" ──► [(Doc 0, tf=1)] "pg_ctl" ──► [(Doc 1, tf=1)]

At query time, if the user searches "err_502", the engine looks up "err_502" in O(1)O(1) hash time and only scores the documents in its posting list ([Doc 0])!


2. Code-Aware Tokenization for Technical RAG

Standard NLP tokenizers strip underscores and numbers, turning "ERR_PG_9021" into "err" and "pg". In technical/SRE RAG, our tokenizer must preserve alphanumeric identifiers, underscores, hyphens, and error codes (re.findall(r"[a-z0-9_/-]+", text.lower())).


In Simple English: How an Inverted Index Works Like a Textbook Back-of-Book Index

Instead of scanning every document word-by-word when someone searches "redis flushdb": An Inverted Index builds a dictionary flipped backwards ahead of time:

  • "redis" -> [Doc 2, Doc 9, Doc 14]
  • "flushdb" -> [Doc 2] Instant intersection finds Doc 2 in microseconds! Check Tab 2 (Codes) to read and run our pure-Python Inverted Index + BM25 scorer directly inside your browser!