NLP: The most common n-grams

Mine the frequent phrases of a corpus, a quick way to find names and key terms.

What to build

A program that counts n-grams across sentences and prints the most frequent ones.

Requirements

  • Each input line is one sentence; n-grams never cross from one line to the next. Lowercase each word and strip . , ! ? from its ends; drop words that become empty.
  • Skip any n-gram made only of stopwords.
  • Print the k most frequent n-grams as count n-gram, highest count first, ties in alphabetical order of the n-gram text; then distinct: D, the number of different n-grams counted.

Input

Line 1: n and k. Line 2: stopwords. Line 3: m. Then m sentences.

Output

At most k lines, then the distinct count.

Constraints

n ≤ 5; m ≤ 200.

Example

Input:

2 3
of the a
3
New York is big.
I love New York!
The state of New York.

Output:

3 new york
1 i love
1 is big
distinct: 8

Why it works

Repeated n-grams that are not just function words are usually real phrases such as names and technical terms, and keeping n-grams inside sentences avoids counting word pairs that were never next to each other.

Examples

Example 1 · Input
2 3
of the a
3
New York is big.
I love New York!
The state of New York.
Expected output
3 new york
1 i love
1 is big
distinct: 8
Example 2 · Input
1 2
the a
2
The cat and the dog.
A cat!
Expected output
2 cat
1 and
distinct: 3

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

Hints

Hint 1

Clean each word with `w.strip(".,!?").lower()` and drop empty ones, then take n-grams within each line only.

Hint 2

Skip an n-gram when `all(w in stop for w in gram)`; join the words with spaces to use it as a dictionary key.

Solution

Show one correct solution (try it yourself first)
n, k = map(int, input().split())
stop = set(input().split())
counts = {}
for _ in range(int(input())):
    words = [w.strip(".,!?").lower() for w in input().split()]
    words = [w for w in words if w]
    for i in range(len(words) - n + 1):
        gram = words[i:i + n]
        if all(w in stop for w in gram):
            continue
        key = " ".join(gram)
        counts[key] = counts.get(key, 0) + 1
for gram, c in sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))[:k]:
    print(c, gram)
print("distinct:", len(counts))

Lesson: Bag of words and n-grams →