BM25 Ranking

The problem

BM25 is the classic way to rank documents for a query by the words they contain. It needs no training, it is fast, and it is hard to beat when the query contains exact names, codes or rare words. You will implement it as a class that indexes a collection of documents and scores queries against it.

The formula

where:

• $t$ runs over the terms of the query (a term that appears twice in the query counts twice);
• $f_{t,d}$ is the number of times $t$ occurs in document $d$;
• $L_d = |d| / \mathrm{avgdl}$ is the document's length relative to the average length;
• $k_1$ and $b$ are constants (defaults $1.2$ and $0.75$);
• $\mathrm{idf}(t) = \ln\!\left(1 + \frac{N - n_t + 0.5}{n_t + 0.5}\right)$ is Lucene's inverse document frequency, with $N$ documents of which $n_t$ contain $t$: the rarer the term, the larger.

Two effects: saturation (more occurrences help less and less, controlled by $k_1$) and length normalization (the same count means less in a long document, controlled by $b$).

Example. Documents: $d_0$ = ["the", "cat", "sat"], $d_1$ = ["the", "dog", "barked", "at", "the", "cat", "all", "day"], $d_2$ = ["a", "bird", "sang"]. $N = 3$, lengths $3, 8, 3$, average $4.67$.

• Query ["cat"]: $n = 2$, $\mathrm{idf} = \ln(1 + 1.5/2.5) = 0.47$. For $d_0$: $L = 0.64$, $s = 2.2 / (1 + 1.2(0.25 + 0.75 \cdot 0.64)) = 1.17$, score $0.55$. For $d_1$: $L = 1.71$, $s = 0.77$, score $0.36$. For $d_2$: 0. Ranking: $d_0, d_1, d_2$.
• Query ["dog"]: $n = 1$, $\mathrm{idf} = \ln(1 + 2.5/1.5) = 0.98$; only $d_1$: $0.98 \cdot 0.77 = 0.76$.
• Query ["cat", "dog"]: the sum of the two: $0.55$, $1.12$, $0$.
• A term in no document, such as "fish", adds 0.

What to implement

class BM25 with:

• __init__(self, docs, k1=1.2, b=0.75): docs is a list of documents, each a list of tokens (strings). Precompute what the scores need: the count of every term in every document, the document lengths, the average length, and the document frequency of every term (in how many documents it appears).
• score(self, query): query is a list of tokens. Return a NumPy array with one score per document.
• rank(self, query, k): the indices of the k best documents, best first, ties by lower index.

Requirements

• $f_{t,d}$ is the number of times $t$ occurs in document $d$ (collections.Counter per document).
• Use the natural logarithm (math.log).