Rank documents for a query the way a classic search engine does.
What to build
A program that ranks documents by the cosine similarity of their TF-IDF vectors to each query.
Requirements
- Lowercase and split documents and queries on whitespace. For any text, a word's weight is (number of times it occurs in the text) × idf, with idf = ln(N ÷ df) over the documents. Query words that occur in no document are ignored.
- Score each document by the cosine similarity of its weights and the query's weights (0 if either has length 0).
- For each query, print the at most k documents with a score above 0 as
D:S(document number from 1, score with four decimal places), separated by spaces, highest score first and equal scores in document order; printno resultsif there are none.
Input
Line 1: N and k. Then N documents. Then q and q queries.
Output
q lines.
Constraints
N ≤ 200; q ≤ 50.
Example
Input:
4 2
cheap flights paris
paris hotels cheap
python books
python guide
2
cheap paris hotels
python
Output:
2:1.0000 1:0.3333
3:0.4472 4:0.4472
Why it works
Cosine ignores document length, and IDF gives words found in every document a weight of 0 and rare words large weights, so documents that share the query's informative words rise to the top.
Examples
4 2 cheap flights paris paris hotels cheap python books python guide 2 cheap paris hotels python
2:1.0000 1:0.3333 3:0.4472 4:0.4472
2 3 the cat the dog 2 the cat dog
no results 1:0.7071 2:0.7071
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A text's weights are a dictionary `{word: count × idf}` over its words that occur in the collection; idf = `math.log(N / df)`.
Hint 2
Cosine = dot ÷ (length × length); if either length is 0, the similarity is 0. Sort by `(-round(score, 9), number)`.
Solution
Show one correct solution (try it yourself first)
import math
n, k = map(int, input().split())
docs = [input().lower().split() for _ in range(n)]
df = {}
for doc in docs:
for w in set(doc):
df[w] = df.get(w, 0) + 1
idf = {w: math.log(n / c) for w, c in df.items()}
def weights(words):
return {w: words.count(w) * idf[w] for w in words if w in idf}
def cosine(a, b):
dot = sum(a[w] * b[w] for w in a if w in b)
na = math.sqrt(sum(v * v for v in a.values()))
nb = math.sqrt(sum(v * v for v in b.values()))
return dot / (na * nb) if na and nb else 0.0
vectors = [weights(doc) for doc in docs]
for _ in range(int(input())):
q = weights(input().lower().split())
scores = [(cosine(q, v), i + 1) for i, v in enumerate(vectors)]
ranked = sorted([s for s in scores if s[0] > 0], key=lambda s: (-round(s[0], 9), s[1]))[:k]
print(" ".join(f"{i}:{s:.4f}" for s, i in ranked) if ranked else "no results")