代码解析
import numpy as np
from six.moves import xrange


import numpy as np
import editDistance as ed
import heapq as hq
from six.moves import xrange


def ctc_loss(params, seq, blank=0, is_prob=True):
    """
    params: [vocab_size, T], logits.softmax(-1). T 是输入序列的长度，vocab_size是词表大小。
    seq: [seq_len] 输出序列的长度。

    CTC loss function.
    params - n x m matrix of n-D probability distributions over m frames.
    seq - sequence of phone id's for given example.
    is_prob - whether params have already passed through a softmax
    Returns objective and gradient.
    """
    seqLen = seq.shape[0]  # Length of label sequence (# phones)
    numphones = params.shape[0]  # Number of labels
    L = 2 * seqLen + 1  # Length of label sequence with blanks, 拓展后的 l'.
    T = params.shape[1]  # Length of utterance (time)

    # 建立表格 l' x T.
    alphas = np.zeros((L, T))  # 前向概率
    betas = np.zeros((L, T))  # 后向概率

    # 这里dp的map：
    # 横轴为 2*seq_len+1, 也就是 ground truth label中每个token前后插入 blank
    # 纵轴是 T frames

    # logits 转换为概率
    if not is_prob:
        # if not probs, params is logits without softmax.
        params = params - np.max(params, axis=0)
        params = np.exp(params)
        params = params / np.sum(params, axis=0)

    # Initialize alphas and forward pass

    # 初始条件：T=0时，只能为 blank 或 seq[0]
    alphas[0, 0] = params[blank, 0]
    alphas[1, 0] = params[seq[0], 0]
    # T=0， alpha[:, 0] 其他的全部为 0


    c = np.sum(alphas[:, 0])
    alphas[:, 0] = alphas[:, 0] / c  # 这里 T=0 时刻所有可能节点的概率要归一化

    llForward = np.log(c)  # 转换为log域

    for t in xrange(1, T):
        # 第一个循环： 计算每个时刻所有可能节点的概率和
        start = max(0, L - 2 * (T - t))  # 对于时刻 t, 其可能的节点.与公式2一致。
        end = min(2 * t + 2, L)  # 对于时刻 t，最大节点范围不可能超过 2t+2
        for s in xrange(start, L):
            l = (s - 1) / 2
            # blank，节点s在偶数位置，意味着s为blank
            if s % 2 == 0:
                if s == 0: # 初始位置，单独讨论
                    alphas[s, t] = alphas[s, t - 1] * params[blank, t]
                else:
                    alphas[s, t] = (alphas[s, t - 1] + alphas[s - 1, t - 1]) * params[blank, t]
            # s为奇数，非空
            # l = (s-1/2) 就是 s 所对应的 lable 中的字符。
            # ((s-2)-1)/2 = (s-1)/2-1 = l-1 就是 s-2 对应的lable中的字符
            elif s == 1 or seq[l] == seq[l - 1]:
                alphas[s, t] = (alphas[s, t - 1] + alphas[s - 1, t - 1]) * params[seq[l], t]
            else:
                alphas[s, t] = (alphas[s, t - 1] + alphas[s - 1, t - 1] + alphas[s - 2, t - 1]) \
                               * params[seq[l], t]

        # normalize at current time (prevent underflow)
        c = np.sum(alphas[start:end, t])
        alphas[start:end, t] = alphas[start:end, t] / c
        llForward += np.log(c)
      return llForward
ctc_beam_search 解码
def ctc_beam_search_decode(probs, beam_size=5, blank=0):
    """
    :param probs: The output probabilities (e.g. post-softmax) for each
    time step. Should be an array of shape (time x output dim).
    :param beam:
    :param blank:
    :return:
    """
    # T表示时间，S表示词表大小
    T, S = probs.shape

    # 求概率的对数
    probs = np.log(probs)

    # Elements in the beam are (prefix, (p_blank, p_no_blank))
    # Initialize the beam with the empty sequence, a probability of
    # 1 for ending in blank and zero for ending in non-blank
    # (in log space).
    # 每次总是保留beam_size条路径
    beam = [(tuple(), ((0.0, NEG_INF), tuple()))]

    for t in range(T):  # Loop over time
        # A default dictionary to store the next step candidates.
        next_beam = make_new_beam()

        for s in range(S):  # Loop over vocab
            # print(s)
            p = probs[t, s]  # t时刻，符号为s的概率

            # The variables p_b and p_nb are respectively the
            # probabilities for the prefix given that it ends in a
            # blank and does not end in a blank at this time step.
            for prefix, ((p_b, p_nb), prefix_p) in beam:  # Loop over beam
                # p_b表示前缀最后一个是blank的概率，p_nb是前缀最后一个非blank的概率
                # If we propose a blank the prefix doesn't change.
                # Only the probability of ending in blank gets updated.

                if s == blank:
                    # 增加的字母是blank
                    # 先取出对应prefix的两个概率，然后更后缀为blank的概率n_p_b
                    (n_p_b, n_p_nb), _ = next_beam[prefix]  # -inf, -inf
                    n_p_b = logsumexp(n_p_b, p_b + p, p_nb + p)  # 更新后缀为blank的概率
                    next_beam[prefix] = ((n_p_b, n_p_nb), prefix_p)  # s=blank， prefix不更新，因为blank要去掉的。
                    # print(next_beam[prefix])
                    continue

                # Extend the prefix by the new character s and add it to
                # the beam. Only the probability of not ending in blank
                # gets updated.
                end_t = prefix[-1] if prefix else None
                n_prefix = prefix + (s,)  # 更新 prefix, 它是一个tuple
                n_prefix_p = prefix_p + (p,)
                # 先取出对应 n_prefix 的两个概率, 这个是更新了blank概率之后的 new 概率
                (n_p_b, n_p_nb), _ = next_beam[n_prefix]  # -inf, -inf

                if s != end_t:
                    # 如果s不和上一个不重复，则更新非空格的概率
                    n_p_nb = logsumexp(n_p_nb, p_b + p, p_nb + p)
                else:
                    # 如果s和上一个重复，也要更新非空格的概率
                    # We don't include the previous probability of not ending
                    # in blank (p_nb) if s is repeated at the end. The CTC
                    # algorithm merges characters not separated by a blank.
                    n_p_nb = logsumexp(n_p_nb, p_b + p)

                # If s is repeated at the end we also update the unchanged
                # prefix. This is the merging case.
                if s == end_t:
                    (n_p_b, n_p_nb), n_prefix_p = next_beam[prefix]
                    n_p_nb = logsumexp(n_p_nb, p_nb + p)
                    # 如果是s=end_t，则prefix不更新
                    next_beam[prefix] = ((n_p_b, n_p_nb), n_prefix_p)
                else:
                    # *NB* this would be a good place to include an LM score.
                    next_beam[n_prefix] = ((n_p_b, n_p_nb), n_prefix_p)
        # print(t, next_beam.keys())
        # Sort and trim the beam before moving on to the
        # next time-step.
        # 根据概率进行排序，每次保留概率最高的beam_size条路径
        beam = sorted(next_beam.items(),
                      key=lambda x: logsumexp(*x[1][0]),
                      reverse=True)
        beam = beam[:beam_size]

    # best = beam[0]
    # return best[0], -logsumexp(*best[1][0]), best[1][1]

    pred_lens = [len(beam[i][0]) for i in range(beam_size)]
    max_len = max(pred_lens)
    pred_seq, scores, pred_pobs = np.zeros((beam_size, max_len), dtype=np.int32), \
                                  [], np.zeros((beam_size, max_len))
    for bs in range(beam_size):
        pred_seq[bs][:pred_lens[bs]] = beam[bs][0]
        scores.append(-logsumexp(*beam[bs][1][0]))
        pred_pobs[bs][:pred_lens[bs]] = np.exp(beam[bs][1][1])
    return pred_seq, scores, pred_pobs


# 因为代码中为了避免数据下溢，都采用的是对数概率，所以看起来比较繁琐
def logsumexp(*args):
    """
    Stable log sum exp.
    """
    if all(a == NEG_INF for a in args):
        return NEG_INF
    a_max = max(args)
    lsp = math.log(sum(math.exp(a - a_max) for a in args))  # 概率相加再取log，为避免数值下溢
    return a_max + lsp


# 创建一个新的beam
def make_new_beam():
    fn = lambda: ((NEG_INF, NEG_INF), tuple())
    return collections.defaultdict(fn)

if __name__ == "__main__":
    import ctcdecode, time

    np.random.seed(3)

    seq_len = 50
    output_dim = 20

    probs = np.random.rand(seq_len, output_dim)
    # probs = np.random.rand(time, output_dim)
    # probs = np.random.rand(time, output_dim)
    probs = probs / np.sum(probs, axis=1, keepdims=True)

    start_time = time.time()
    labels, score, labels_p = MPGenerate.ctc_beam_search_decode(probs, beam_size=5, blank=0)
    print("labels:", labels[0], len(labels[0]))
    print("labels_p: ", labels_p[0], len(labels_p[0]))
    print("Score {:.3f}".format(score[0]))
    print("First method time: ", time.time() - start_time)

    dec_logits = torch.FloatTensor(probs).unsqueeze(0)
    len_video = torch.LongTensor([seq_len])
    decoder_vocab = [chr(x) for x in range(20000, 20000 + output_dim)]

    second_time = time.time()
    decoder = ctcdecode.CTCBeamDecoder(decoder_vocab, beam_width=5, blank_id=0, num_processes=10)

    pred_seq, scores, _, out_seq_len = decoder.decode(dec_logits, len_video)

    # pred_seq: [batch, beam, length]
    # out_seq_len: [batch, beam]
    print(pred_seq[0, 0, :][:out_seq_len[0, 0]])
    print(out_seq_len[0, 0])
    print("Score {:.3f}".format(scores[0, 0]))
    print("Second method time: ", time.time() - second_time)