Extract the keywords of every document with the smoothed TF-IDF that scikit-learn uses.
What to build
A program that prints the top k keywords of each document by TF-IDF.
Requirements
- Lowercase the documents, split them on whitespace and remove the stopwords.
- tf = count ÷ the document's length after stopword removal; idf = ln((1 + N) ÷ (1 + df)) + 1, where df counts the documents (after stopword removal) containing the word.
- For each document print
doc I: w1 (s1), w2 (s2), ...with its k highest-scoring distinct words, scores with three decimal places, highest first and ties in alphabetical order (fewer if the document has fewer distinct words).
Input
Line 1: N and k. Line 2: stopwords. Then N documents.
Output
N lines.
Constraints
N ≤ 50; every document keeps at least one word.
Example
Input:
3 2
the a
the cat sat on the mat
the dog sat on a log
the cat chased the dog
Output:
doc 1: mat (0.423), cat (0.322)
doc 2: log (0.423), dog (0.322)
doc 3: chased (0.564), cat (0.429)
Why it works
After stopwords are gone, the words with the highest tf × idf are the ones a document uses a lot and other documents rarely use, which is what makes them describe that document; smoothing keeps every idf positive and defined.
Examples
3 2 the a the cat sat on the mat the dog sat on a log the cat chased the dog
doc 1: mat (0.423), cat (0.322) doc 2: log (0.423), dog (0.322) doc 3: chased (0.564), cat (0.429)
2 1 is rain is wet rain sun is hot
doc 1: rain (0.937) doc 2: hot (0.703)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Remove stopwords first; the document length used in tf is the length after removal.
Hint 2
Smoothed idf is `math.log((1 + n) / (1 + df)) + 1`; rank with `key=lambda kv: (-kv[1], kv[0])`.
Solution
Show one correct solution (try it yourself first)
import math
n, k = map(int, input().split())
stop = set(input().split())
docs = [[w for w in input().lower().split() if w not in stop] for _ in range(n)]
df = {}
for doc in docs:
for w in set(doc):
df[w] = df.get(w, 0) + 1
for i, doc in enumerate(docs, 1):
scores = {}
for w in doc:
idf = math.log((1 + n) / (1 + df[w])) + 1
scores[w] = doc.count(w) / len(doc) * idf
best = sorted(scores.items(), key=lambda kv: (-kv[1], kv[0]))[:k]
print(f"doc {i}: " + ", ".join(f"{w} ({s:.3f})" for w, s in best))