Overview

Prerequisites

• Prior topics: SQL Essentials and Data Structures and Algorithms Essentials -- see this topic's own Overview for the full prerequisite rationale.
• Tools & environment: a macOS/Linux terminal; Python at a recent stable release with type hints and pyright. Every example is pure-Python and stdlib-only.
• Assumed knowledge: dictionaries, sets, and sorting by a key; reading and writing a small file from Python.

Why this exists -- the big idea

Index-then-rank: build a term -> documents map once, then let every query do a cheap lookup instead of a per-query scan. This tier turns that one idea into 80 runnable, progressively deeper examples -- from a hand-rolled inverted index through BM25 ranking and evaluation to a typed, incremental, persisted mini search engine.

How this topic is organized

• Beginner (Examples 1-28) -- tokenization (whitespace vs regex), case-folding, building an inverted index and posting lists, boolean AND/OR/NOT, the two-pointer posting-list merge and why scanning loses to indexing, term frequency and idf, stop-words and their recall risk, a from-scratch Porter (1980) stemmer, skip pointers, ranking by tf-idf, and the vector-space model's cosine similarity.
• Intermediate (Examples 29-56) -- BM25's own RSJ idf, saturating tf, and length normalization, sweeping k1/b to see them genuinely change (and even flip) a ranking, the Lucene/Elasticsearch software defaults versus the paper's own recommended range, top-k selection with a size-k heap, the full precision/recall/F1/precision@k/MAP/nDCG evaluation family over a relevance-judgment set, a typed analyzer pipeline model, a small boolean query DSL parsed and executed, positional indexes and the phrase/proximity queries they enable, and a segment-merge model.
• Advanced (Examples 57-80) -- near-real-time refresh semantics, a typed InvertedIndex class with incremental add proven identical to a from-scratch rebuild, JSON/binary/delta-encoded persistence, an incrementally-maintained avgdl, BM25F field weighting versus a broken naive alternative, fuzzy matching (Levenshtein, Damerau-Levenshtein, spelling correction), edge and character n-grams for autocomplete and substring search, synonym expansion, toy semantic embeddings and cosine ranking, approximate versus exact k-NN, hybrid lexical+vector search, PageRank's power iteration alone and combined with BM25, and a final mini search engine assembling the whole pipeline.
• Capstone -- a typed inverted index, BM25 top-k ranking, precision@k evaluation across two analyzer configs, and incremental indexing, assembled behind one small library over a real 8-document text corpus.

Every code example is real, runnable, fully type-annotated, colocated under learning/code/ex-NN-<slug>/, actually executed to capture its documented output -- every printed number on these pages is a genuine, captured transcript, never a fabricated one -- and pyright-clean under # pyright: strict. Run each example with python3 <file>.py from its own learning/code/ex-NN-<slug>/ directory. Where a Lucene-family engine (Elasticsearch/OpenSearch) is discussed, the code remains a pure-Python model of its behavior, never a live dependency.

Examples by Level

Beginner (Examples 1–28)

• Example 1: Tokenize Whitespace
• Example 2: Tokenize Regex
• Example 3: Case Fold
• Example 4: Build Term-Doc Map
• Example 5: Posting List Sorted
• Example 6: Boolean AND
• Example 7: Boolean OR
• Example 8: Boolean NOT
• Example 9: Merge Two Pointer
• Example 10: Scan vs Index Timing
• Example 11: Term Frequency Count
• Example 12: Document Frequency
• Example 13: IDF Formula
• Example 14: TF-IDF Weight
• Example 15: Stop-Word Drop
• Example 16: Stop-Word Recall Risk
• Example 17: Porter Stem
• Example 18: Stem Index Shrink
• Example 19: Lemmatize vs Stem
• Example 20: Normalization Recall Delta
• Example 21: Posting with Frequency
• Example 22: Multi-Term AND
• Example 23: Skip-Pointer Build
• Example 24: Skip-Pointer Merge
• Example 25: Rank by TF-IDF
• Example 26: Vector-Space Vectors
• Example 27: Cosine Similarity
• Example 28: Analyzer Order

Intermediate (Examples 29–56)

• Example 29: BM25 IDF Term
• Example 30: BM25 Score: One Term
• Example 31: BM25 Saturation Curve
• Example 32: TF-IDF vs BM25 Saturation
• Example 33: BM25 Length Normalization
• Example 34: BM25 b Sweep
• Example 35: BM25 k1 Sweep
• Example 36: BM25 Defaults
• Example 37: BM25 Full Ranker
• Example 38: Top-K Heap
• Example 39: Top-K vs Full Sort Timing
• Example 40: Precision/Recall Compute
• Example 41: Precision/Recall Direction
• Example 42: F1 Harmonic Mean
• Example 43: Precision at K
• Example 44: Qrels Load
• Example 45: Evaluate Two Configs
• Example 46: Average Precision
• Example 47: MAP: Multi-Query
• Example 48: nDCG Compute
• Example 49: Analyzer Pipeline Model
• Example 50: Analyzer Swap Filter
• Example 51: Query DSL Parse
• Example 52: Query DSL Execute
• Example 53: Positional Index Build
• Example 54: Phrase Query
• Example 55: Proximity Query
• Example 56: Segment Merge Model

Advanced (Examples 57–80)

• Example 57: NRT Refresh Model
• Example 58: Typed Index Class
• Example 59: Incremental Add
• Example 60: Incremental Equals Rebuild
• Example 61: Persist JSON
• Example 62: Persist Binary
• Example 63: Delta-Encode Postings
• Example 64: avgdl Incremental
• Example 65: BM25F: Fields
• Example 66: BM25F vs Naive
• Example 67: Fuzzy: Levenshtein
• Example 68: Fuzzy: Damerau
• Example 69: Spelling Correct
• Example 70: Edge N-Gram Autocomplete
• Example 71: Char N-Gram Substring
• Example 72: Synonym Expand
• Example 73: Semantic Embedding Cosine
• Example 74: ANN vs Exact kNN
• Example 75: Hybrid Lexical + Vector
• Example 76: Lexical Miss, Semantic Win
• Example 77: PageRank Toy
• Example 78: PageRank + BM25
• Example 79: Evaluate Hybrid
• Example 80: Mini Search Engine

---

← Previous: Overview · Next: Beginner Examples →