动态规划（五）算法设计与分析 国科大

序列对齐

序列对齐问题是一个经常用到的问题。大部分的拼写工具都会进行拼写校验来纠正拼写错误，例如图中工具将错误单词（呈现为 “O-CURRANCE”）与正确单词 “OCCURRENCE” 进行对齐，其中竖线 “|” 代表对应位置的字符完全匹配。该对齐结果表明，错误单词 “OCURRANCE” 与正确单词 “OCCURRENCE” 高度相似 —— 错误单词是通过插入、删除、字符突变等操作，从正确单词生成的，即拼写工具据此识别错误并提供纠正建议。

错误类型

1. 对齐的核心用途序列对齐是用来描述 “错误单词从正确单词生成” 的过程，这个过程会用到 4 种操作：插入（Insertion）、删除（Deletion）、匹配（Match）、突变（Mutation）。

2. 对齐的实现方式：统一序列长度为了用上述操作描述生成过程，需要让 “错误序列（记为 S）” 和 “正确序列（记为 T）” 长度一致 —— 通过在合适位置添加空格 “-”，将 S 改写为 S'、T 改写为 T'，使得 |S'| = |T'|（长度相同）。

   • 示例：S' 是 “O-CURR-ANCE”，T' 是 “OCCURRE-NCE”（空格 “-” 让两者长度统一，中间竖线代表对齐关系）。

3. 空格 “-” 的含义（生成过程的解释）对齐后，通过 S' 和 T' 中 “空格的位置”，可以解释 S 从 T 生成的过程：

   • 若 \(S'[i] = '-'\)：代表 T 的第 i 位被删除了；
   • 若 \(T'[i] = '-'\)：代表 S' 的第 i 位是插入的字母；
   • 其他情况：S' 的第 i 位是 T 第 i 位的复制（可能带有突变）。

得分计算

某个正确序列可能会有多个不同的错误序列，因此我们需要一种计算方法来衡量不同错误序列的偏差程度。

1. 得分的计算方式每个生成过程的可能性，用线性函数计算总得分：总得分 (s(T', S')是 “每个对齐位置 i 的得分 s(T'[i], S'[i]) 的总和（从 i=1 到 S' 的长度），公式为：

2. 单位置的得分规则（简单设定）对 s(a,b)（a 是 T' 的位，b 是 S' 的位）的得分规则做了简化定义：

   • 匹配（Match）：a 和 b 相同，得 + 1（比如 s('C','C')=1）；
   • 突变（Mutation）：a 和 b 不同，得 - 1（比如 s('E','A')=-1）；
   • 插入 / 删除（Insertion/Deletion）：其中一个是空格 “-”，得 - 3（比如 s('C','-')=-3）。

我们可以看到，该计分方式下，对缺少或者添加字母的惩罚是远高于写错的。下面看几个例子：

候选词 1：OCCURRENCE

• 对齐处理：将错误词处理为 S'（O-CURRANCE）、正确词处理为 T'（OCCURRENCE），通过空格统一长度并对齐；
• 得分计算：依据 “匹配 + 1、突变 - 1、插入 / 删除 - 3” 的规则，计算对齐得分：s(T',S') = 1 - 3 + 1+1+1+1 - 1 + 1+1+1 = 4

候选词 2：OCCUPATION

• 对齐处理：将错误词处理为 S'（OC-URRA---NCE）、正确词处理为 T'（OCCU-PATION--），通过空格统一长度并对齐；
• 得分计算：同样按规则，对齐得分：s(T',S') = 1+1 - 3 + 1 - 3 - 1 + 1 - 3 - 3 - 3 + 1 - 3 - 3 = -14

从上面的例子我们也可以发现一个情况，不同的对齐方式也会对序列的得分有所影响，由此，通过序列对齐，可判断 “OCCURRENCE” 转化为错误拼写 “OCURRANCE” 的最可能操作组合（插入 / 删除 / 突变）。下面再看几个例子：

• 对齐 1：

  • 对齐形式：错误词处理为 S'（O-CURRANCE），正确词处理为 T'（OCCURRENCE）；
  • 得分计算：s(T',S') = 1 - 3 + 1+1+1+1 - 1 + 1+1+1 = 4。

• 对齐 2：

  • 对齐形式：错误词处理为 S'（O-CURR-ANCE），正确词处理为 T'（OCCURRE-NCE）；
  • 得分计算：s(T',S') = 1 - 3 + 1+1+1+1 - 3 - 3 + 1+1+1 = -1。

由于对齐 1 的得分（4）远高于对齐 2（-1），因此对齐 1 对应的操作是 “OCCURRENCE” 生成 “OCURRANCE” 的真实过程。由此我们可以判断出该拼写的错误类型，即“删除”。

问题概述

INPUT：

给定两个序列 T 和 S，其中 T 的长度为 m（记为 |T|=m），S 的长度为 n（记为 |S|=n）。

OUTPUT：

找到 T 与 S 的一个对齐方式，使得预先定义的得分函数取值最大化。

序列的元素采用下标索引：（即，T_1 为 T 的第 1 个元素，T_m 为最后 1 个元素），。

寻找最优子结构

通过在序列中插入空格 “-” 表示 “S 从 T 生成” 的过程，将求解对齐的过程转化为多阶段决策过程：

• 每个决策阶段需选择 3 种操作之一：
  • 匹配 / 突变（Match/Mutation）：让 T 的第 i 位(T_i）与 S 的第 j 位（S_j）对齐；
  • 插入（Insertion）：让 S 的第 j 位（S_j）与空格 “-” 对齐；
  • 删除（Deletion）：让 T 的第 i 位（T_i）与空格 “-” 对齐。

以 “OCURRANCE”（S）和 “OCCURRENCE”（T）为例，展示三种操作对应的对齐形式

• 匹配 / 突变：S' 与 T' 的对应字符直接对齐；
• 插入：S' 的字符与 T' 的 “-” 对齐；
• 删除：S' 的 “-” 与 T' 的字符对齐。

从这个例子我们可以看出，对于两个序列的对齐问题，最后一个元素要么是匹配 / 突变、要么是插入、要么是删除。我们可以以此，来将其分解成三个子问题：

• 场景 1（匹配 / 突变）：S_n来自T_m（T 的最后一位）→ 子问题：对齐 T 的前缀T[1..m-1]与 S 的前缀S[1..n-1]；
• 场景 2（插入）：S_n是插入操作→ 子问题：对齐 T 的完整序列T[1..m]与 S 的前缀S[1..n-1]；
• 场景 3（删除）：S_n来自 T 的前缀T[1..m-1]→ 子问题：对齐 T 的前缀T[1..m-1]与 S 的完整序列S[1..n]。

1. 子问题的通用定义：将子问题抽象为 “对齐 T 的前缀T[1..i]与 S 的前缀S[1..j]”，并将该子问题的 最优得分（即最大化得分函数的结果）记为OPT(i,j)。

2. 最优子结构性质（递归公式）：原问题的最优解可由子问题的最优解推导，因此OPT(i,j)是以下三种情况的最大值（对应三种操作的得分 + 子问题得分）：其中s(a,b)是之前定义的 “单位置得分函数”（匹配 + 1、突变 - 1、插入 / 删除 - 3）。

算法

由此我们就可以写出这个问题的算法：

这里我解释一下初始化的部分：

计算 OPT[i,0] = -3 × i表示 “T 的前缀T[1..i]与空序列对齐”：空序列等价于全空格，因此 T 的每个元素对应删除操作（得分 - 3），i 个元素的总得分是 -3i。同样的，计算 OPT[0,j] = -3 × j表示 “S 的前缀S[1..j]与空序列对齐”：S 的每个元素对应插入操作（得分 - 3），j 个元素的总得分是 -3j。

下面看一下OPT表的更新过程：

首先是初始化

该图说明了为什么要引入第一行/列，其实就是为了最后能有一个递归出口。

下面我们详细说明一下该表如何更新：

重述一遍：OPT(i,j)表示：“T 的前 i 个字符” 与 “Y 的前 j 个字符” 对齐的最优得分。因此，红圈就表示OPT("OC", "OCUR")。计算公式为：

操作 1：匹配 / 突变（T 的第 i 个字符与 S 的第 j 个字符对齐）

• 逻辑：T 的第 i 个字符（此处 T 的第 2 个字符是C）与 S 的第 j 个字符（此处 S 的第 4 个字符是R）对齐，得分由 “子问题OPT(i-1,j-1)的得分 + 该位置的匹配 / 突变得分” 决定。
• 计算：
  • 子问题：OPT(i-1,j-1)=OPT(1,3)（T 的前 1 个字符O与 S 的前 3 个字符OCU对齐的得分，对应矩阵 “第 1 行、第 3 列” 的单元格，得分是-5）；
  • 匹配 / 突变得分：C与R不匹配（属于突变），得分-1；
  • 操作 1 的总得分：-5 + (-1) = -6。

操作 2：删除（T 的第 i 个字符与空格对齐）

• 逻辑：T 的第 i 个字符（C）被删除，得分由 “子问题OPT(i-1,j)的得分 + 删除操作得分（-3）” 决定。
• 计算：
  • 子问题：OPT(i-1,j)=OPT(1,4)（T 的前 1 个字符O与 S 的前 4 个字符OCUR对齐的得分，对应矩阵 “第 1 行、第 4 列” 的单元格，得分是-8）；
  • 操作 2 的总得分：-8 + (-3) = -11。

操作 3：插入（S 的第 j 个字符与空格对齐）

• 逻辑：S 的第 j 个字符（R）是插入的，得分由 “子问题OPT(i,j-1)的得分 + 插入操作得分（-3）” 决定。
• 计算：
  • 子问题：OPT(i,j-1)=OPT(2,3)（T 的前 2 个字符OC与 S 的前 3 个字符OCU对齐的得分，对应矩阵 “第 2 行、第 3 列” 的单元格，得分是-1）；
  • 操作 3 的总得分：-1 + (-3) = -4。

取 3 种操作得分的最大值：max(-6, -11, -4) = -4，这就是OPT(2,4)（即OPT("OC", "OCUR")）的得分，对应矩阵中 “第 2 行、第 4 列” 的单元格值。

最终对齐形式：S' = O-CURRANCE、T' = OCCURRENCE，验证了 “该错误序列与正确序列的最优对齐得分是 4”，即对应最可能的生成过程。

回溯

我们可以从OPT表中通过反向遍历来得到最优对齐形式

以 “T=OCCURRENCE、S=OCURRANCE” 的得分矩阵为例：

• 从最终得分单元格（红色圈出的 “4”，对应 OPT(m,n)）开始，沿红色圈出的路径反向遍历OPT表；
• 每一步回溯对应一种对齐操作（匹配 / 插入 / 删除），最终得到具体对齐结果：S' = O-CURRANCE、T' = OCCURRENCE（即之前拼写纠错的最优对齐形式）。