AI020. 语音识别 CER

解题思路

明确转换方向

本题把识别序列变成参考序列，允许插入、删除或替换一个 token，每次操作的代价都是 1。先求最少编辑次数 d，再按参考序列长度 n 计算 CER。这里的计算单位是输入中的 token，而不是 token 内的单个字符。

状态与三种转移

令 dp[i][j] 表示把识别序列前 j 个 token 变成参考序列前 i 个 token 的最少编辑次数。行对应参考序列，列对应识别序列。

• 如果 ref[i-1] 与 hyp[j-1] 相同，两者直接匹配，dp[i][j] = dp[i-1][j-1]。
• 否则，比较以下三种操作的代价，取最小值：
• 替换：dp[i-1][j-1] + 1。把识别序列最后一个 token 替换成参考序列最后一个 token。
• 插入：dp[i-1][j] + 1。先把前 j 个识别 token 变成前 i-1 个参考 token，再插入 ref[i-1]。
• 删除：dp[i][j-1] + 1。删除 hyp[j-1]，其余前 j-1 个识别 token 转换成前 i 个参考 token。

因此，上方格子对应插入，左方格子对应删除；操作名称由这里的转换方向决定，不要只按表格位置记忆。

初始化也按相同含义处理：dp[i][0] = i，因为空识别序列需要插入 i 个 token；dp[0][j] = j，因为要删除识别序列的全部 j 个 token。最终距离是 dp[n][m]。

用小例子检查方向

参考序列为 a b，识别序列为 a。第二个参考 token b 没有对应项，需要插入一次，距离为 1。交换两序列后，则需要删除一次，距离仍为 1，但操作方向不同。仅比较最终距离相同，不能据此判断插入和删除的解释是否正确。

滚动数组与复杂度

计算当前行 cur 时，只读取上一行的 prev[j-1]、prev[j] 和当前行左侧的 cur[j-1]。保留这两行即可，不必存储整个二维表。每轮先设置 cur[0] = i，再从左到右计算，最后交换两行。

时间复杂度为 O(n·m)，滚动数组的额外空间为 O(m)。n、m 均不超过 2000，最多计算 400 万个状态；总内存还包括输入序列。实际运行时间取决于实现与判题环境。

CER 与四舍五入

参考序列非空时，CER = d/n。题目要求保留四位小数，并采用通常的四舍五入规则。对非负整数 d 和正整数 n，可以先计算万分之一单位：

q = (20000*d + n) // (2*n)

再把 q//10000 作为整数部分，把 q%10000 补足四位作为小数部分。例如 d=1、n=32，CER=0.03125，应输出 0.0313。Python 的 round 使用中点取偶规则，不能直接用它替代本题的四舍五入；这个例子本身可以精确表示为二进制数，差异不只是浮点表示误差。

参考序列为空时，题目另有约定：CER 的数值等于编辑距离 d，不执行除法。例如 n=0、m=2 时，输出距离 2 和 CER 2.0000。

读入与输出

长度为 0 的序列对应空行。可以把完整输入按空白切成 token 流：先读 n、m，再依次取 n 个参考 token 和 m 个识别 token。按行读取同样可行，但必须保留空序列的位置，不能把后面的行误当成前一个序列。

输出两行：第一行是编辑距离；第二行是四位小数的 CER。参考实现先算距离，再进行整数四舍五入与字符串补零。

自测

1. 参考 a b、识别 a b：距离 0，CER 0.0000。 2. 参考 a b、识别 a：距离 1，CER 0.5000；检查插入方向。 3. 参考 a、识别 a b：距离 1，CER 1.0000；检查删除方向。 4. 参考有 3 个 token、识别为空：距离 3，CER 1.0000。 5. 参考为空、识别有 2 个 token：距离 2，CER 2.0000。 6. 两序列均为空：距离 0，CER 0.0000。 7. 参考长 32，识别只替换其中一个 token：距离 1，CER 0.0313。

这些例子分别检查匹配、编辑方向、空序列与舍入。再加入重复 token 和混合编辑的输入，核对三种转移是否都被考虑。