Full-text search engines don't scan every document for every query -- they build an INVERTED INDEX once: for every term, the list of documents that contain it, along with how many times. Query time becomes "look up a handful of terms and walk their (already tiny) posting lists" instead of scanning the whole corpus.

Having found candidate documents, they still need to be RANKED -- more term matches, rarer terms, and (relative to document length) more concentrated term frequency should all push a document up the ranking. BM25 (Okapi BM25) is the ranking function essentially every modern search engine still uses for this.

Implement:

• build_index(documents) -> (index, doc_lengths): documents is a list of raw text strings; tokenize each with the given tokenize (lowercase + whitespace split). index maps each term to a dict of {doc_id: term_frequency} (only for documents that actually contain the term). doc_lengths maps doc_id to that document's token count.

• idf(term, index, n_docs) -> the term's inverse-document-frequency weight, using the exact formula log(1 + (n_docs - doc_freq + 0.5) / (doc_freq + 0.5)), where doc_freq is the number of documents containing term (0 if the term never appears at all).

• bm25_score(query_terms, doc_id, index, doc_lengths, avgdl, k1=1.2, b=0.75) -> BM25's score for one document against a list of query terms:

  score = sum over query terms of idf(term) * (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * doc_len / avgdl))

  where tf is the term's frequency in doc_id (0 if absent -- such a term contributes nothing, not an error), and doc_len/avgdl are that document's length and the corpus's average document length.

• search(documents, query, k1=1.2, b=0.75) -> build the index, tokenize query, score every document, and return [(doc_id, score), ...] sorted by score descending, ties broken by doc_id ascending.

Example

docs = [
    "the quick brown fox jumps over the lazy dog",
    "the lazy dog sleeps all day",
    "quick foxes are quick and clever quick quick",
]
search(docs, "quick fox")
# doc 0 (has both "quick" and "fox") ranks above doc 2 (only "quick",
# but many more repeats -- diminishing returns from k1 saturation caps
# how much that alone can win), which ranks above doc 1 (neither term).

Constraints

• k1 controls term-frequency saturation (diminishing returns for a heavily repeated term); b controls how strongly document length is penalized (b=0 disables length normalization entirely, b=1 fully normalizes against the corpus average).
• A query term that never appears anywhere in the corpus must contribute a score of 0 to every document, not raise a KeyError -- idf is still well-defined for a term with doc_freq=0, and tf for such a term is 0 in every document.

Real-world grounding

• Apache Lucene's BM25Similarity: lucene/core/src/java/org/apache/lucene/search/similarities/BM25Similarity.java -- look at idf() (same formula as above) and BM25Scorer.doScore (the saturating term-frequency / length-normalization formula), with k1 = 1.2 and b = 0.75 as its own defaults.

Elasticsearch's relevance scoring is Lucene's BM25Similarity running underneath it -- Elasticsearch's own repository does NOT reimplement BM25 itself; it embeds Lucene as its search core. (Elasticsearch does have a file named LegacyBM25Similarity.java, but it's a deprecated wrapper that delegates straight to Lucene's BM25Similarity for backwards- compatible scoring, not an independent implementation.) This exercise is grounded in the real thing: Lucene's BM25Similarity.

Real search engines go further: BM25F extends this to multiple weighted fields per document, proximity/phrase scoring layers on top of the plain term-match score, and posting lists get compressed (delta + variable-byte encoding over sorted doc ids) rather than stored as plain dicts -- but "IDF times a saturating, length-normalized term-frequency term, summed across query terms" is exactly the core of BM25 as shipped.