AI028. 束搜索解码

解码器逐步生成长度为 T 的 token 序列,词表大小为 V(token 编号 0 到 V-1)。第 1 步选择 token j 得分 s[j];第 t 步(t >= 2)在上一步选择的 token 为 i 时选择 token j,得分 M_t[i][j]。序列总分为各步得分之和。束搜索按固定规则执行:开始时束中只有空序列(分数 0);每一步把束中每个序列分别扩展 V 个 token 得到候选序列,再按「总分从大到小,总分相同时序列字典序从小到大」排序,只保留前 B 个进入下一步;T 步结束后,束中排在最前面的序列即为答案。注意:答案由上述束搜索过程定义,当 B 较小时它可能不等于全局最优序列。请输出答案序列的总分与序列本身。字典序比较按 token 编号逐位比较。