A bigram model's prediction is a probability for every possible next word. Compute them for one word.
What to build
A program that prints the next-word probabilities of a bigram model for a given word.
Requirements
- Print
NEXT Pfor each word that follows the given word, with P to 3 decimal places. - Order: highest probability first; equal probabilities alphabetically.
- If the word is never followed by anything, print
no successors.
Input
Line 1: the training text. Line 2: the word.
Output
One line per possible next word.
Constraints
1 to 10,000 words.
Example
Input:
the cat sat on the mat . the cat ate the fish . the dog sat on the log .
the
Output:
cat 0.333
dog 0.167
fish 0.167
log 0.167
mat 0.167
Why it works
Counts of the pairs that start with the word, divided by their total, form a probability distribution over what comes next.
Examples
Example 1 · Input
the cat sat on the mat . the cat ate the fish . the dog sat on the log . the
Expected output
cat 0.333 dog 0.167 fish 0.167 log 0.167 mat 0.167
Example 2 · Input
the cat sat on the mat . the cat ate the fish . the dog sat on the log . sat
Expected output
on 1.000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Collect every word that directly follows the given word, and count them.
Hint 2
Divide each count by the number of times the given word was followed by anything.
Hint 3
Sort by probability from highest to lowest, then alphabetically.
Solution
Show one correct solution (try it yourself first)
words = input().split()
word = input().strip()
counts = {}
for a, b in zip(words, words[1:]):
if a == word:
counts[b] = counts.get(b, 0) + 1
total = sum(counts.values())
if not counts:
print("no successors")
for nxt in sorted(counts, key=lambda w: (-counts[w], w)):
print(nxt, f"{counts[nxt] / total:.3f}")