Build BM25 From Scratch

Implement bm25_scores(query, docs, k1=1.5, b=0.75) returning one score per document, and bm25_top(query, docs, k=3) returning the top-k documents, best first.

The formula, for each query term t and document d:

$$\text{score}(d) = \sum_{t} \text{idf}(t) \cdot \frac{f(t,d),(k_1 + 1)}{f(t,d) + k_1\left(1 - b + b,\frac{|d|}{\text{avgdl}}\right)}$$

$$\text{idf}(t) = \ln!\left(\frac{N - n(t) + 0.5}{n(t) + 0.5} + 1\right)$$

where f(t,d) is how often t appears in d, |d| is the document's length in tokens, avgdl is the mean document length, N is the number of documents and n(t) is how many contain t.

The tests check three properties that fall out of it:

1. A term in every document is nearly worthless: idf goes to almost zero.
2. Repeated occurrences help, but with diminishing returns: k1 caps it.
3. Longer documents are penalised by b.

Tokenise by lowercasing and splitting on non-alphanumeric characters; tokenize in the starter code does this.