Beginner Examples

# pyright: strict
"""Example 1: Tokenize Whitespace (co-06)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def tokenize_whitespace(text: str) -> list[str]:  # => split text into tokens on any run of whitespace
    """Split text into tokens on any run of whitespace."""
    return text.split()  # => str.split() with no args splits on runs of whitespace, drops empties
 
 
def main() -> None:  # => defines main
    document: str = "the quick brown fox jumps over the lazy dog"  # => 9 space-separated words
    tokens: list[str] = tokenize_whitespace(document)  # => co-06: the first stage of every index pipeline
    print(f"document: {document!r}")  # => shows document
    print(f"tokens: {tokens}")  # => shows tokens
    print(f"token count: {len(tokens)}")  # => shows token count
 
    expected_count: int = len(document.split(" "))  # => an independent count: split on literal " "
    assert len(tokens) == expected_count, "token count must equal the space-separated word count"  # => token count must equal the space-separated word count
    print(f"MATCH: token count ({len(tokens)}) equals the space-separated word count ({expected_count})")  # => shows MATCH: token count (
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

document: 'the quick brown fox jumps over the lazy dog'
tokens: ['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog']
token count: 9
MATCH: token count (9) equals the space-separated word count (9)

# pyright: strict
"""Example 2: Tokenize Regex (co-06)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
import re  # => stdlib regex -- the \w+ tokenizer pattern
 
TOKEN_PATTERN: re.Pattern[str] = re.compile(r"\w+")  # => matches runs of word chars, dropping punctuation
 
 
def tokenize_regex(text: str) -> list[str]:  # => tokenize text with a \\w+ regex, discarding all punctuation
    """Tokenize text with a \\w+ regex, discarding all punctuation."""
    return TOKEN_PATTERN.findall(text)  # => every maximal run of [A-Za-z0-9_], in order
 
 
def main() -> None:  # => defines main
    with_period: str = "this is the end."  # => a sentence ending in a period right after "end"
    without_period: str = "this is the end"  # => the SAME sentence, no trailing period
    tokens_with: list[str] = tokenize_regex(with_period)  # => co-06: regex tokenization strips "."
    tokens_without: list[str] = tokenize_regex(without_period)  # => no punctuation to strip here
    print(f"tokens (with period): {tokens_with}")  # => shows tokens (with period)
    print(f"tokens (without period): {tokens_without}")  # => shows tokens (without period)
 
    assert tokens_with[-1] == "end", "the regex tokenizer must drop the trailing period"  # => the regex tokenizer must drop the trailing period
    assert tokens_with == tokens_without, "'end.' and 'end' must tokenize to the identical token list"  # => 'end.' and 'end' must tokenize to the identical token list
    print("MATCH: 'end.' and 'end' tokenize to the identical list -- punctuation carries no weight to \\w+")  # => shows MATCH: 'end.' and 'end' tokenize to the identical list -- punctuation carries no weight to \\w+
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

tokens (with period): ['this', 'is', 'the', 'end']
tokens (without period): ['this', 'is', 'the', 'end']
MATCH: 'end.' and 'end' tokenize to the identical list -- punctuation carries no weight to \w+

# pyright: strict
"""Example 3: Case Fold (co-07)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def case_fold(tokens: list[str]) -> list[str]:  # => lowercase every token so case variants conflate to one index term
    """Lowercase every token so case variants conflate to one index term."""
    return [t.lower() for t in tokens]  # => str.lower() -- the standard ASCII/Unicode case fold
 
 
def main() -> None:  # => defines main
    tokens: list[str] = ["The", "the", "THE", "ThE"]  # => four case variants of the same word
    folded: list[str] = case_fold(tokens)  # => co-07: every variant becomes the SAME index term
    print(f"before: {tokens}")  # => shows before
    print(f"after:  {folded}")  # => shows after
 
    unique_before: set[str] = set(tokens)  # => 4 distinct strings before folding
    unique_after: set[str] = set(folded)  # => how many distinct strings survive folding
    print(f"unique before: {len(unique_before)} | unique after: {len(unique_after)}")  # => shows unique before
 
    assert len(unique_after) == 1, "all four case variants must collapse to exactly one term"  # => all four case variants must collapse to exactly one term
    assert folded[0] == folded[1] == "the", "'The' and 'the' must both fold to 'the'"  # => 'The' and 'the' must both fold to 'the'
    print("MATCH: 'The' and 'the' (and every other case variant) collapse to the single term 'the'")  # => shows MATCH: 'The' and 'the' (and every other case variant) collapse to the single term 'the'
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

before: ['The', 'the', 'THE', 'ThE']
after:  ['the', 'the', 'the', 'the']
unique before: 4 | unique after: 1
MATCH: 'The' and 'the' (and every other case variant) collapse to the single term 'the'

# pyright: strict
"""Example 4: Build Term-Doc Map (co-01)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def build_term_doc_map(docs: dict[int, list[str]]) -> dict[str, set[int]]:  # => build a term -> set-of-doc-ids inverted index over already-tokenized docs
    """Build a term -> set-of-doc-ids inverted index over already-tokenized docs."""
    index: dict[str, set[int]] = {}  # => co-01: the inverted index -- empty until populated
    for doc_id, tokens in docs.items():  # => one document at a time
        for term in tokens:  # => one term at a time, within this document
            index.setdefault(term, set()).add(doc_id)  # => creates the term's set on first sight, adds doc_id
    return index  # => returns index
 
 
def main() -> None:  # => defines main
    docs: dict[int, list[str]] = {  # => 3 tiny, already-tokenized documents
        0: ["search", "engines", "rank", "documents"],  # => doc 0's tokens, this fixture's row
        1: ["search", "index", "documents", "fast"],  # => doc 1's tokens, this fixture's row
        2: ["rank", "pages", "by", "relevance"],  # => doc 2's tokens, this fixture's row
    }  # => opens/closes this multi-line literal
    index: dict[str, set[int]] = build_term_doc_map(docs)  # => co-01: term -> {doc-ids containing it}
    for term in sorted(index):  # => sorted for deterministic, readable output
        print(f"{term!r}: {sorted(index[term])}")  # => prints this step's result
 
    assert index["search"] == {0, 1}, "'search' must map to exactly docs 0 and 1"  # => 'search' must map to exactly docs 0 and 1
    assert index["rank"] == {0, 2}, "'rank' must map to exactly docs 0 and 2"  # => 'rank' must map to exactly docs 0 and 2
    for term, doc_ids in index.items():  # => a general check across every term, not just the two above
        for doc_id in doc_ids:  # => every doc-id this term claims to appear in
            assert term in docs[doc_id], f"{term!r} claims doc {doc_id} but is absent from it"  # => {term!r} claims doc {doc_id} but is absent from it
    print("MATCH: every term maps to exactly the docs that actually contain it")  # => shows MATCH: every term maps to exactly the docs that actually contain it
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

'by': [2]
'documents': [0, 1]
'engines': [0]
'fast': [1]
'index': [1]
'pages': [2]
'rank': [0, 2]
'relevance': [2]
'search': [0, 1]
MATCH: every term maps to exactly the docs that actually contain it

# pyright: strict
"""Example 5: Posting List Sorted (co-02)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def build_sorted_postings(docs: dict[int, list[str]], term: str) -> list[int]:  # => return term's posting list as a strictly ascending, deduplicated list[int]
    """Return term's posting list as a strictly ascending, deduplicated list[int]."""
    doc_ids: set[int] = {doc_id for doc_id, tokens in docs.items() if term in tokens}  # => co-02: which docs contain term
    return sorted(doc_ids)  # => sorted() guarantees ascending order, the standard posting-list invariant
 
 
def main() -> None:  # => defines main
    docs: dict[int, list[str]] = {  # => doc-ids deliberately inserted OUT of order
        5: ["index", "search"],  # => doc 5's tokens, this fixture's row
        1: ["search", "rank"],  # => doc 1's tokens, this fixture's row
        3: ["search", "documents"],  # => doc 3's tokens, this fixture's row
    }  # => opens/closes this multi-line literal
    postings: list[int] = build_sorted_postings(docs, "search")  # => co-02: term's own posting list
    print(f"docs inserted in order: {list(docs)}")  # => shows docs inserted in order
    print(f"postings for 'search': {postings}")  # => shows postings for 'search'
 
    for i in range(1, len(postings)):  # => walks every adjacent pair
        assert postings[i] > postings[i - 1], "postings must be STRICTLY ascending, no ties or drops"  # => postings must be STRICTLY ascending, no ties or drops
    print(f"MATCH: postings {postings} are strictly ascending despite docs being inserted as {list(docs)}")  # => shows MATCH: postings
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

docs inserted in order: [5, 1, 3]
postings for 'search': [1, 3, 5]
MATCH: postings [1, 3, 5] are strictly ascending despite docs being inserted as [5, 1, 3]

# pyright: strict
"""Example 6: Boolean AND (co-03, co-04)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def boolean_and(postings_a: list[int], postings_b: list[int]) -> list[int]:  # => intersect two SORTED posting lists -- an AND query (co-03)
    """Intersect two SORTED posting lists -- an AND query (co-03)."""
    return sorted(set(postings_a) & set(postings_b))  # => co-04: set intersection IS boolean AND
 
 
def main() -> None:  # => defines main
    search_postings: list[int] = [1, 3, 5, 7, 9]  # => docs containing "search"
    engine_postings: list[int] = [2, 3, 5, 8, 9]  # => docs containing "engine"
    result: list[int] = boolean_and(search_postings, engine_postings)  # => docs with BOTH terms
    print(f"search postings: {search_postings}")  # => shows search postings
    print(f"engine postings: {engine_postings}")  # => shows engine postings
    print(f"search AND engine: {result}")  # => shows search AND engine
 
    expected: list[int] = sorted(set(search_postings) & set(engine_postings))  # => Python's own set '&'
    assert result == expected, "boolean_and must match Python's native set intersection"  # => boolean_and must match Python's native set intersection
    print(f"MATCH: boolean_and's result equals Python's set '&' result ({expected})")  # => shows MATCH: boolean_and's result equals Python's set '&' result (
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

search postings: [1, 3, 5, 7, 9]
engine postings: [2, 3, 5, 8, 9]
search AND engine: [3, 5, 9]
MATCH: boolean_and's result equals Python's set '&' result ([3, 5, 9])

# pyright: strict
"""Example 7: Boolean OR (co-03, co-04)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def boolean_or(postings_a: list[int], postings_b: list[int]) -> list[int]:  # => union two SORTED posting lists -- an OR query (co-03)
    """Union two SORTED posting lists -- an OR query (co-03)."""
    return sorted(set(postings_a) | set(postings_b))  # => co-04: set union IS boolean OR
 
 
def main() -> None:  # => defines main
    search_postings: list[int] = [1, 3, 5]  # => docs containing "search"
    rank_postings: list[int] = [2, 3, 6]  # => docs containing "rank"
    result: list[int] = boolean_or(search_postings, rank_postings)  # => docs with EITHER term
    print(f"search postings: {search_postings}")  # => shows search postings
    print(f"rank postings: {rank_postings}")  # => shows rank postings
    print(f"search OR rank: {result}")  # => shows search OR rank
 
    expected: list[int] = sorted(set(search_postings) | set(rank_postings))  # => Python's own set '|'
    assert result == expected, "boolean_or must match Python's native set union"  # => boolean_or must match Python's native set union
    print(f"MATCH: boolean_or's result equals Python's set '|' result ({expected})")  # => shows MATCH: boolean_or's result equals Python's set '|' result (
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

search postings: [1, 3, 5]
rank postings: [2, 3, 6]
search OR rank: [1, 2, 3, 5, 6]
MATCH: boolean_or's result equals Python's set '|' result ([1, 2, 3, 5, 6])

# pyright: strict
"""Example 8: Boolean NOT (co-03)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def boolean_not(all_docs: list[int], postings: list[int]) -> list[int]:  # => return every doc-id NOT present in postings -- a NOT query (co-03)
    """Return every doc-id NOT present in postings -- a NOT query (co-03)."""
    return sorted(set(all_docs) - set(postings))  # => the full universe, minus this term's postings
 
 
def main() -> None:  # => defines main
    all_docs: list[int] = [0, 1, 2, 3, 4, 5]  # => every document id in the corpus
    deprecated_postings: list[int] = [1, 3]  # => docs containing the term "deprecated"
    result: list[int] = boolean_not(all_docs, deprecated_postings)  # => docs WITHOUT "deprecated"
    print(f"all docs: {all_docs}")  # => shows all docs
    print(f"'deprecated' postings: {deprecated_postings}")  # => shows 'deprecated' postings
    print(f"NOT deprecated: {result}")  # => shows NOT deprecated
 
    for doc_id in deprecated_postings:  # => every excluded doc-id
        assert doc_id not in result, f"doc {doc_id} contains 'deprecated' and must be excluded"  # => doc {doc_id} contains 'deprecated' and must be excluded
    for doc_id in result:  # => every doc-id that DID survive
        assert doc_id not in deprecated_postings, f"doc {doc_id} leaked into the NOT result"  # => doc {doc_id} leaked into the NOT result
    print(f"MATCH: every doc in {deprecated_postings} is excluded, every other doc in {all_docs} survives")  # => shows MATCH: every doc in
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

all docs: [0, 1, 2, 3, 4, 5]
'deprecated' postings: [1, 3]
NOT deprecated: [0, 2, 4, 5]
MATCH: every doc in [1, 3] is excluded, every other doc in [0, 1, 2, 3, 4, 5] survives

# pyright: strict
"""Example 9: Merge Two Pointer (co-04)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
import random  # => stdlib PRNG -- reproducible synthetic fixtures and trials
 
 
def merge_and_two_pointer(a: list[int], b: list[int]) -> list[int]:  # => intersect two SORTED posting lists with a single linear two-pointer pass
    """Intersect two SORTED posting lists with a single linear two-pointer pass."""
    result: list[int] = []  # => accumulates matching doc-ids, in order
    i = j = 0  # => one cursor per list -- each only ever moves forward
    while i < len(a) and j < len(b):  # => stop the instant either list is exhausted
        if a[i] == b[j]:  # => a match -- record it and advance BOTH cursors
            result.append(a[i])  # => records this item, in order
            i += 1  # => advances i
            j += 1  # => advances j
        elif a[i] < b[j]:  # => a[i] can never match anything later in b -- advance i only
            i += 1  # => advances i
        else:  # => b[j] can never match anything later in a -- advance j only
            j += 1  # => advances j
    return result  # => every doc-id present in both a and b, ascending
 
 
def main() -> None:  # => defines main
    rng = random.Random(42)  # => fixed seed -- reproducible random trials
    for trial in range(200):  # => 200 random posting-list pairs
        size_a, size_b = rng.randint(0, 20), rng.randint(0, 20)  # => varying sizes, including empty
        a: list[int] = sorted({rng.randint(0, 30) for _ in range(size_a)})  # => a valid sorted posting list
        b: list[int] = sorted({rng.randint(0, 30) for _ in range(size_b)})  # => another valid sorted posting list
        got: list[int] = merge_and_two_pointer(a, b)  # => the two-pointer algorithm's own answer
        expected: list[int] = sorted(set(a) & set(b))  # => the reference answer, via Python's set '&'
        assert got == expected, f"trial {trial}: {a} & {b} -> got {got}, expected {expected}"  # => trial {trial}: {a} & {b} -> got {got}, expected {expected}
 
    sample_a: list[int] = [1, 3, 5, 7, 9, 11]  # => a small, readable example for the printed output
    sample_b: list[int] = [2, 3, 4, 7, 8, 11]  # => sample b = [2, 3, 4, 7, 8, 11]
    print(f"a={sample_a}")  # => shows a=
    print(f"b={sample_b}")  # => shows b=
    print(f"merge_and_two_pointer(a, b) = {merge_and_two_pointer(sample_a, sample_b)}")  # => shows merge_and_two_pointer(a, b) =
    print("MATCH: two-pointer intersection equals Python's set '&' across 200 random trials, one pass each")  # => shows MATCH: two-pointer intersection equals Python's set '&' across 200 random trials, one pass each
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

a=[1, 3, 5, 7, 9, 11]
b=[2, 3, 4, 7, 8, 11]
merge_and_two_pointer(a, b) = [3, 7, 11]
MATCH: two-pointer intersection equals Python's set '&' across 200 random trials, one pass each

# pyright: strict
"""Example 10: Scan vs Index Timing (co-01)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
import time  # => stdlib timer -- wall-clock measurement, not a benchmark micro-op
 
 
def build_docs(n: int) -> list[str]:  # => build n synthetic documents; only ONE additional document contains the needle term
    """Build n synthetic documents; only ONE additional document contains the needle term."""
    docs: list[str] = [f"filler words about topic number {i} nothing relevant here" for i in range(n)]  # => n non-matching docs
    docs.append("this final document mentions the needle term explicitly")  # => the ONE doc containing "needle"
    return docs  # => returns docs
 
 
def scan_time(docs: list[str], term: str) -> float:  # => time a naive substring scan across every document -- O(N) per query
    """Time a naive substring scan across every document -- O(N) per query."""
    start: float = time.perf_counter()  # => wall-clock start
    _ = [d for d in docs if term in d]  # => co-01: must touch EVERY doc, no matter where the match is
    return time.perf_counter() - start  # => elapsed seconds for this one scan
 
 
def index_lookup_time(index: dict[str, list[int]], term: str) -> float:  # => time a single dict lookup against a pre-built inverted index -- O(1) amortized
    """Time a single dict lookup against a pre-built inverted index -- O(1) amortized."""
    start: float = time.perf_counter()  # => wall-clock start
    _ = index.get(term, [])  # => co-01: a single hash lookup, regardless of corpus size
    return time.perf_counter() - start  # => elapsed seconds for this one lookup
 
 
def main() -> None:  # => defines main
    sizes: tuple[int, ...] = (2_000, 8_000, 32_000)  # => geometrically growing corpus sizes
    scan_seconds_by_n: dict[int, float] = {}  # => remembers each N's own best scan time, for the check below
    for n in sizes:  # => iterates one item at a time
        docs: list[str] = build_docs(n)  # => n+1 documents total
        index: dict[str, list[int]] = {"needle": [n]}  # => the pre-built index already knows WHERE "needle" is
        scan_seconds: float = min(scan_time(docs, "needle") for _ in range(5))  # => best of 5, reduces noise
        index_seconds: float = min(index_lookup_time(index, "needle") for _ in range(5))  # => best of 5
        scan_seconds_by_n[n] = scan_seconds  # => stored for the growth check below
        ratio: float = scan_seconds / index_seconds if index_seconds > 0 else float("inf")  # => how much slower the scan is
        print(f"N={n:>6}: scan={scan_seconds * 1e6:9.1f}us  index={index_seconds * 1e6:8.3f}us  ratio={ratio:8.0f}x")  # => shows N=
 
    assert scan_seconds_by_n[sizes[-1]] > scan_seconds_by_n[sizes[0]], "scan time must rise as N grows"  # => scan time must rise as N grows
    print(  # => prints this step's result
        f"MATCH: scan time rises with N ({scan_seconds_by_n[sizes[0]] * 1e6:.1f}us -> "  # => continues the f-string/message started on the prior line
        f"{scan_seconds_by_n[sizes[-1]] * 1e6:.1f}us) while an index lookup stays a flat, single hash lookup"  # => continues the f-string/message started on the prior line
    )  # => opens/closes this multi-line literal
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

N=  2000: scan=     43.1us  index=   0.083us  ratio=     520x
N=  8000: scan=    170.8us  index=   0.041us  ratio=    4169x
N= 32000: scan=    715.3us  index=   0.041us  ratio=   17407x
MATCH: scan time rises with N (43.1us -> 715.3us) while an index lookup stays a flat, single hash lookup

# pyright: strict
"""Example 11: Term Frequency Count (co-12)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def term_frequency(tokens: list[str]) -> dict[str, int]:  # => count how many times each term appears in one document's token list
    """Count how many times each term appears in one document's token list."""
    tf: dict[str, int] = {}  # => co-12: term -> raw occurrence count, within THIS one document
    for term in tokens:  # => one token at a time
        tf[term] = tf.get(term, 0) + 1  # => starts at 0 on first sight, then increments
    return tf  # => returns tf
 
 
def main() -> None:  # => defines main
    doc_text: str = "search engines index documents so search stays fast for every search"  # => the sample document
    doc_tokens: list[str] = [str(t) for t in doc_text.split()]  # => co-06: whitespace tokenization, as in Example 1 (str(t) widens pyright's LiteralString inference to plain str)
    tf: dict[str, int] = term_frequency(doc_tokens)  # => co-12: this document's own term-frequency table
    for term in sorted(tf, key=lambda t: (-tf[t], t)):  # => most frequent first, alphabetical tiebreak
        print(f"{term!r}: tf={tf[term]}")  # => prints this step's result
 
    assert tf["search"] == 3, "'search' appears 3 times in the sample document"  # => 'search' appears 3 times in the sample document
    assert tf["engines"] == 1, "'engines' appears exactly once"  # => 'engines' appears exactly once
    assert sum(tf.values()) == len(doc_tokens), "tf counts must sum to the total token count"  # => tf counts must sum to the total token count
    print(f"MATCH: tf['search']={tf['search']} (repeated term, count > 1) and counts sum to {len(doc_tokens)} tokens")  # => shows MATCH: tf['search']=
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

'search': tf=3
'documents': tf=1
'engines': tf=1
'every': tf=1
'fast': tf=1
'for': tf=1
'index': tf=1
'so': tf=1
'stays': tf=1
MATCH: tf['search']=3 (repeated term, count > 1) and counts sum to 11 tokens

# pyright: strict
"""Example 12: Document Frequency (co-13)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
 
def document_frequency(docs: dict[int, list[str]]) -> dict[str, int]:  # => count, per term, how many documents contain it at least once
    """Count, per term, how many documents contain it at least once."""
    df: dict[str, int] = {}  # => co-13: term -> number of DOCUMENTS (not occurrences) containing it
    for tokens in docs.values():  # => one document's token list at a time
        for term in set(tokens):  # => set() -- a term counts ONCE per document, however often it repeats
            df[term] = df.get(term, 0) + 1  # => counter pattern: 0 on first sight, then increments
    return df  # => returns df
 
 
def main() -> None:  # => defines main
    docs: dict[int, list[str]] = {  # => "search" appears in every doc; "engine" only in doc 0
        0: ["search", "engine", "search", "ranks"],  # => "search" repeats but still counts once for df
        1: ["search", "index", "documents"],  # => doc 1's tokens, this fixture's row
        2: ["search", "fast", "results"],  # => doc 2's tokens, this fixture's row
    }  # => opens/closes this multi-line literal
    n_docs: int = len(docs)  # => N, the total corpus size
    df: dict[str, int] = document_frequency(docs)  # => co-13: this corpus's own document-frequency table
    for term in sorted(df):  # => iterates one item at a time
        print(f"{term!r}: df={df[term]} of N={n_docs}")  # => prints this step's result
 
    assert df["search"] == n_docs, "'search' appears in EVERY doc, so its df must equal N"  # => 'search' appears in EVERY doc, so its df must equal N
    assert df["engine"] == 1, "'engine' appears in exactly one document"  # => 'engine' appears in exactly one document
    print(f"MATCH: df['search']={df['search']} equals N={n_docs} (present in every doc)")  # => shows MATCH: df['search']=
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

'documents': df=1 of N=3
'engine': df=1 of N=3
'fast': df=1 of N=3
'index': df=1 of N=3
'ranks': df=1 of N=3
'results': df=1 of N=3
'search': df=3 of N=3
MATCH: df['search']=3 equals N=3 (present in every doc)

# pyright: strict
"""Example 13: IDF Formula (co-13)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
import math  # => stdlib math -- log/sqrt for idf, cosine, and skip-pointer spacing
 
 
def idf(term_df: int, n_docs: int) -> float:  # => inverse document frequency: idf = log(N / df) (IR-book form)
    """Inverse document frequency: idf = log(N / df) (IR-book form)."""
    return math.log(n_docs / term_df)  # => co-13: rarer term (small df) -> larger idf
 
 
def main() -> None:  # => defines main
    n_docs: int = 1_000  # => corpus size N
    common_df: int = 900  # => "the" -- appears in almost every document
    rare_df: int = 5  # => "quasar" -- appears in almost none
 
    common_idf: float = idf(common_df, n_docs)  # => a near-ubiquitous term
    rare_idf: float = idf(rare_df, n_docs)  # => a genuinely rare term
    print(f"idf('the',    df={common_df:>4}/{n_docs}) = {common_idf:.4f}")  # => shows idf('the',    df=
    print(f"idf('quasar', df={rare_df:>4}/{n_docs}) = {rare_idf:.4f}")  # => shows idf('quasar', df=
 
    all_docs_idf: float = idf(n_docs, n_docs)  # => a term present in EVERY document
    print(f"idf(term in every doc, df={n_docs}/{n_docs}) = {all_docs_idf:.4f}")  # => shows idf(term in every doc, df=
 
    assert rare_idf > common_idf, "a rarer term (lower df) must have a LARGER idf"  # => a rarer term (lower df) must have a LARGER idf
    assert math.isclose(all_docs_idf, 0.0, abs_tol=1e-9), "a term in every doc must have idf == 0"  # => a term in every doc must have idf == 0
    print(f"MATCH: rare_idf ({rare_idf:.4f}) exceeds common_idf ({common_idf:.4f}), and a ubiquitous term scores idf=0")  # => shows MATCH: rare_idf (
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

idf('the',    df= 900/1000) = 0.1054
idf('quasar', df=   5/1000) = 5.2983
idf(term in every doc, df=1000/1000) = 0.0000
MATCH: rare_idf (5.2983) exceeds common_idf (0.1054), and a ubiquitous term scores idf=0

# pyright: strict
"""Example 14: TF-IDF Weight (co-14)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
import math  # => stdlib math -- log/sqrt for idf, cosine, and skip-pointer spacing
 
 
def term_frequency(tokens: list[str]) -> dict[str, int]:  # => defines term frequency
    tf: dict[str, int] = {}  # => starts empty, populated by the loop below
    for term in tokens:  # => iterates one item at a time
        tf[term] = tf.get(term, 0) + 1  # => counter pattern: 0 on first sight, then increments
    return tf  # => returns tf
 
 
def document_frequency(docs: dict[int, list[str]]) -> dict[str, int]:  # => defines document frequency
    df: dict[str, int] = {}  # => starts empty, populated by the loop below
    for tokens in docs.values():  # => iterates one item at a time
        for term in set(tokens):  # => iterates one item at a time
            df[term] = df.get(term, 0) + 1  # => counter pattern: 0 on first sight, then increments
    return df  # => returns df
 
 
def tf_idf_matrix(docs: dict[int, list[str]]) -> dict[int, dict[str, float]]:  # => compute tf-idf for every (term, doc) pair: weight = tf * log(N / df)
    """Compute tf-idf for every (term, doc) pair: weight = tf * log(N / df)."""
    n_docs: int = len(docs)  # => N -- needed by every idf() call below
    df: dict[str, int] = document_frequency(docs)  # => co-13: corpus-wide document frequencies
    matrix: dict[int, dict[str, float]] = {}  # => co-14: doc_id -> {term: tf-idf weight}
    for doc_id, tokens in docs.items():  # => iterates one item at a time
        tf: dict[str, int] = term_frequency(tokens)  # => co-12: this doc's own term frequencies
        matrix[doc_id] = {term: count * math.log(n_docs / df[term]) for term, count in tf.items()}  # => co-14: tf * idf
    return matrix  # => returns matrix
 
 
def main() -> None:  # => defines main
    docs: dict[int, list[str]] = {  # => a tiny 3-doc fixture, hand-verifiable; "index" is in ALL 3 docs on purpose
        0: ["search", "engine", "search", "index"],  # => doc 0's tokens, this fixture's row
        1: ["search", "index"],  # => doc 1's tokens, this fixture's row
        2: ["index", "index", "fast"],  # => doc 2's tokens, this fixture's row
    }  # => opens/closes this multi-line literal
    matrix: dict[int, dict[str, float]] = tf_idf_matrix(docs)  # => co-14: the full tf-idf weight matrix
    for doc_id in sorted(matrix):  # => iterates one item at a time
        weights: dict[str, float] = matrix[doc_id]  # => weights = matrix[doc_id]
        print(f"doc {doc_id}: " + ", ".join(f"{t}={w:.4f}" for t, w in sorted(weights.items())))  # => shows doc
 
    n_docs: int = len(docs)  # => this fixture's own size
    hand_weight_search_doc0: float = 2 * math.log(n_docs / 2)  # => tf("search", doc0)=2, df("search")=2
    assert math.isclose(matrix[0]["search"], hand_weight_search_doc0, abs_tol=1e-9), "doc 0's 'search' weight must match the hand computation tf=2 * log(3/2)"  # => doc 0's 'search' weight must match the hand computation tf=2 * log(3/2)
    hand_weight_index_doc2: float = 2 * math.log(n_docs / 3)  # => tf("index", doc2)=2, df("index")=3 (present in ALL docs)
    assert math.isclose(matrix[2]["index"], hand_weight_index_doc2, abs_tol=1e-9), "doc 2's 'index' weight must be 0 -- 'index' appears in all 3 docs, so idf('index') == 0"  # => doc 2's 'index' weight must be 0 -- 'index' appears in all 3 docs, so idf('index') == 0
    print("MATCH: the computed tf-idf matrix equals the hand-derived weights for 'search' in doc 0 and 'index' in doc 2")  # => shows MATCH: the computed tf-idf matrix equals the hand-derived weights for 'search' in doc 0 and 'index' in doc 2
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

doc 0: engine=1.0986, index=0.0000, search=0.8109
doc 1: index=0.0000, search=0.4055
doc 2: fast=1.0986, index=0.0000
MATCH: the computed tf-idf matrix equals the hand-derived weights for 'search' in doc 0 and 'index' in doc 2

# pyright: strict
"""Example 15: Stop-Word Drop (co-08)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
STOP_WORDS: frozenset[str] = frozenset({"the", "a", "an", "of", "in", "on", "and", "or", "to", "is", "are", "for"})  # => STOP WORDS = frozenset({"the", "a", "an", "of", "in", "on", ...
# => co-08: a small, deliberately narrow stop-word list -- high frequency, low signal
 
 
def remove_stop_words(tokens: list[str]) -> list[str]:  # => drop every token that is in the stop-word list, preserving relative order
    """Drop every token that is in the stop-word list, preserving relative order."""
    return [t for t in tokens if t not in STOP_WORDS]  # => co-08: filters out low-signal terms
 
 
def main() -> None:  # => defines main
    text: str = "the quick brown fox jumps over the lazy dog and the cat"  # => the sample document
    tokens: list[str] = [str(t) for t in text.split()]  # => co-06: whitespace tokenization, as in Example 1 (str(t) widens pyright's LiteralString inference to plain str)
    filtered: list[str] = remove_stop_words(tokens)  # => co-08: the same tokens, stop words dropped
    print(f"before ({len(tokens)} tokens): {tokens}")  # => shows before (
    print(f"after  ({len(filtered)} tokens): {filtered}")  # => shows after  (
 
    assert "the" not in filtered, "'the' must be fully removed by stop-word filtering"  # => 'the' must be fully removed by stop-word filtering
    assert "and" not in filtered, "'and' must be fully removed by stop-word filtering"  # => 'and' must be fully removed by stop-word filtering
    assert len(filtered) < len(tokens), "the total token count must strictly fall after removal"  # => the total token count must strictly fall after removal
    print(f"MATCH: 'the' is absent and the token count dropped from {len(tokens)} to {len(filtered)}")  # => shows MATCH: 'the' is absent and the token count dropped from
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

before (12 tokens): ['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog', 'and', 'the', 'cat']
after  (8 tokens): ['quick', 'brown', 'fox', 'jumps', 'over', 'lazy', 'dog', 'cat']
MATCH: 'the' is absent and the token count dropped from 12 to 8

# pyright: strict
"""Example 16: Stop-Word Recall Risk (co-08, co-11)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
STOP_WORDS: frozenset[str] = frozenset({"the", "a", "an", "of", "in", "on", "and", "or", "to", "is", "are", "for"})  # => STOP WORDS = frozenset({"the", "a", "an", "of", "in", "on", ...
 
 
def build_index(docs: dict[int, list[str]], *, drop_stop_words: bool) -> dict[str, set[int]]:  # => build a term -> doc-id-set index, optionally dropping stop words first
    """Build a term -> doc-id-set index, optionally dropping stop words first."""
    index: dict[str, set[int]] = {}  # => starts empty, populated by the loop below
    for doc_id, tokens in docs.items():  # => iterates one item at a time
        kept: list[str] = [t for t in tokens if not (drop_stop_words and t in STOP_WORDS)]  # => co-08: the filter, if enabled
        for term in kept:  # => iterates one item at a time
            index.setdefault(term, set()).add(doc_id)  # => part of this step's computation, continued from the line above
    return index  # => returns index
 
 
def query_and(index: dict[str, set[int]], terms: list[str]) -> set[int]:  # => a boolean AND query -- terms absent from the index contribute an empty set
    """A boolean AND query -- terms absent from the index contribute an empty set."""
    result: set[int] | None = None  # => result = None
    for term in terms:  # => iterates one item at a time
        postings: set[int] = index.get(term, set())  # => co-11: a stop word never indexed returns EMPTY
        result = postings if result is None else result & postings  # => result = postings if result is None else result & postings
    return result or set()  # => returns result or set()
 
 
def main() -> None:  # => defines main
    docs: dict[int, list[str]] = {0: ["to", "be", "or", "not", "to", "be"], 1: ["the", "answer", "is", "42"]}  # => docs = {0: ["to", "be", "or", "not", "to", "be"], 1: [...
    stripped_index: dict[str, set[int]] = build_index(docs, drop_stop_words=True)  # => co-08: stop words dropped
    full_index: dict[str, set[int]] = build_index(docs, drop_stop_words=False)  # => a baseline WITHOUT the filter
 
    stripped_hits: set[int] = query_and(stripped_index, ["to", "be", "or"])  # => a phrase of ONLY stop words
    full_hits: set[int] = query_and(full_index, ["to", "be", "or"])  # => the SAME phrase, unstripped index
    print(f"query ['to', 'be', 'or'] against STRIPPED index: {sorted(stripped_hits)}")  # => shows query ['to', 'be', 'or'] against STRIPPED index
    print(f"query ['to', 'be', 'or'] against FULL index:     {sorted(full_hits)}")  # => shows query ['to', 'be', 'or'] against FULL index
 
    assert stripped_hits == set(), "the stripped index must return NOTHING for an all-stop-word query"  # => the stripped index must return NOTHING for an all-stop-word query
    assert full_hits == {0}, "the unstripped index must still find doc 0, 'To be or not to be'"  # => the unstripped index must still find doc 0, 'To be or not to be'
    print("MATCH: the stripped index returns empty (recall lost) where the unstripped index correctly finds doc 0")  # => shows MATCH: the stripped index returns empty (recall lost) where the unstripped index correctly finds doc 0
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

query ['to', 'be', 'or'] against STRIPPED index: []
query ['to', 'be', 'or'] against FULL index:     [0]
MATCH: the stripped index returns empty (recall lost) where the unstripped index correctly finds doc 0

# pyright: strict
"""Example 17: Porter Stem (co-09).
 
A from-scratch implementation of Porter's (1980) suffix-stripping algorithm,
following the paper's own Steps 1a through 5b in order.
"""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
def _cv_string(word: str) -> str:  # => classify every letter of word as 'c' (consonant) or 'v' (vowel) per
    """Classify every letter of word as 'c' (consonant) or 'v' (vowel) per
    Porter's definition, where 'y' is a vowel only when preceded by a
    consonant (or is a consonant at word-start)."""
    result: list[str] = []  # => starts empty, populated by the loop below
    for i, ch in enumerate(word):  # => iterates one item at a time
        if ch in "aeiou":  # => true when ch in "aeiou"
            result.append("v")  # => records this item, in order
        elif ch == "y":  # => otherwise, true when ch == "y"
            result.append("c" if i == 0 or result[i - 1] == "v" else "v")  # => records this item, in order
        else:  # => the fallback branch, when no prior condition matched
            result.append("c")  # => records this item, in order
    return "".join(result)  # => returns "".join(result)
 
 
def _measure(stem: str) -> int:  # => porter's m: the count of VC repetitions in [C](VC)^m[V]
    """Porter's m: the count of VC repetitions in [C](VC)^m[V]."""
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    collapsed: list[str] = []  # => starts empty, populated by the loop below
    for ch in cv:  # => collapses runs of the same letter type into one marker
        if not collapsed or collapsed[-1] != ch:  # => true when not collapsed or collapsed[-1] != ch
            collapsed.append(ch)  # => records this item, in order
    pattern = "".join(collapsed)  # => pattern = "".join(collapsed)
    if pattern.startswith("c"):  # => true when pattern.startswith("c")
        pattern = pattern[1:]  # => strips the optional leading consonant run
    if pattern.endswith("v"):  # => true when pattern.endswith("v")
        pattern = pattern[:-1]  # => strips the optional trailing vowel run
    return len(pattern) // 2  # => what remains is (vc)^m -- each pair is one unit of measure
 
 
def _contains_vowel(stem: str) -> bool:  # => defines  contains vowel
    return "v" in _cv_string(stem)  # => the *v* condition Porter's ED/ING rules require
 
 
def _ends_double_consonant(stem: str) -> bool:  # => defines  ends double consonant
    if len(stem) < 2:  # => true when len(stem) < 2
        return False  # => returns False
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    return cv[-1] == "c" and cv[-2] == "c" and stem[-1] == stem[-2]  # => e.g. "hopp"
 
 
def _ends_cvc(stem: str) -> bool:  # => defines  ends cvc
    if len(stem) < 3:  # => true when len(stem) < 3
        return False  # => returns False
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    return cv[-3:] == "cvc" and stem[-1] not in "wxy"  # => Porter's *o condition
 
 
def _step1a(word: str) -> str:  # => defines  step1a
    if word.endswith("sses"):  # => true when word.endswith("sses")
        return word[:-2]  # => caresses -> caress
    if word.endswith("ies"):  # => true when word.endswith("ies")
        return word[:-2]  # => ponies -> poni
    if word.endswith("ss"):  # => true when word.endswith("ss")
        return word  # => caress -> caress (unchanged)
    if word.endswith("s"):  # => true when word.endswith("s")
        return word[:-1]  # => cats -> cat
    return word  # => returns word
 
 
def _step1b_cleanup(stem: str) -> str:  # => defines  step1b cleanup
    if stem.endswith(("at", "bl", "iz")):  # => true when stem.endswith(("at", "bl", "iz"))
        return stem + "e"  # => conflat(ed) -> conflate
    if _ends_double_consonant(stem) and not stem.endswith(("l", "s", "z")):  # => true when _ends_double_consonant(stem) and not stem.endswith((...
        return stem[:-1]  # => hopp(ing) -> hop
    if _measure(stem) == 1 and _ends_cvc(stem):  # => true when _measure(stem) == 1 and _ends_cvc(stem)
        return stem + "e"  # => fil(ing) -> file
    return stem  # => returns stem
 
 
def _step1b(word: str) -> str:  # => defines  step1b
    if word.endswith("eed"):  # => true when word.endswith("eed")
        stem = word[:-3]  # => stem = word[:-3]
        return stem + "ee" if _measure(stem) > 0 else word  # => agreed -> agree
    if word.endswith("ed"):  # => true when word.endswith("ed")
        stem = word[:-2]  # => stem = word[:-2]
        return _step1b_cleanup(stem) if _contains_vowel(stem) else word  # => returns _step1b_cleanup(stem) if _contains_vowel(stem) else word
    if word.endswith("ing"):  # => true when word.endswith("ing")
        stem = word[:-3]  # => stem = word[:-3]
        return _step1b_cleanup(stem) if _contains_vowel(stem) else word  # => returns _step1b_cleanup(stem) if _contains_vowel(stem) else word
    return word  # => returns word
 
 
def _step1c(word: str) -> str:  # => defines  step1c
    if word.endswith("y") and _contains_vowel(word[:-1]):  # => true when word.endswith("y") and _contains_vowel(word[:-1])
        return word[:-1] + "i"  # => happy -> happi
    return word  # => returns word
 
 
_STEP2 = [  # =>  STEP2 = [
    ("ational", "ate"), ("tional", "tion"), ("enci", "ence"), ("anci", "ance"),  # => part of this step's computation, continued from the line above
    ("izer", "ize"), ("abli", "able"), ("alli", "al"), ("entli", "ent"),  # => part of this step's computation, continued from the line above
    ("eli", "e"), ("ousli", "ous"), ("ization", "ize"), ("ation", "ate"),  # => part of this step's computation, continued from the line above
    ("ator", "ate"), ("alism", "al"), ("iveness", "ive"), ("fulness", "ful"),  # => part of this step's computation, continued from the line above
    ("ousness", "ous"), ("aliti", "al"), ("iviti", "ive"), ("biliti", "ble"),  # => part of this step's computation, continued from the line above
]  # => sorted longest-suffix-first below, so "ization" wins over "ation"
 
 
def _step2(word: str) -> str:  # => defines  step2
    for suf, repl in sorted(_STEP2, key=lambda p: len(p[0]), reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem + repl if _measure(stem) > 0 else word  # => relational -> relate
    return word  # => returns word
 
 
_STEP3 = [("icate", "ic"), ("ative", ""), ("alize", "al"), ("iciti", "ic"), ("ical", "ic"), ("ful", ""), ("ness", "")]  # =>  STEP3 = [("icate", "ic"), ("ative", ""), ("alize", "al"...
 
 
def _step3(word: str) -> str:  # => defines  step3
    for suf, repl in sorted(_STEP3, key=lambda p: len(p[0]), reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem + repl if _measure(stem) > 0 else word  # => hopeful -> hope
    return word  # => returns word
 
 
_STEP4 = ["al", "ance", "ence", "er", "ic", "able", "ible", "ant", "ement", "ment", "ent", "ou", "ism", "ate", "iti", "ous", "ive", "ize"]  # =>  STEP4 = ["al", "ance", "ence", "er", "ic", "able", "ibl...
 
 
def _step4(word: str) -> str:  # => defines  step4
    if word.endswith("ion"):  # => true when word.endswith("ion")
        stem = word[:-3]  # => stem = word[:-3]
        if _measure(stem) > 1 and stem.endswith(("s", "t")):  # => true when _measure(stem) > 1 and stem.endswith(("s", "t"))
            return stem  # => adoption -> adopt (only after s/t, and only if m>1)
    for suf in sorted(_STEP4, key=len, reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem if _measure(stem) > 1 else word  # => airliner -> airlin (m>1 required)
    return word  # => returns word
 
 
def _step5a(word: str) -> str:  # => defines  step5a
    if word.endswith("e"):  # => true when word.endswith("e")
        stem = word[:-1]  # => stem = word[:-1]
        m = _measure(stem)  # => m = _measure(stem)
        if m > 1 or (m == 1 and not _ends_cvc(stem)):  # => true when m > 1 or (m == 1 and not _ends_cvc(stem))
            return stem  # => probate -> probat, but cease stays cease (m==1 and *o)
    return word  # => returns word
 
 
def _step5b(word: str) -> str:  # => defines  step5b
    if _measure(word) > 1 and _ends_double_consonant(word) and word.endswith("l"):  # => true when _measure(word) > 1 and _ends_double_consonant(word) ...
        return word[:-1]  # => controll -> control
    return word  # => returns word
 
 
def porter_stem(word: str) -> str:  # => reduce word to its Porter (1980) stem by chaining Steps 1a through 5b
    """Reduce word to its Porter (1980) stem by chaining Steps 1a through 5b."""
    if len(word) <= 2:  # => true when len(word) <= 2
        return word  # => Porter's algorithm is a no-op below 3 letters
    w = word.lower()  # => w = word.lower()
    for step in (_step1a, _step1b, _step1c, _step2, _step3, _step4, _step5a, _step5b):  # => iterates one item at a time
        w = step(w)  # => each step's OUTPUT feeds the next step's INPUT, in this fixed order
    return w  # => returns w
 
 
def main() -> None:  # => defines main
    words: list[str] = ["running", "runs", "runner"]  # => the three forms ex-17 exercises
    stems: dict[str, str] = {w: porter_stem(w) for w in words}  # => co-09: each word's own Porter stem
    for w in words:  # => iterates one item at a time
        print(f"porter_stem({w!r}) = {stems[w]!r}")  # => shows porter_stem(
 
    assert stems["running"] == "run", "'running' must stem to 'run' (ING removed, double-consonant cleanup)"  # => 'running' must stem to 'run' (ING removed, double-consonant cleanup)
    assert stems["runs"] == "run", "'runs' must stem to 'run' (the plain S rule)"  # => 'runs' must stem to 'run' (the plain S rule)
    assert stems["running"] == stems["runs"], "'running' and 'runs' must share the stem 'run'"  # => 'running' and 'runs' must share the stem 'run'
    print(f"MATCH: 'running' and 'runs' both stem to {stems['running']!r}")  # => shows MATCH: 'running' and 'runs' both stem to
 
    # 'runner' is an agent noun: Step 4's -ER rule requires measure(stem) > 1 on 'runn',
    # but measure('runn') == 1 -- so the real algorithm leaves 'runner' UNCHANGED. This is
    # not a bug in this implementation; it is a genuine, well-known limit of suffix stripping.
    assert stems["runner"] == "runner", "the real Porter algorithm leaves 'runner' unstemmed (m == 1, not > 1)"  # => the real Porter algorithm leaves 'runner' unstemmed (m == 1, not > 1)
    print(f"NOTE: {stems['runner']!r} does NOT reduce to 'run' -- Step 4's -ER rule needs measure > 1, and")  # => shows NOTE
    print("      measure('runn') == 1, so the rule's own gate blocks it. Suffix stripping is not lemmatization.")  # => shows measure('runn') == 1, so the rule's own gate blocks it. Suffix stripping is not lemmatization.
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

porter_stem('running') = 'run'
porter_stem('runs') = 'run'
porter_stem('runner') = 'runner'
MATCH: 'running' and 'runs' both stem to 'run'
NOTE: 'runner' does NOT reduce to 'run' -- Step 4's -ER rule needs measure > 1, and
      measure('runn') == 1, so the rule's own gate blocks it. Suffix stripping is not lemmatization.

# pyright: strict
"""Example 18: Stem Index Shrink (co-09, co-11)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
def _cv_string(word: str) -> str:  # => classify every letter of word as 'c' (consonant) or 'v' (vowel) per
    """Classify every letter of word as 'c' (consonant) or 'v' (vowel) per
    Porter's definition, where 'y' is a vowel only when preceded by a
    consonant (or is a consonant at word-start)."""
    result: list[str] = []  # => starts empty, populated by the loop below
    for i, ch in enumerate(word):  # => iterates one item at a time
        if ch in "aeiou":  # => true when ch in "aeiou"
            result.append("v")  # => records this item, in order
        elif ch == "y":  # => otherwise, true when ch == "y"
            result.append("c" if i == 0 or result[i - 1] == "v" else "v")  # => records this item, in order
        else:  # => the fallback branch, when no prior condition matched
            result.append("c")  # => records this item, in order
    return "".join(result)  # => returns "".join(result)
 
 
def _measure(stem: str) -> int:  # => porter's m: the count of VC repetitions in [C](VC)^m[V]
    """Porter's m: the count of VC repetitions in [C](VC)^m[V]."""
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    collapsed: list[str] = []  # => starts empty, populated by the loop below
    for ch in cv:  # => collapses runs of the same letter type into one marker
        if not collapsed or collapsed[-1] != ch:  # => true when not collapsed or collapsed[-1] != ch
            collapsed.append(ch)  # => records this item, in order
    pattern = "".join(collapsed)  # => pattern = "".join(collapsed)
    if pattern.startswith("c"):  # => true when pattern.startswith("c")
        pattern = pattern[1:]  # => strips the optional leading consonant run
    if pattern.endswith("v"):  # => true when pattern.endswith("v")
        pattern = pattern[:-1]  # => strips the optional trailing vowel run
    return len(pattern) // 2  # => what remains is (vc)^m -- each pair is one unit of measure
 
 
def _contains_vowel(stem: str) -> bool:  # => defines  contains vowel
    return "v" in _cv_string(stem)  # => the *v* condition Porter's ED/ING rules require
 
 
def _ends_double_consonant(stem: str) -> bool:  # => defines  ends double consonant
    if len(stem) < 2:  # => true when len(stem) < 2
        return False  # => returns False
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    return cv[-1] == "c" and cv[-2] == "c" and stem[-1] == stem[-2]  # => e.g. "hopp"
 
 
def _ends_cvc(stem: str) -> bool:  # => defines  ends cvc
    if len(stem) < 3:  # => true when len(stem) < 3
        return False  # => returns False
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    return cv[-3:] == "cvc" and stem[-1] not in "wxy"  # => Porter's *o condition
 
 
def _step1a(word: str) -> str:  # => defines  step1a
    if word.endswith("sses"):  # => true when word.endswith("sses")
        return word[:-2]  # => caresses -> caress
    if word.endswith("ies"):  # => true when word.endswith("ies")
        return word[:-2]  # => ponies -> poni
    if word.endswith("ss"):  # => true when word.endswith("ss")
        return word  # => caress -> caress (unchanged)
    if word.endswith("s"):  # => true when word.endswith("s")
        return word[:-1]  # => cats -> cat
    return word  # => returns word
 
 
def _step1b_cleanup(stem: str) -> str:  # => defines  step1b cleanup
    if stem.endswith(("at", "bl", "iz")):  # => true when stem.endswith(("at", "bl", "iz"))
        return stem + "e"  # => conflat(ed) -> conflate
    if _ends_double_consonant(stem) and not stem.endswith(("l", "s", "z")):  # => true when _ends_double_consonant(stem) and not stem.endswith((...
        return stem[:-1]  # => hopp(ing) -> hop
    if _measure(stem) == 1 and _ends_cvc(stem):  # => true when _measure(stem) == 1 and _ends_cvc(stem)
        return stem + "e"  # => fil(ing) -> file
    return stem  # => returns stem
 
 
def _step1b(word: str) -> str:  # => defines  step1b
    if word.endswith("eed"):  # => true when word.endswith("eed")
        stem = word[:-3]  # => stem = word[:-3]
        return stem + "ee" if _measure(stem) > 0 else word  # => agreed -> agree
    if word.endswith("ed"):  # => true when word.endswith("ed")
        stem = word[:-2]  # => stem = word[:-2]
        return _step1b_cleanup(stem) if _contains_vowel(stem) else word  # => returns _step1b_cleanup(stem) if _contains_vowel(stem) else word
    if word.endswith("ing"):  # => true when word.endswith("ing")
        stem = word[:-3]  # => stem = word[:-3]
        return _step1b_cleanup(stem) if _contains_vowel(stem) else word  # => returns _step1b_cleanup(stem) if _contains_vowel(stem) else word
    return word  # => returns word
 
 
def _step1c(word: str) -> str:  # => defines  step1c
    if word.endswith("y") and _contains_vowel(word[:-1]):  # => true when word.endswith("y") and _contains_vowel(word[:-1])
        return word[:-1] + "i"  # => happy -> happi
    return word  # => returns word
 
 
_STEP2 = [  # =>  STEP2 = [
    ("ational", "ate"), ("tional", "tion"), ("enci", "ence"), ("anci", "ance"),  # => part of this step's computation, continued from the line above
    ("izer", "ize"), ("abli", "able"), ("alli", "al"), ("entli", "ent"),  # => part of this step's computation, continued from the line above
    ("eli", "e"), ("ousli", "ous"), ("ization", "ize"), ("ation", "ate"),  # => part of this step's computation, continued from the line above
    ("ator", "ate"), ("alism", "al"), ("iveness", "ive"), ("fulness", "ful"),  # => part of this step's computation, continued from the line above
    ("ousness", "ous"), ("aliti", "al"), ("iviti", "ive"), ("biliti", "ble"),  # => part of this step's computation, continued from the line above
]  # => sorted longest-suffix-first below, so "ization" wins over "ation"
 
 
def _step2(word: str) -> str:  # => defines  step2
    for suf, repl in sorted(_STEP2, key=lambda p: len(p[0]), reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem + repl if _measure(stem) > 0 else word  # => relational -> relate
    return word  # => returns word
 
 
_STEP3 = [("icate", "ic"), ("ative", ""), ("alize", "al"), ("iciti", "ic"), ("ical", "ic"), ("ful", ""), ("ness", "")]  # =>  STEP3 = [("icate", "ic"), ("ative", ""), ("alize", "al"...
 
 
def _step3(word: str) -> str:  # => defines  step3
    for suf, repl in sorted(_STEP3, key=lambda p: len(p[0]), reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem + repl if _measure(stem) > 0 else word  # => hopeful -> hope
    return word  # => returns word
 
 
_STEP4 = ["al", "ance", "ence", "er", "ic", "able", "ible", "ant", "ement", "ment", "ent", "ou", "ism", "ate", "iti", "ous", "ive", "ize"]  # =>  STEP4 = ["al", "ance", "ence", "er", "ic", "able", "ibl...
 
 
def _step4(word: str) -> str:  # => defines  step4
    if word.endswith("ion"):  # => true when word.endswith("ion")
        stem = word[:-3]  # => stem = word[:-3]
        if _measure(stem) > 1 and stem.endswith(("s", "t")):  # => true when _measure(stem) > 1 and stem.endswith(("s", "t"))
            return stem  # => adoption -> adopt (only after s/t, and only if m>1)
    for suf in sorted(_STEP4, key=len, reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem if _measure(stem) > 1 else word  # => airliner -> airlin (m>1 required)
    return word  # => returns word
 
 
def _step5a(word: str) -> str:  # => defines  step5a
    if word.endswith("e"):  # => true when word.endswith("e")
        stem = word[:-1]  # => stem = word[:-1]
        m = _measure(stem)  # => m = _measure(stem)
        if m > 1 or (m == 1 and not _ends_cvc(stem)):  # => true when m > 1 or (m == 1 and not _ends_cvc(stem))
            return stem  # => probate -> probat, but cease stays cease (m==1 and *o)
    return word  # => returns word
 
 
def _step5b(word: str) -> str:  # => defines  step5b
    if _measure(word) > 1 and _ends_double_consonant(word) and word.endswith("l"):  # => true when _measure(word) > 1 and _ends_double_consonant(word) ...
        return word[:-1]  # => controll -> control
    return word  # => returns word
 
 
def porter_stem(word: str) -> str:  # => reduce word to its Porter (1980) stem by chaining Steps 1a through 5b
    """Reduce word to its Porter (1980) stem by chaining Steps 1a through 5b."""
    if len(word) <= 2:  # => true when len(word) <= 2
        return word  # => Porter's algorithm is a no-op below 3 letters
    w = word.lower()  # => w = word.lower()
    for step in (_step1a, _step1b, _step1c, _step2, _step3, _step4, _step5a, _step5b):  # => iterates one item at a time
        w = step(w)  # => each step's OUTPUT feeds the next step's INPUT, in this fixed order
    return w  # => returns w
 
 
def build_index(docs: dict[int, list[str]], *, stem: bool) -> dict[str, set[int]]:  # => build a term -> doc-id-set index, optionally applying porter_stem to every token
    """Build a term -> doc-id-set index, optionally applying porter_stem to every token."""
    index: dict[str, set[int]] = {}  # => starts empty, populated by the loop below
    for doc_id, tokens in docs.items():  # => iterates one item at a time
        terms: list[str] = [porter_stem(t) for t in tokens] if stem else list(tokens)  # => co-09: the ONLY difference
        for term in terms:  # => iterates one item at a time
            index.setdefault(term, set()).add(doc_id)  # => part of this step's computation, continued from the line above
    return index  # => returns index
 
 
def main() -> None:  # => defines main
    docs: dict[int, list[str]] = {  # => docs = {
        0: ["running", "shoes", "for", "sale"],  # => doc 0's tokens, this fixture's row
        1: ["he", "runs", "every", "morning"],  # => doc 1's tokens, this fixture's row
        2: ["the", "run", "was", "long"],  # => doc 2's tokens, this fixture's row
    }  # => opens/closes this multi-line literal
    raw_index: dict[str, set[int]] = build_index(docs, stem=False)  # => co-11: no normalization
    stemmed_index: dict[str, set[int]] = build_index(docs, stem=True)  # => co-09: every token stemmed first
    print(f"raw distinct terms:     {len(raw_index)} -> {sorted(raw_index)}")  # => shows raw distinct terms
    print(f"stemmed distinct terms: {len(stemmed_index)} -> {sorted(stemmed_index)}")  # => shows stemmed distinct terms
 
    query_hits: set[int] = stemmed_index.get(porter_stem("run"), set())  # => co-11: query "run" through the SAME stemmer
    print(f"query 'run' (stemmed index) hits: {sorted(query_hits)}")  # => shows query 'run' (stemmed index) hits
 
    assert len(stemmed_index) < len(raw_index), "stemming must shrink the distinct-term count"  # => stemming must shrink the distinct-term count
    assert 0 in query_hits, "querying 'run' must retrieve doc 0 ('running'), which the raw index cannot do"  # => querying 'run' must retrieve doc 0 ('running'), which the raw index cannot do
    print(f"MATCH: distinct terms fell from {len(raw_index)} to {len(stemmed_index)}, and 'run' now retrieves doc 0")  # => shows MATCH: distinct terms fell from
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end

raw distinct terms:     12 -> ['every', 'for', 'he', 'long', 'morning', 'run', 'running', 'runs', 'sale', 'shoes', 'the', 'was']
stemmed distinct terms: 10 -> ['everi', 'for', 'he', 'long', 'morn', 'run', 'sale', 'shoe', 'the', 'wa']
query 'run' (stemmed index) hits: [0, 1, 2]
MATCH: distinct terms fell from 12 to 10, and 'run' now retrieves doc 0

# pyright: strict
"""Example 19: Lemmatize vs Stem (co-10)."""
 
from __future__ import annotations  # => hygiene: postpones annotation evaluation, interpreter-version-agnostic
 
def _cv_string(word: str) -> str:  # => classify every letter of word as 'c' (consonant) or 'v' (vowel) per
    """Classify every letter of word as 'c' (consonant) or 'v' (vowel) per
    Porter's definition, where 'y' is a vowel only when preceded by a
    consonant (or is a consonant at word-start)."""
    result: list[str] = []  # => starts empty, populated by the loop below
    for i, ch in enumerate(word):  # => iterates one item at a time
        if ch in "aeiou":  # => true when ch in "aeiou"
            result.append("v")  # => records this item, in order
        elif ch == "y":  # => otherwise, true when ch == "y"
            result.append("c" if i == 0 or result[i - 1] == "v" else "v")  # => records this item, in order
        else:  # => the fallback branch, when no prior condition matched
            result.append("c")  # => records this item, in order
    return "".join(result)  # => returns "".join(result)
 
 
def _measure(stem: str) -> int:  # => porter's m: the count of VC repetitions in [C](VC)^m[V]
    """Porter's m: the count of VC repetitions in [C](VC)^m[V]."""
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    collapsed: list[str] = []  # => starts empty, populated by the loop below
    for ch in cv:  # => collapses runs of the same letter type into one marker
        if not collapsed or collapsed[-1] != ch:  # => true when not collapsed or collapsed[-1] != ch
            collapsed.append(ch)  # => records this item, in order
    pattern = "".join(collapsed)  # => pattern = "".join(collapsed)
    if pattern.startswith("c"):  # => true when pattern.startswith("c")
        pattern = pattern[1:]  # => strips the optional leading consonant run
    if pattern.endswith("v"):  # => true when pattern.endswith("v")
        pattern = pattern[:-1]  # => strips the optional trailing vowel run
    return len(pattern) // 2  # => what remains is (vc)^m -- each pair is one unit of measure
 
 
def _contains_vowel(stem: str) -> bool:  # => defines  contains vowel
    return "v" in _cv_string(stem)  # => the *v* condition Porter's ED/ING rules require
 
 
def _ends_double_consonant(stem: str) -> bool:  # => defines  ends double consonant
    if len(stem) < 2:  # => true when len(stem) < 2
        return False  # => returns False
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    return cv[-1] == "c" and cv[-2] == "c" and stem[-1] == stem[-2]  # => e.g. "hopp"
 
 
def _ends_cvc(stem: str) -> bool:  # => defines  ends cvc
    if len(stem) < 3:  # => true when len(stem) < 3
        return False  # => returns False
    cv = _cv_string(stem)  # => cv = _cv_string(stem)
    return cv[-3:] == "cvc" and stem[-1] not in "wxy"  # => Porter's *o condition
 
 
def _step1a(word: str) -> str:  # => defines  step1a
    if word.endswith("sses"):  # => true when word.endswith("sses")
        return word[:-2]  # => caresses -> caress
    if word.endswith("ies"):  # => true when word.endswith("ies")
        return word[:-2]  # => ponies -> poni
    if word.endswith("ss"):  # => true when word.endswith("ss")
        return word  # => caress -> caress (unchanged)
    if word.endswith("s"):  # => true when word.endswith("s")
        return word[:-1]  # => cats -> cat
    return word  # => returns word
 
 
def _step1b_cleanup(stem: str) -> str:  # => defines  step1b cleanup
    if stem.endswith(("at", "bl", "iz")):  # => true when stem.endswith(("at", "bl", "iz"))
        return stem + "e"  # => conflat(ed) -> conflate
    if _ends_double_consonant(stem) and not stem.endswith(("l", "s", "z")):  # => true when _ends_double_consonant(stem) and not stem.endswith((...
        return stem[:-1]  # => hopp(ing) -> hop
    if _measure(stem) == 1 and _ends_cvc(stem):  # => true when _measure(stem) == 1 and _ends_cvc(stem)
        return stem + "e"  # => fil(ing) -> file
    return stem  # => returns stem
 
 
def _step1b(word: str) -> str:  # => defines  step1b
    if word.endswith("eed"):  # => true when word.endswith("eed")
        stem = word[:-3]  # => stem = word[:-3]
        return stem + "ee" if _measure(stem) > 0 else word  # => agreed -> agree
    if word.endswith("ed"):  # => true when word.endswith("ed")
        stem = word[:-2]  # => stem = word[:-2]
        return _step1b_cleanup(stem) if _contains_vowel(stem) else word  # => returns _step1b_cleanup(stem) if _contains_vowel(stem) else word
    if word.endswith("ing"):  # => true when word.endswith("ing")
        stem = word[:-3]  # => stem = word[:-3]
        return _step1b_cleanup(stem) if _contains_vowel(stem) else word  # => returns _step1b_cleanup(stem) if _contains_vowel(stem) else word
    return word  # => returns word
 
 
def _step1c(word: str) -> str:  # => defines  step1c
    if word.endswith("y") and _contains_vowel(word[:-1]):  # => true when word.endswith("y") and _contains_vowel(word[:-1])
        return word[:-1] + "i"  # => happy -> happi
    return word  # => returns word
 
 
_STEP2 = [  # =>  STEP2 = [
    ("ational", "ate"), ("tional", "tion"), ("enci", "ence"), ("anci", "ance"),  # => part of this step's computation, continued from the line above
    ("izer", "ize"), ("abli", "able"), ("alli", "al"), ("entli", "ent"),  # => part of this step's computation, continued from the line above
    ("eli", "e"), ("ousli", "ous"), ("ization", "ize"), ("ation", "ate"),  # => part of this step's computation, continued from the line above
    ("ator", "ate"), ("alism", "al"), ("iveness", "ive"), ("fulness", "ful"),  # => part of this step's computation, continued from the line above
    ("ousness", "ous"), ("aliti", "al"), ("iviti", "ive"), ("biliti", "ble"),  # => part of this step's computation, continued from the line above
]  # => sorted longest-suffix-first below, so "ization" wins over "ation"
 
 
def _step2(word: str) -> str:  # => defines  step2
    for suf, repl in sorted(_STEP2, key=lambda p: len(p[0]), reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem + repl if _measure(stem) > 0 else word  # => relational -> relate
    return word  # => returns word
 
 
_STEP3 = [("icate", "ic"), ("ative", ""), ("alize", "al"), ("iciti", "ic"), ("ical", "ic"), ("ful", ""), ("ness", "")]  # =>  STEP3 = [("icate", "ic"), ("ative", ""), ("alize", "al"...
 
 
def _step3(word: str) -> str:  # => defines  step3
    for suf, repl in sorted(_STEP3, key=lambda p: len(p[0]), reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem + repl if _measure(stem) > 0 else word  # => hopeful -> hope
    return word  # => returns word
 
 
_STEP4 = ["al", "ance", "ence", "er", "ic", "able", "ible", "ant", "ement", "ment", "ent", "ou", "ism", "ate", "iti", "ous", "ive", "ize"]  # =>  STEP4 = ["al", "ance", "ence", "er", "ic", "able", "ibl...
 
 
def _step4(word: str) -> str:  # => defines  step4
    if word.endswith("ion"):  # => true when word.endswith("ion")
        stem = word[:-3]  # => stem = word[:-3]
        if _measure(stem) > 1 and stem.endswith(("s", "t")):  # => true when _measure(stem) > 1 and stem.endswith(("s", "t"))
            return stem  # => adoption -> adopt (only after s/t, and only if m>1)
    for suf in sorted(_STEP4, key=len, reverse=True):  # => iterates one item at a time
        if word.endswith(suf):  # => true when word.endswith(suf)
            stem = word[: -len(suf)]  # => stem = word[: -len(suf)]
            return stem if _measure(stem) > 1 else word  # => airliner -> airlin (m>1 required)
    return word  # => returns word
 
 
def _step5a(word: str) -> str:  # => defines  step5a
    if word.endswith("e"):  # => true when word.endswith("e")
        stem = word[:-1]  # => stem = word[:-1]
        m = _measure(stem)  # => m = _measure(stem)
        if m > 1 or (m == 1 and not _ends_cvc(stem)):  # => true when m > 1 or (m == 1 and not _ends_cvc(stem))
            return stem  # => probate -> probat, but cease stays cease (m==1 and *o)
    return word  # => returns word
 
 
def _step5b(word: str) -> str:  # => defines  step5b
    if _measure(word) > 1 and _ends_double_consonant(word) and word.endswith("l"):  # => true when _measure(word) > 1 and _ends_double_consonant(word) ...
        return word[:-1]  # => controll -> control
    return word  # => returns word
 
 
def porter_stem(word: str) -> str:  # => reduce word to its Porter (1980) stem by chaining Steps 1a through 5b
    """Reduce word to its Porter (1980) stem by chaining Steps 1a through 5b."""
    if len(word) <= 2:  # => true when len(word) <= 2
        return word  # => Porter's algorithm is a no-op below 3 letters
    w = word.lower()  # => w = word.lower()
    for step in (_step1a, _step1b, _step1c, _step2, _step3, _step4, _step5a, _step5b):  # => iterates one item at a time
        w = step(w)  # => each step's OUTPUT feeds the next step's INPUT, in this fixed order
    return w  # => returns w
 
LEMMA_DICTIONARY: dict[str, str] = {  # => co-10: a small, HAND-CURATED irregular-form dictionary
    "better": "good",  # => entry for 'better'
    "best": "good",  # => entry for 'best'
    "worse": "bad",  # => entry for 'worse'
    "went": "go",  # => entry for 'went'
    "mice": "mouse",  # => entry for 'mice'
}  # => opens/closes this multi-line literal
 
 
def lemmatize(word: str) -> str:  # => look up word's dictionary lemma; words not in the dictionary pass through unchanged
    """Look up word's dictionary lemma; words not in the dictionary pass through unchanged."""
    return LEMMA_DICTIONARY.get(word, word)  # => co-10: dictionary-based, not rule-based
 
 
def main() -> None:  # => defines main
    word: str = "better"  # => a classic irregular comparative -- no suffix connects it to "good"
    lemma: str = lemmatize(word)  # => co-10: the dictionary knows the irregular mapping
    stem: str = porter_stem(word)  # => co-09: pure suffix stripping has no suffix to strip here
    print(f"word:     {word!r}")  # => shows word
    print(f"lemma:    {lemma!r}  (dictionary lookup)")  # => shows lemma
    print(f"stem:     {stem!r}  (Porter suffix stripping)")  # => shows stem
 
    assert lemma == "good", "lemmatize('better') must return the dictionary's irregular mapping 'good'"  # => lemmatize('better') must return the dictionary's irregular mapping 'good'
    assert stem == "better", "porter_stem('better') has no suffix rule to apply and leaves the word unchanged"  # => porter_stem('better') has no suffix rule to apply and leaves the word unchanged
    assert lemma != stem, "the lemma and the stem must DIFFER -- this is the whole point of the contrast"  # => the lemma and the stem must DIFFER -- this is the whole point of the contrast
    print(f"MATCH: lemma ({lemma!r}) differs from stem ({stem!r}) -- only a dictionary can catch an irregular form")  # => shows MATCH: lemma (
 
 
if __name__ == "__main__":  # => entry point -- runs only when this file executes directly, not on import
    main()  # => runs the example end to end