Problems

1 / 1

Implement BM25 Ranking Score

NLPLinear AlgebraData Processing

Hard

Compute one BM25 relevance score per tokenized document. Repeated query terms are counted once.

\operatorname{idf}(t) = \log\left(\frac{N-\operatorname{df}(t)+0.5}{\operatorname{df}(t)+0.5}+1\right)

\operatorname{score}(D,Q) = \sum_{t \in Q} \operatorname{idf}(t)\frac{\operatorname{tf}(t,D)(k_1+1)}{\operatorname{tf}(t,D)+k_1\left(1-b+b\frac{|D|}{\operatorname{avgdl}}\right)}

Here, $N$ is the document count, $\operatorname{df}(t)$ counts documents containing term $t$ , $\operatorname{tf}(t,D)$ counts the term in document $D$ , $|D|$ is document length, and $\operatorname{avgdl}$ is average document length. Return a NumPy array whose entries follow the original document order.

Loading visualization...

Examples

Input: query_tokens = ["machine", "learning"], docs = [["introduction", "to", "machine", "learning"], ["deep", "learning", "basics"], ["cooking", "pasta", "guide"]], k1 = 1.2, b = 0.75

Output: [1.341106, 0.490052, 0.0]

Explanation: The first document matches both query terms, the second matches one, and the third matches neither.

Input: query_tokens = ["data"], docs = [["data", "data", "mining"], ["applied", "data", "science", "science", "science"], ["sports", "news"]], k1 = 1.2, b = 0.75

Output: [0.664957, 0.390192, 0.0]

Hint 1

Use one Counter per document for term frequencies.

Hint 2

Use Counter.update(set(document)) to count document frequencies.

Hint 3

Build a NumPy vector of one term's frequency across all documents before applying the formula.

Requirements

Use the stated BM25 IDF and scoring formulas
Count repeated query terms once
Preserve document order
Return a NumPy array of floating-point scores

Constraints

docs is a list of token lists
$k_1 > 0$ and $0 \le b \le 1$
Use NumPy and the Python standard library only

Try Similar Problems

Tfidf Vectorizer Bag Of Words Cosine Similarity Jaccard Similarity Edit Distance

Prev Next