All problems
CTC Prefix Beam Search (Lite)
Problem
Run a lite CTC prefix beam search. Each beam tracks a prefix and two probabilities: ending in blank and ending in a non-blank token.
Every frame extends each beam with every token, handling repeated tokens through the blank split. Keep the top beam_width prefixes by total probability, with ties broken by the prefix tuple, and return the best prefix as a list of indices.
Hint
Probabilities of all paths that collapse to the same prefix are summed.
Test cases
case 1
in: [[[0.1,0.7,0.2]],0,2]
expected: [1]
case 2
in: [[[0.1,0.6,0.3],[0.1,0.4,0.5]],0,2]
expected: [1]
case 3
in: [[[0.7,0.2,0.1],[0.6,0.3,0.1]],0,2]
expected: []
case 4
in: [[[0.1,0.5,0.4],[0.1,0.5,0.4]],0,2]
expected: [1]
Starter codePython
def ctc_prefix_beam_lite(frames, blank_index, beam_width):
# Your code here
pass4 test cases · run your code against them in the editor