Implement BM25 Ranking Score
Implement BM25 Ranking Score
Implement the BM25 ranking score to rank a list of documents for a tokenized query. Return a score per document (higher = more relevant).
IDF Formula:
idf(t)=log(df(t)+0.5N−df(t)+0.5+1)BM25 Score:
score(D,Q)=t∈Q∑idf(t)⋅tf(t,D)+k1(1−b+b⋅avgdl∣D∣)tf(t,D)⋅(k1+1)Where: N = #docs, df(t) = #docs containing t, |D| = doc length, avgdl = average doc length
Function Arguments
query_tokens: list[str]- List of query terms to search fordocs: list[list[str]]- List of documents, each document is a list of tokensk1: float = 1.2- Term frequency saturation parameterb: float = 0.75- Length normalization parameter
Examples
Input: query=["machine","learning"], docs=[["introduction","to","machine","learning"], ["deep","learning","basics"], ["cooking","pasta","guide"]]
Output: [1.34111, 0.49005, 0.00000]
scores[0] ≥ scores[1] ≫ scores[2] (doc 0 has both terms, doc 1 has one term, doc 2 has none)
Input: query=["data"], docs=[["data","science"], ["big","data","analytics"], ["cooking","recipes"]]
Output: [0.49918, 0.42082, 0.00000]
Hint 1
Use Counter to count term frequencies in each document and document frequencies across the corpus. Use set() to get unique terms per document.
Hint 2
Use np.array() for document lengths and np.mean() for average length. Use dict.fromkeys() to deduplicate query terms while preserving order.
Hint 3
Use math.log() for IDF calculation and np.zeros() to initialize the score array. Use .get() method on Counter objects for safe term frequency lookups.
Requirements
- Use the formula above with the provided parameters
- Return
np.ndarrayof shape(len(docs),)(dtype float) - If a query term never appears in the corpus, its
idfcan be 0 - Handle empty corpus by returning an empty array
Constraints
- Corpus size ≤ 10,000 docs; each doc length ≤ 2,000 tokens
- Vectorized where reasonable; avoid heavy nested loops
- Libraries: NumPy + standard library only
Try Similar Problems
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
Accepts: number
Implement BM25 Ranking Score
Implement BM25 Ranking Score
Implement the BM25 ranking score to rank a list of documents for a tokenized query. Return a score per document (higher = more relevant).
IDF Formula:
idf(t)=log(df(t)+0.5N−df(t)+0.5+1)BM25 Score:
score(D,Q)=t∈Q∑idf(t)⋅tf(t,D)+k1(1−b+b⋅avgdl∣D∣)tf(t,D)⋅(k1+1)Where: N = #docs, df(t) = #docs containing t, |D| = doc length, avgdl = average doc length
Function Arguments
query_tokens: list[str]- List of query terms to search fordocs: list[list[str]]- List of documents, each document is a list of tokensk1: float = 1.2- Term frequency saturation parameterb: float = 0.75- Length normalization parameter
Examples
Input: query=["machine","learning"], docs=[["introduction","to","machine","learning"], ["deep","learning","basics"], ["cooking","pasta","guide"]]
Output: [1.34111, 0.49005, 0.00000]
scores[0] ≥ scores[1] ≫ scores[2] (doc 0 has both terms, doc 1 has one term, doc 2 has none)
Input: query=["data"], docs=[["data","science"], ["big","data","analytics"], ["cooking","recipes"]]
Output: [0.49918, 0.42082, 0.00000]
Hint 1
Use Counter to count term frequencies in each document and document frequencies across the corpus. Use set() to get unique terms per document.
Hint 2
Use np.array() for document lengths and np.mean() for average length. Use dict.fromkeys() to deduplicate query terms while preserving order.
Hint 3
Use math.log() for IDF calculation and np.zeros() to initialize the score array. Use .get() method on Counter objects for safe term frequency lookups.
Requirements
- Use the formula above with the provided parameters
- Return
np.ndarrayof shape(len(docs),)(dtype float) - If a query term never appears in the corpus, its
idfcan be 0 - Handle empty corpus by returning an empty array
Constraints
- Corpus size ≤ 10,000 docs; each doc length ≤ 2,000 tokens
- Vectorized where reasonable; avoid heavy nested loops
- Libraries: NumPy + standard library only
Try Similar Problems
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
Accepts: number