NLP: Most frequent words

Find the words that dominate a text, the first look at any new corpus.

What to build

A program that counts word frequencies over several lines and prints the most common words.

Requirements

  • Split each line on whitespace, lowercase each piece and strip the characters . , ! ? ; : " ( ) from both ends; ignore pieces that become empty.
  • Print tokens T, vocabulary V: the number of kept tokens and of distinct words.
  • Then print the k most frequent words as word count, highest count first, ties in alphabetical order (fewer lines if there are fewer than k distinct words).

Input

Line 1: n and k. Then n lines of text.

Output

One summary line, then at most k lines.

Constraints

n ≤ 100; each line has at most 1,000 characters.

Example

Input:

2 3
The cat sat. The cat ran!
A dog ran, too.

Output:

tokens 10, vocabulary 7
cat 2
ran 2
the 2

Why it works

A dictionary of counts is the simplest model of a text; sorting by count shows Zipf's law at once, and a fixed tie-break keeps the answer the same every time.

Examples

Example 1 · Input
2 3
The cat sat. The cat ran!
A dog ran, too.
Expected output
tokens 10, vocabulary 7
cat 2
ran 2
the 2
Example 2 · Input
1 2
"Yes!" she said. Yes, yes.
Expected output
tokens 5, vocabulary 3
yes 3
said 1

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

Hints

Hint 1

Lowercase each word, then `word.strip('.,!?;:"()')` removes punctuation from both ends. Skip a word that becomes empty.

Hint 2

Sort with `key=lambda kv: (-kv[1], kv[0])` to put high counts first and break ties alphabetically.

Solution

Show one correct solution (try it yourself first)
n, k = map(int, input().split())
counts = {}
total = 0
for _ in range(n):
    for raw in input().lower().split():
        word = raw.strip('.,!?;:"()')
        if word:
            counts[word] = counts.get(word, 0) + 1
            total += 1
print(f"tokens {total}, vocabulary {len(counts)}")
for word, c in sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))[:k]:
    print(word, c)

Lesson: What natural language processing is →