NLP: List the n-grams

Slide a window over text to produce its word or character n-grams.

What to build

A program that prints every word n-gram or character n-gram of a line.

Requirements

  • Line 1 is word n or char n. For word, the units are the words of line 2 (split on whitespace) and an n-gram is printed with its words separated by single spaces.
  • For char, spaces in line 2 are first replaced with _, the units are the single characters, and an n-gram is printed with no separator.
  • Print each n-gram on its own line, in order, then count: K. If there are fewer than n units, print only count: 0.

Input

Line 1: the mode and n. Line 2: the text.

Output

K lines, then the count.

Constraints

1 ≤ n ≤ 10; the text has at most 1,000 characters.

Example

Input:

word 2
the cat sat on the mat

Output:

the cat
cat sat
sat on
on the
the mat
count: 5

Why it works

A text of m units has m − n + 1 windows of length n, and each window is one n-gram; replacing spaces makes word boundaries visible inside character n-grams.

Examples

Example 1 · Input
word 2
the cat sat on the mat
Expected output
the cat
cat sat
sat on
on the
the mat
count: 5
Example 2 · Input
char 3
a cat
Expected output
a_c
_ca
cat
count: 3

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

Hints

Hint 1

An n-gram starts at every position i from 0 to len(units) − n: `units[i:i + n]`.

Hint 2

For characters, use `list(text.replace(" ", "_"))` as the units and join an n-gram with no separator.

Solution

Show one correct solution (try it yourself first)
mode, n = input().split()
n = int(n)
text = input()
units = text.split() if mode == "word" else list(text.replace(" ", "_"))
grams = [units[i:i + n] for i in range(len(units) - n + 1)]
sep = " " if mode == "word" else ""
for g in grams:
    print(sep.join(g))
print("count:", len(grams))

Lesson: Bag of words and n-grams →