BM25

Task

Implement bm25_scores(documents: list[list[str]], query_tokens: list[str], k1: float, b: float) -> list[float]. Compute one BM25 relevance score per tokenized document, in corpus order.

Requirements

• documents is a list of already-tokenized documents, and query_tokens is already tokenized; compare tokens exactly and case-sensitively without splitting, lowercasing, stemming, or other normalization.
• k1 is finite and non-negative, and b is finite and lies in the closed interval [0, 1].
• Let N be the number of documents, document length be its token count, and average document length be the total number of corpus tokens divided by N.
• For each distinct query token t, let tf(t, d) be its occurrence count in document d and df(t) be the number of documents containing it at least once.
• Use IDF(t) = log(1 + (N - df(t) + 0.5) / (df(t) + 0.5)), where log is the natural logarithm.
• Add IDF(t) * tf(t,d) * (k1 + 1) / (tf(t,d) + k1 * (1 - b + b * len(d) / avgdl)) for every distinct query token present in d.
• Repeated query tokens have no additional effect: score each distinct query token exactly once.
• Return scores in the same order as documents, including 0.0 for documents with no matching query token.
• Return an empty list for an empty corpus. For an empty query, return one 0.0 per document.
• A corpus whose documents are all empty has average length zero; return zero scores without dividing by zero.
• Do not mutate documents or query_tokens.

Example

bm25_scores(
    [["the", "cat", "sat", "cat"], ["the", "dog", "sat"], ["dog"]],
    ["cat", "sat"],
    1.2,
    0.75,
)
# [1.5725612026838964, 0.44713858782297006, 0.0]