Next-word probabilities

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 P for 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}")

Lesson: Generating text with a Markov model →