最简单的decode方式当然是最近拿每个frame的最大概率的token，但实际应用中这种方法字错率会颇高，且无法和语言模型结合。

        要与语言模型结合，必须有多个candidate，但也不能够穷尽每个frame每个token的组合，故有beam search。但beam search的candidate会有很多相同的部分，相同的部分应把他们置信度加起来，否则会可能因为单一路径置信度偏小而错误排优，所以有了Prefix beam search。

         CTC 的 prefix beam search 算法维护的不是beam 个路径前缀，而是 beam 个标签前缀（存在不同的路径映射到相同前缀），但仍需要考虑其背后的路径（路径到标签的多对一关系）。每个时间步，对 beam 个前缀进行扩展，用字符表中的字符对已有前缀做扩展，得到新的多个前缀，然后计算这些前缀的概率，从中挑选出概率最大的 beam 个保存，不断重复这个过程直到最后一个时间步，然后选出概率最大的一个结果作为最终的标签。

ctc_probs = ctc_probs.squeeze(0)# cur_hyps: (prefix, (blank_ending_score, none_blank_ending_score))# cur_hyps (prefix ,(pb, pnb))用于当前已经存在的前缀 prefix， 初始化为 空#                             pb 对应前缀 prefix 以 blank 结尾的概率， 初始化为 1 （空前缀等价 blank）#                             pnb 对应前缀 prefix 以 非 blank 结尾的概率, 初始化为 0 （空前缀 没有 非 blank）cur_hyps = [(tuple(), (0.0, -float('inf')))]# 2. CTC beam search step by stepfor t in range(0, maxlen):# t 时刻 扩展序列可以分为三种情况：#  A（t, l): t 时刻生成 l 序列#  Ab(t, l): t 时刻生成 l 序列且以 blank 结尾#  Anb(t, l): t 时刻生成 l 序列且以 非 blank 结尾logp = ctc_probs[t]  # (vocab_size,)# key: prefix, value (pb, pnb), default value(-inf, -inf)# next_hpys 保存 t 时刻，扩展的路径next_hyps = defaultdict(lambda: (-float('inf'), -float('inf')))# 2.1 First beam prune: select topk best# 当前 t 时刻的 beam 个 top 输出top_k_logp, top_k_index = logp.topk(beam_size)  # (beam_size,)for s in top_k_index:s = s.item()ps = logp[s].item()for prefix, (pb, pnb) in cur_hyps:last = prefix[-1] if len(prefix) > 0 else Noneif s == 0:  # blank# 扩展符号为 blank, 则当前前缀扩展后还是一样，有两种情况# 情况1,前缀为结尾非 blank : 如 aa (a) + _ 后 变成 a_ (a), 而pnb(a) 没改变# 情况2,前缀为结尾 blank : 如 a_ (a) + _ 后 还是为 a_ (a), 所以 概率更新 n_pb += (pb * ps) + (pnb * ps)# 注： n_pb += 用累加是 n_pb 是时刻保存一样路径的概率和， 同理 n_pnb += 。n_pb, n_pnb = next_hyps[prefix]n_pb = log_add([n_pb, pb + ps, pnb + ps])next_hyps[prefix] = (n_pb, n_pnb)elif s == last:# 扩展符号非 blank 且与前缀最后字符相同，有两种情况# 情况1,前缀结尾是非 blank : 如 *a + a 后 变成 ×a , 从而更新pnb(*a)  n_pnb += pnb * ps# 情况2,前缀结尾是 blank : 如 ×a_ + a 后 变城 ×aa, 是另一个路径， 则新改路径 n_pnb(*aa) += pb(*a_) * ps#  Update *ss -> *s;n_pb, n_pnb = next_hyps[prefix]n_pnb = log_add([n_pnb, pnb + ps])next_hyps[prefix] = (n_pb, n_pnb)# Update *s-s -> *ss, - is for blankn_prefix = prefix + (s, )n_pb, n_pnb = next_hyps[n_prefix]n_pnb = log_add([n_pnb, pb + ps])next_hyps[n_prefix] = (n_pb, n_pnb)else:# 扩展符号非 blank 且与前缀最后字符不同，则只有一种情况，就是扩展为另一个路径，此时更新这个路径概率# 如 ×a + c 后变后 ×ac , *a_ + c 后也变为 ×ac , 所以 n_pnb（×ac） += pb(*a_) * ps + pnb(*a_) * psn_prefix = prefix + (s, )n_pb, n_pnb = next_hyps[n_prefix]n_pnb = log_add([n_pnb, pb + ps, pnb + ps])next_hyps[n_prefix] = (n_pb, n_pnb)# 所有 t 时刻重新更新保存 beam 个最优 前缀。# 2.2 Second beam prunenext_hyps = sorted(next_hyps.items(),key=lambda x: log_add(list(x[1])),reverse=True)cur_hyps = next_hyps[:beam_size]