NLP: Document frequency

Count how many documents contain each word, the input to IDF.

What to build

A program that prints the document frequency of every word in a collection.

Requirements

  • Lowercase the documents and split them on whitespace.
  • A word's document frequency is the number of documents that contain it at least once.
  • Print word df for every word, highest frequency first, ties in alphabetical order.

Input

Line 1: n. Then n documents, one per line.

Output

One line per distinct word.

Constraints

n ≤ 100; each document has at most 500 words.

Example

Input:

3
the cat sat
the dog sat
a cat

Output:

cat 2
sat 2
the 2
a 1
dog 1

Why it works

Counting a set of words per document ignores repeats inside a document, so the number measures how widespread a word is in the collection rather than how often it is used.

Examples

Example 1 · Input
3
the cat sat
the dog sat
a cat
Expected output
cat 2
sat 2
the 2
a 1
dog 1
Example 2 · Input
2
spam spam spam
ham spam
Expected output
spam 2
ham 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Turn each document into a set of lowercase words so a word counts at most once per document.

Hint 2

Sort the items with `key=lambda kv: (-kv[1], kv[0])`.

Solution

Show one correct solution (try it yourself first)
n = int(input())
df = {}
for _ in range(n):
    for w in set(input().lower().split()):
        df[w] = df.get(w, 0) + 1
for w, c in sorted(df.items(), key=lambda kv: (-kv[1], kv[0])):
    print(w, c)

Lesson: TF-IDF: weighting words →