Inverted Index & BM25 Ranking Lab (Interactive)
Type queries into a live tokenized corpus and tune k1 and b to reshape Okapi BM25 rankings. A real analyzer and scoring engine: tokenizes six documents, shows per-term postings lists with frequencies, and ranks hits with adjustable BM25 saturation and length normalization.
Inverted Index & Okapi BM25 Ranking
Tokenize a live corpus, walk postings lists, and tune the saturation and length-norm parameters.
Distributed caching with Redis avoids high database load during read-heavy traffic spikes.
66 unique terms in FST dictionary · intersection via skip pointers every 128 doc IDs · drop b to 0 to see long documents outrank concise ones; raise k1 toward 3 to weaken TF saturation.
How It Works Under the Hood
Search engines invert the storage question: instead of document to content, the index maps term to a sorted postings list of document IDs with frequencies. A query analyzes into tokens, intersects postings via skip pointers, and scores survivors with Okapi BM25, whose IDF weights rare terms, whose k1 parameter saturates term frequency so keyword stuffing hits a diminishing-returns asymptote, and whose b penalizes long documents relative to average length. This lab runs the complete pipeline live so you can watch scores recompute as parameters move.
Core Architectural Principles
- Analyzer pipeline lowercases, strips punctuation, and drops stopwords before dictionary lookup.
- Postings lists are sorted doc-ID arrays intersected with skip pointers for AND queries.
- BM25 bounds term-frequency contribution at k1+1 while b scales length normalization.
Draw the inverted index explicitly: term dictionary as an FST in RAM, compressed postings on SSD with deltas and positions for phrase matching. When ranking comes up, contrast TF-IDF linearity with BM25 saturation, and explain why long documents are penalized. Mention immutable Lucene segments and NRT refresh to show production indexing fluency.
Inverted indexes deliver millisecond full-text search but make writes expensive index-builds on immutable segments.