Greedy decoding commits to one word at a time. Beam search keeps several candidates and can find a more probable sentence.
What to build
A program that runs beam search over a table of next-word probabilities.
Requirements
- Start with one beam: the start word, probability 1.
- Repeat L times: extend each beam by each successor of its last word (multiplying the probabilities), drop beams with no successors, and keep the B best by probability (ties: alphabetical order of the whole text).
- Print the final beams, best first, as
TEXT Pwith P to 4 decimal places; if none survive, printno sequence.
Input
Line 1: m. Then m lines prev next probability. Then a line start B L.
Output
Up to B lines.
Constraints
1 ≤ m ≤ 1000; 1 ≤ B ≤ 10; 1 ≤ L ≤ 10.
Example
Input:
9
the cat 0.5
the dog 0.4
the end 0.1
cat sat 0.3
cat ran 0.3
cat ate 0.4
dog sat 0.9
dog ran 0.1
end . 1.0
the 2 2
Output:
the dog sat 0.3600
the cat ate 0.2000
Why it works
Keeping B candidates lets a sequence that starts with a less likely word survive long enough to show that it leads to a more probable whole, which greedy decoding can never discover.
Examples
9 the cat 0.5 the dog 0.4 the end 0.1 cat sat 0.3 cat ran 0.3 cat ate 0.4 dog sat 0.9 dog ran 0.1 end . 1.0 the 2 2
the dog sat 0.3600 the cat ate 0.2000
2 a b 1.0 b c 1.0 a 1 2
a b c 1.0000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A beam is a list of words and its probability; extend every beam with every successor of its last word.
Hint 2
A beam whose last word has no successors is dropped.
Hint 3
Sort candidates by probability (highest first), then by their text, and keep the first B.
Solution
Show one correct solution (try it yourself first)
m = int(input())
following = {}
for _ in range(m):
a, nxt, p = input().split()
following.setdefault(a, []).append((nxt, float(p)))
start, b, l = input().split()
beams = [([start], 1.0)]
for _ in range(int(l)):
candidates = []
for words, prob in beams:
for nxt, p in following.get(words[-1], []):
candidates.append((words + [nxt], prob * p))
candidates.sort(key=lambda c: (-c[1], " ".join(c[0])))
beams = candidates[: int(b)]
if not beams:
print("no sequence")
for words, prob in beams:
print(f"{' '.join(words)} {prob:.4f}")
Lesson: Decoding: temperature, top-k, top-p and beam search →