NLP: A most-frequent-tag baseline

Build the baseline every part-of-speech tagger is compared with.

What to build

A program that tags words with the tag they had most often in training.

Requirements

  • Training items are word/TAG; the tag is after the last / (a word may contain / itself). Compare words in lowercase.
  • A known word gets its most frequent training tag; an unknown word gets the most frequent tag of the whole training data. Ties go to the alphabetically first tag.
  • For each test sentence print the words as written, each followed by / and its tag, separated by spaces.

Input

Line 1: n. Then n tagged sentences. Then m and m untagged sentences.

Output

m lines.

Constraints

n ≤ 1,000; m ≤ 100.

Example

Input:

3
the/DET dog/NOUN barks/VERB
the/DET can/NOUN rusts/VERB
I/PRON can/AUX swim/VERB
2
the dog can swim
a cat barks

Output:

the/DET dog/NOUN can/AUX swim/VERB
a/VERB cat/VERB barks/VERB

Why it works

Most words have one dominant tag, so choosing it is right most of the time, and the most common tag overall is the best single guess for a word never seen before.

Examples

Example 1 · Input
3
the/DET dog/NOUN barks/VERB
the/DET can/NOUN rusts/VERB
I/PRON can/AUX swim/VERB
2
the dog can swim
a cat barks
Expected output
the/DET dog/NOUN can/AUX swim/VERB
a/VERB cat/VERB barks/VERB
Example 2 · Input
2
Fish/NOUN swim/VERB
they/PRON fish/VERB fish/NOUN
1
fish they
Expected output
fish/NOUN they/PRON

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

Hints

Hint 1

The tag comes after the last slash: `word, tag = item.rsplit("/", 1)`.

Hint 2

`min(counts, key=lambda t: (-counts[t], t))` returns the most frequent tag, alphabetically first on a tie.

Solution

Show one correct solution (try it yourself first)
n = int(input())
word_tags, tag_counts = {}, {}
for _ in range(n):
    for item in input().split():
        word, tag = item.rsplit("/", 1)
        counts = word_tags.setdefault(word.lower(), {})
        counts[tag] = counts.get(tag, 0) + 1
        tag_counts[tag] = tag_counts.get(tag, 0) + 1


def most_common(counts):
    return min(counts, key=lambda t: (-counts[t], t))


default = most_common(tag_counts)
for _ in range(int(input())):
    out = []
    for w in input().split():
        known = word_tags.get(w.lower())
        out.append(f"{w}/{most_common(known) if known else default}")
    print(" ".join(out))

Lesson: Part-of-speech tagging with an HMM →