Generate text with a bigram model

Generate text the way a Markov model does: start from a word and keep sampling the next one.

What to build

A program that learns a bigram model and generates text by sampling, using given random numbers.

Requirements

  • The text starts with the start word, which counts towards the length.
  • To add a word: list the current word's successors alphabetically with their probabilities, take the next draw r, and choose the first successor whose running total is greater than r.
  • Stop after adding ., when the current word has no successors, or when the text has n words. Print the text.

Input

Line 1: the training text. Line 2: the start word and n. Line 3: the draws (there are always enough).

Output

One line.

Constraints

1 to 10,000 training words; 1 ≤ n ≤ 100.

Example

Input:

the cat sat on the mat . the cat ate the fish . the dog sat on the log .
the 8
0.1 0.9 0.3 0.5 0.6 0.2 0.95

Output:

the cat sat on the fish .

Why it works

Each step samples from the bigram distribution of the current word, so the text follows pairs seen in training while the random draws decide between alternatives.

Examples

Example 1 · Input
the cat sat on the mat . the cat ate the fish . the dog sat on the log .
the 8
0.1 0.9 0.3 0.5 0.6 0.2 0.95
Expected output
the cat sat on the fish .
Example 2 · Input
a b
a 5
0.5 0.5
Expected output
a b

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

Hints

Hint 1

Learn the next-word counts first; for each word, list its successors in alphabetical order.

Hint 2

For each new word, take the next draw r and choose the first successor whose running total of probabilities is greater than r.

Hint 3

Stop at `.`, at a word with no successors, or when the text has n words.

Solution

Show one correct solution (try it yourself first)
words = input().split()
start, n = input().split()
n = int(n)
draws = list(map(float, input().split()))
following = {}
for a, b in zip(words, words[1:]):
    following.setdefault(a, {})
    following[a][b] = following[a].get(b, 0) + 1
text = [start]
used = 0
while len(text) < n and text[-1] != "." and text[-1] in following:
    options = following[text[-1]]
    total = sum(options.values())
    r = draws[used]
    used += 1
    running = 0.0
    pick = sorted(options)[-1]
    for w in sorted(options):
        running += options[w] / total
        if r < running:
            pick = w
            break
    text.append(pick)
print(" ".join(text))

Lesson: Generating text with a Markov model →