首页 > 代码库 > [CLRS][CH 15.4] 最长公共子序列

[CLRS][CH 15.4] 最长公共子序列

---恢复内容开始---

摘要

介绍了最长公共子序列的概念及解题思路。

子序列概念

子序列:一个给定序列的子序列就是该给定序列中,去掉零个或多个元素。一般来说,给定一个序列 X = <x1, x2, ..., xm>,另一个序列 Z = <z1, z2, ..., zk> 如果存在X的一个严格递增下标序列<i1, i2, ..., ik>,使得所有的j = 1, 2, ..., k,有xij = zj,则Z是X的一个子序列。例如,Z = <B, C, D, B> 是 X = <A, B, C, B, D, A, B> 的一个子序列,相应下标序列为<2, 3, 5, 7>。

公共子序列:给定两个序列X和Z,如果Z既是X的子序列又是Y的子序列,则称Z为X和Y的公共子序列。

最长公共子序列(Longest Common Substring, LCS):就是最长的那个公共子序列了。

在最长子序列问题中,给定两个序列 X = <x1, x2, ..., xm> 和 Y = <y1, y2, ..., yn>,希望找出X和Y的LCS。我们可以用动态规划来有效解决。

步骤1:描述一个LCS

解决LCS问题的一种强力方法是枚举X所有子序列,逐一检查是否为Y的子序列,并记录所发现的最长子序列。对于有m个元素的序列X,一共有2m个子序列,显然不切实际。

然而LCS问题具有最优子结构性质。给定一个序列 X = <x1, x2, ..., xm>,对于i = 0, 1, ..., m,定义X的第i个前缀为 Xi = <x1, x2, ..., xi>。
例如,如果 X = <A, B, C, B, D, A, B>,则 X4 = <A, B, C, B>,而X0是一个空序列。

定理(LCS的最优子结构):设 X = <x1, x2, ..., xm> 和 Y = <y1, y2, ..., yn> 为两个序列,并设 Z = <z1, z2, ..., zk> 为X和Y的任意一个LCS。
1)如果 xm = yn, 那么 zk = xm = y且 Zk-1 是 Xm-1 和 Yn-1 的一个LCS;
2)如果 xm != yn,那么 zk != xm 蕴含 Z 是 Xm-1 和 Y 的一个LCS;
3)如果 xm != yn,那么 zk != yn 蕴含 Z 是 Yn-1 和 X 的一个LCS。

证明:这他妈说了个啥。
1)如果 zk != xm ,则可以添加 xm = y到Z中,即得到X和Y的一个长度为k+1的公共子序列,与Z是X和Y的LCS矛盾,因而必有 zk = xm = yn。并且此时前缀 Zk-1 是 Xm-1 和 Yn-1 的长度为k-1的公共子序列。假设 Xm-1 和 Yn-1 有一个长度大于k-1的公共子序列W,那么 xm = y添加到W上就会产生一个长度大于k的公共子序列,因而与Z是X和Y的LCS矛盾。得证。
2)如果 zk != xm 那么Z是 Xm-1 和 Y 的一个LCS。如果 Xm-1 和 Y 有一个长度大于k的公共子序列W,则W也应该是 Xm 和 Y 的一个公共子序列,这与Z为X和Y的LCS的假设矛盾。得证。
3)与证明2)对称,得证。

解释:这条定理的特征说明两个序列的一个LCS也包含了两个序列的前缀的一个LCS。这就说明LCS问题具有最优子结构性质。

步骤2:一个递归解

根据定理我们可知在找 X = <x1, x2, ..., xm> 和 Y = <y1, y2, ..., yn> 的一个LCS时,可能要检查一个或两个子问题。即:
如果 xm = y,必须找出 Xm-1 和 Yn-1 的一个LCS。将 xm = y添加到这个子LCS上,产生X和Y的一个LCS;
如果 xm != yn,就必须解决两个子问题:找出 Xm-1 和 Y 的一个LCS,以及 Yn-1 和 X 的一个LCS。这两个LCS中,较长的就是X和Y的一个LCS。

很容易看出LCS问题中重叠子问题性质。定义c[i,j]为序列Xi和Yi的一个LCS长度。如果i=0或j=0,其中一个的序列长度为0,因而LCS长度为0。由此得递归方程:

$\textrm{c}[i,j]= \begin{cases} 0&,\ i = 0\or\ j=0\\ c[i-1,j-1]+1&,\ i,j>0 \or\ x_{i}=y_{i}\\ \textrm{max}(c[i,j-1],c[i-1,j])&,\ i,j>0 \or\ x_{i}\neq y_{i} \end{cases}$

步骤3:计算LCS长度

过程LCS-LENGTH以两个序列 X = <x1, x2, ..., xm> 和 Y = <y1, y2, ..., yn> 为输入。运行时间为O(mn)。
它把c[i,j]的值填入一个按行计算表项的表c[0..m, 0..n]中(如下图);
它还维护表b[1..m, 1..n]以简化最优解的构造,b[i,j]指向一个表项,对应于在计算c[i,j]时所选择的最优子问题的解;
它返回表b和c;c[m,n]即为X和Y的一个LCS长度。 

 

LCS-LENGTH(X, Y)// 初始化表项m = length[X]n = length[Y]for i = (0 to m) c[i,0] = 0for j = (0 to n) c[0,j] = 0// 循环计算LCS长度for i = (1 to m)    for j = (1 to n)        if (x[i] = y[j])            c[i,j] = c[i-1,j-1] + 1            b[i,j] = &b[i-1,j-1]        else if (c[i-1,j] >= c[i,j-1])            c[i,j] = c[i-1,j]            b[i,j] = &b[i-1,j]        else            c[i,j] = c[i,j-1]            b[i,j] = &b[i,j-1]// 返回结果return b and c

步骤4:构造一个LCS

我们可以很容易地根据表b的结果快速构造X和Y的LCS。首先从b[m,n]开始,根据指针跟踪下去。每当遇到一个指向左上方的指针时,意味着 xm = y是LCS的一个元素,输出尔后继续追踪。该跟踪过程运行时间为O(m+n)。

改进代码

我们可以完全去掉表b,每个表项c[i,j]仅依赖于另外三个c的表项,即c[i-1,j-1], c[i-1,j], c[i,j-1]。给定c[i,j]的值,我们可以在O(1)时间内确定这三个值中哪一个是被用来计算c[i,j]的,而不用检查表b。这样我们就可以在同样O(m+n)时间内重构一个LCS。这种方法节省了O(mn)的空间。但并没有节省运行时间。当然,我们可以更激进一些,如果不需要重构LCS,只要求结果的话,我们只要c中两行数据就可以计算。因而进一步节省了空间。

[CLRS][CH 15.4] 最长公共子序列