NLP: Keywords by TF-IDF

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

Example 1 · Input
3 2
the a
the cat sat on the mat
the dog sat on a log
the cat chased the dog
Expected 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)
Example 2 · Input
2 1
is
rain is wet rain
sun is hot
Expected output
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))

Lesson: TF-IDF: weighting words →