NLP: Bag-of-words count vectors

Vectorize documents the way scikit-learn's CountVectorizer does, with a minimum document frequency.

What to build

A program that builds a vocabulary and a count vector for each document.

Requirements

  • Lowercase the documents and split them on whitespace.
  • A word is in the vocabulary only if it appears in at least min_df documents; the vocabulary is sorted alphabetically.
  • Print vocabulary: followed by the words, then one line per document with its counts separated by spaces.

Input

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

Output

n + 1 lines.

Constraints

n ≤ 100; at least one word reaches min_df.

Example

Input:

3 1
the cat sat
the cat sat on the mat
the dog ate the cat

Output:

vocabulary: ate cat dog mat on sat the
0 1 0 0 0 1 1
0 1 0 1 1 1 2
1 1 1 0 0 0 2

Why it works

A fixed, sorted vocabulary gives every document a vector with the same positions, and the document-frequency limit drops words too rare to be useful.

Examples

Example 1 · Input
3 1
the cat sat
the cat sat on the mat
the dog ate the cat
Expected output
vocabulary: ate cat dog mat on sat the
0 1 0 0 0 1 1
0 1 0 1 1 1 2
1 1 1 0 0 0 2
Example 2 · Input
3 2
The cat sat
the cat sat on the mat
the dog ate the cat
Expected output
vocabulary: cat sat the
1 1 1
1 1 2
1 0 2

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

Hints

Hint 1

First count, for every word, the number of documents it appears in (use a set per document so a word counts once per document).

Hint 2

The vocabulary is `sorted(w for w in df if df[w] >= min_df)`; a document's vector is `[doc.count(w) for w in vocab]`.

Solution

Show one correct solution (try it yourself first)
n, min_df = 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
vocab = sorted(w for w in df if df[w] >= min_df)
print("vocabulary:", " ".join(vocab))
for doc in docs:
    print(" ".join(str(doc.count(w)) for w in vocab))

Lesson: Bag of words and n-grams →