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; thendistinct: 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
2 3 of the a 3 New York is big. I love New York! The state of New York.
3 new york 1 i love 1 is big distinct: 8
1 2 the a 2 The cat and the dog. A cat!
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))