NLP: Chunk noun phrases

Group tagged words into noun phrases with a tag pattern, as NLTK's RegexpParser does.

What to build

A program that brackets the noun phrases of a tagged sentence.

Requirements

  • The input is word/TAG items (tag after the last /). A noun phrase is an optional DET, then any number of ADJ, then one or more NOUN or PROPN. Phrases are found from left to right and never overlap; each is as long as possible.
  • Print the sentence's words with every noun phrase in square brackets, for example [the old dog] chased [a ball], then noun phrases: N.

Input

One line of tagged words.

Output

Two lines.

Constraints

At most 500 words.

Example

Input:

the/DET old/ADJ dog/NOUN chased/VERB a/DET big/ADJ red/ADJ ball/NOUN

Output:

[the old dog] chased [a big red ball]
noun phrases: 2

Why it works

Writing each tag as one letter turns the phrase pattern into a regular expression over a string, and the regex engine's leftmost, longest matching gives exactly the non-overlapping chunks.

Examples

Example 1 · Input
the/DET old/ADJ dog/NOUN chased/VERB a/DET big/ADJ red/ADJ ball/NOUN
Expected output
[the old dog] chased [a big red ball]
noun phrases: 2
Example 2 · Input
Ada/PROPN Lovelace/PROPN wrote/VERB notes/NOUN
Expected output
[Ada Lovelace] wrote [notes]
noun phrases: 2

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

Hints

Hint 1

Map DET to D, ADJ to A, NOUN and PROPN to N and every other tag to x, then search the code string with `re.finditer(r"D?A*N+", code)`.

Hint 2

Each match's `start()` and `end()` are word positions, because there is one letter per word.

Solution

Show one correct solution (try it yourself first)
import re

items = [item.rsplit("/", 1) for item in input().split()]
letters = {"DET": "D", "ADJ": "A", "NOUN": "N", "PROPN": "N"}
code = "".join(letters.get(t, "x") for _, t in items)
out, last, count = [], 0, 0
for m in re.finditer(r"D?A*N+", code):
    out += [w for w, _ in items[last:m.start()]]
    out.append("[" + " ".join(w for w, _ in items[m.start():m.end()]) + "]")
    last = m.end()
    count += 1
out += [w for w, _ in items[last:]]
print(" ".join(out))
print("noun phrases:", count)

Lesson: Named entities and chunking →