月度归档:2015年08月

动态规划与编辑距离问题

动态规划Dynamic Programming)是一种精妙的算法设计技巧,在多种成熟的算法模型中都有动态规划思想的运用。

首先考虑一个简单的爬楼梯问题:一段楼梯共有 n 级阶梯,每次可以向上爬 1 级或 2 级,问一共有多少种上楼梯的方法。

假设在一段楼梯中,爬上第 i 级阶梯一共有 Si 种方法,容易观察到存在 Si = Si-2 + Si-1 (i = 3, 4, 5, …, n)的递推关系,同时显而易见地,有 S1 = 1, S2 = 2 的初始条件。因此,要求 Sn 的值,只需要通过递推关系先后求出 S3, S4, S5, … Sn 的值即可。

存在递推关系是一个问题可以用动态规划思想求解的必要条件。像上述求解爬楼梯问题一样,用动态规划求解一个规模为 n 的问题时,先考虑规模为 1, 2, 3… 等子问题是否有显而易见的解,再找出递推关系,利用递推关系逐步求解更大规模子问题的解,直到最终解出规模为 n 的问题。

动态规划思想经常用于解决最大、最小、最短、最优的路径等问题,在解决这类问题时,要确保找到的递推关系在每一步的计算结果都是符合问题中最大、最小、最短或最优要求的。另外,这类问题经常在每一步都有多个候选的解,需要用数组将这些候选解全部暂时存储起来。下面是一个经典的用动态规划求解的问题:一些数排列成一个三角形,从三解形的顶部出发,每次可以向左下或右下走一步,求走到最底部时经历的所有数之和最小的路径。

   2
  3 4
 6 5 7
4 1 8 3

首先,很显然的是,当这个问题的规模为 1(即只有一行)时,问题的解就是 2。设 Nij 表示这个三角形的第 i 行的第 j 个数(i、j 均从 0 开始计),Sij 表示从根出发到 Nij 可能的所有路径中经历所有的数(包括 Nij)的最小的和,可以得到如下的递推关系:Sij = min(Si-1 j, Si-1 j-1) + Nij。min(x, y) 表示 x, y 中较小的那个数。

然后逐步增加问题的规模,用递推关系解出每一步的结果:当子问题规模为 2、3、4(即 2 行、3 行、4 行)时,(Sn0, Sn1, …, Snn) 分别是 (5, 6)、(11, 10, 13)、(15, 11, 18, 16)。在最终的结果中选出最小的数 11 即为本问题的解。

下面的代码是上述算法的 Python 实现。

不同的问题递推关系中需要的已知条件可能各不相同,有的只需要前一步的结果有的需要前更多步甚至之前所有的结果;如上面的问题只需要前一步的结果,而爬楼梯问题则需要前一步和前两步的结果等。在编写程序时应当根据递推关系的特点暂存前一步或更多步的计算结果。

动态规划一个实用的应用是求编辑距离Edit Distance)。一个字符串可以经历有限次变换步骤转变成另一个字符串,假设每个步骤只允许在字符串的任意位置增加、删除或修改一个字符,由字符串甲转换到字符串乙可行的最少步骤数即是这两个字符串之间的编辑距离。编辑距离在 DNA 分析、拼写检查、语音识别、抄袭检测等多个领域都有应用。

例如,可以通过如下的三个步骤将单词“kitten”转变为“sitting”:

  1. kitten → sitten(k → s)
  2. sitten → sittin (e → i)
  3. sittin → sitting (→ g)

从源字符串经过一系列编辑动作转换为目标字符串的可行路径很多,求解编辑距离实质上就是寻找一条这样的最短路径,并得到它的长度。为了找到最短的编辑路径,可以运用上述的动态规划的思想。

前文中讲到,用动态规划求解问题,首先考虑一个较小规模的子问题是否有显而易见的解。对于编辑距离问题来说,“规模”存在于源字符串和目标字符串的长度两个维度,例如“将字符串 k 转变为字符串 s”是最小规模的一个子问题;“将字符串 ki 转变为字符串 s”与“将字符串 k 转变为字符串 si”为两个维度上不同的两个次小规模的子问题。显然,它们都有显而易见的解。

用下图的一个二维表格来表示上述编辑距离问题中每一个子问题的解的情况。

图 1 用二维表格表示一个编辑距离问题解的情况

在上述表格中,设 Cij 为第 j 行第 i 列的单元格,单元格 Cij 中将填入的数字表示源字符串的长度为 i 的子字符串转换为目标字符串长度为 j 的子字符串的编辑距离。例如,C45 表示字符串 kitt 转换为字符串 sitti 的编辑距离。特别地,当 i 或 j 为 0 时的单元格表示的是空源字符串或空目标字符串。

上述的表格第 0 行表示一个字符串转换为空字符串的编辑距离,显而易见地,这一行中所有单元格的数值是所对应的源字符串的长度;同理,上述表示中第 0 列表示一个空字符串转换为目标字符串的编辑距离,这一列中所有单元格的数值是所对应的目标字符串的长度。所以有 C0p = p, Cq0 = q,可以简单地填满第 0 行和第 0 列的所有单元格如下:

图 2 填写表格的第 0 行和第 0 列

接下来,考虑这个问题的递推关系。先假设 Si 表示源字符串长度为 i 的子字符串,Dj 表示目标字符串长度为 j 的子字符串,所以单元格 Cij 表示的是字符串 Si 转换为字符串 Dj 的编辑距离。由于编辑距离的定义中允许每步插入、删除或修改一个字符,因此由字符串 Sm 转换为字符串 Dn 有如下三种可行的方案:

  • 在由 Sm 转换的字符串 Dn-1 的末尾增加一个字符,编辑长度计 1,即 C’mn = Cm n-1 + 1;
  • 在由 Sm-1 转换的字符串 Dn 的末尾删去一个字符,编辑长度计 1,即 C”mn = Cm-1 n + 1;
  • 在由 Sm-1 转换的字符串 Dn-1 的末尾修改一个字符,编辑长度计 1,即 C”’mn = Cm-1 n-1 + 1;特别地,如果源字符串的第 m 个字符正好与目标字符串的第 n 个字符相同,则此次不必修改字符,即 C”’mn = Cm-1 n-1

由于编辑距离有路径最短的要求,必须在每一步转换中选择编辑长度最短的方案,以达到局部最优解。因此,Cmn 最终的结果可表示为 Cmn = min(C’mn, C”mn, C”’mn),min(a, b, c) 表示取 a, b, c 中最小的数。因为 Cmn 的结果只与 Cm-1 n、Cm n-1 和 Cm-1 n-1 三个数有关,所以上述式子构成解决编辑距离问题的递推关系。

有了递推关系,就可以从初始条件出发,逐步推算出每一个阶段的编辑路径了。在上文的例子中,从上向下、从左向右逐步填写二维表格最终如下:

图 3 通过递推关系逐步推算出所有单元格中的值

取表格中右下角单元格中的值,即是最终要求的编辑距离。如以上的例子中,字符串 kitten 到字符串 sitting 的编辑距离是 3。

下面是用 Python 语言实现的求解两个字符串编辑距离的程序代码。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=410 )

参考文献
[1] Wikipedia. 编辑距离[EB/OL]. https://zh.wikipedia.org/wiki/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2
[2] Wikipedia. Edit Distance[EB/OL]. https://en.wikipedia.org/wiki/Edit_distance