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))