def ctcBeamSearch(mat, classes, lm, k, beamWidth):
    """
    beam search as described by the paper of Hwang et al. and the paper of Graves et al.
    """

    blankIdx = len(classes)
    maxT, maxC = mat.shape

    # initialise beam state
    last = BeamState()
    labeling = ()
    last.entries[labeling] = BeamEntry()
    last.entries[labeling].prBlank = 1
    last.entries[labeling].prTotal = 1

    # go over all time-steps
    for t in range(maxT):
        curr = BeamState()

        # get beam-labelings of best beams
        bestLabelings = last.sort()[0:beamWidth]

	    # go over best beams
        for labeling in bestLabelings:

	        # probability of paths ending with a non-blank
            prNonBlank = 0
	        # in case of non-empty beam
            if labeling:
		       # probability of paths with repeated last char at the end
                try: 
                    prNonBlank = last.entries[labeling].prNonBlank * mat[t, labeling[-1]]
                except FloatingPointError:
                    prNonBlank = 0

	    # probability of paths ending with a blank
            prBlank = (last.entries[labeling].prTotal) * mat[t, blankIdx]

	    # add beam at current time-step if needed
            addBeam(curr, labeling)

            # fill in data
            curr.entries[labeling].labeling = labeling
            curr.entries[labeling].prNonBlank += prNonBlank
            curr.entries[labeling].prBlank += prBlank
            curr.entries[labeling].prTotal += prBlank + prNonBlank
            curr.entries[labeling].prText = last.entries[labeling].prText # beam-labeling not changed, therefore also LM score unchanged from
            curr.entries[labeling].lmApplied = True # LM already applied at previous time-step for this beam-labeling

            # extend current beam-labeling
            for c in range(maxC - 1):
                # add new char to current beam-labeling
                newLabeling = labeling + (c,)

                # if new labeling contains duplicate char at the end, only consider paths ending with a blank
                if labeling and labeling[-1] == c:
                    prNonBlank = mat[t, c] * last.entries[labeling].prBlank
                else:
                    prNonBlank = mat[t, c] * last.entries[labeling].prTotal

		        # add beam at current time-step if needed
                addBeam(curr, newLabeling)
				
		        # fill in data
                curr.entries[newLabeling].labeling = newLabeling
                curr.entries[newLabeling].prNonBlank += prNonBlank
                curr.entries[newLabeling].prTotal += prNonBlank
				
		        # apply LM
                applyLM(curr.entries[labeling], curr.entries[newLabeling], classes, lm)

        # set new beam state
        last = curr

    # normalise LM scores according to beam-labeling-length
    last.norm()

    # sort by probability
    bestLabelings = last.sort()[:k] # get most probable labeling

    output = []
    for bestLabeling in bestLabelings:
        # map labels to chars
        res = ''
        for l in bestLabeling:
            res += classes[l]
        output.append(res)
    return output
def ctcBeamSearch ( mat , classes , lm , k , beamWidth ) : blankIdx = len ( classes ) maxT , maxC = mat . shape last = BeamState ( ) labeling = ( ) last . entries [ labeling ] = BeamEntry ( ) last . entries [ labeling ] . prBlank = 1 last . entries [ labeling ] . prTotal = 1 for t in range ( maxT ) : curr = BeamState ( ) bestLabelings = last . sort ( ) [ 0 : beamWidth ] for labeling in bestLabelings : prNonBlank = 0 if labeling : try : prNonBlank = last . entries [ labeling ] . prNonBlank * mat [ t , labeling [ - 1 ] ] except FloatingPointError : prNonBlank = 0 prBlank = ( last . entries [ labeling ] . prTotal ) * mat [ t , blankIdx ] addBeam ( curr , labeling ) curr . entries [ labeling ] . labeling = labeling curr . entries [ labeling ] . prNonBlank += prNonBlank curr . entries [ labeling ] . prBlank += prBlank curr . entries [ labeling ] . prTotal += prBlank + prNonBlank curr . entries [ labeling ] . prText = last . entries [ labeling ] . prText curr . entries [ labeling ] . lmApplied = True for c in range ( maxC - 1 ) : newLabeling = labeling + ( c , ) if labeling and labeling [ - 1 ] == c : prNonBlank = mat [ t , c ] * last . entries [ labeling ] . prBlank else : prNonBlank = mat [ t , c ] * last . entries [ labeling ] . prTotal addBeam ( curr , newLabeling ) curr . entries [ newLabeling ] . labeling = newLabeling curr . entries [ newLabeling ] . prNonBlank += prNonBlank curr . entries [ newLabeling ] . prTotal += prNonBlank applyLM ( curr . entries [ labeling ] , curr . entries [ newLabeling ] , classes , lm ) last = curr last . norm ( ) bestLabelings = last . sort ( ) [ : k ] output = [ ] for bestLabeling in bestLabelings : res = '' for l in bestLabeling : res += classes [ l ] output . append ( res ) return output
beam search as described by the paper of Hwang et al. and the paper of Graves et al.