liangsonghua/algorithm

数据结构和算法(精选)

algorithm's Issues

编辑距离问题

编辑距离问题

给定两个字符串S和T，对于T我们允许三种操作：

(1) 在任意位置添加任意字符

(2) 删除存在的任意字符

(3) 修改任意字符

问最少操作多少次可以把字符串T变成S？

例如： S＝ “ABCF” T = “DBFG”

那么我们可以

(1) 把D改为A

(2) 删掉G

(3) 加入C

所以答案是3。

分析： 这个最少的操作次数，通常被称之为编辑距离。“编辑距离”一次本身具有最短的意思在里面。因为题目有“最短”这样的关键词，首先我们想到的是BFS。是的，当S的距离为m, T的距离为n的时候，我们可以找到这样的操作次数的界限：

(1) 把T中字符全删了，再添加S的全部字符，操作次数m + n。

(2) 把T中字符删或加成m个，再修改 操作次数最多 |n – m| + m。

虽然，我们找到了这样的上界，BFS从实际角度并不可行，因为搜索空间是指数的，这取决于S中的字符种类——具体的数量级不好估计。

这个问题之所以难，是难在有“添加”“删除”这样的操作，很麻烦。我们试试换个角度理解问题，把它看成字符串对齐的问题，事实上从生物信息学对比基因的角度，我们可以这样理解问题。

给定字符串S和T，我们可以用一种特殊字符促成两个字符串的对齐。我们加的特殊字符是“-”, 我们允许在S和T中任意添加这种特殊字符使得它长度相同，然后让这两个串“对齐”，最终两个串相同位置出现了不同字符，就扣1分，我们要使得这两个串对齐扣分尽量少。

对于例子 我们实际上采取了这样的对齐方式：

12345

ABCF-

DB-FG

注意：如果要对齐，两个“-”相对是没有意义的，所以我们要求不出现这种情况。

那么看一下：

(1) S,T对应位置都是普通字符，相同，则不扣分。 例如位置2，4

(2) S,T对应位置都是普通字符，不同，则扣1分。 例如位置1

(3) S在该位置是特殊字符，T在该位置是普通字符，则扣1分，例如位置5

(4) S在该位置是普通字符，T在该位置是特殊字符，则扣1分，例如位置3

我们来看看扣分项目对应什么？

(1) 不扣分，直接对应

(2) 对应把T中对应位置的字符修改

(3) 对应在T中删除该字符

(4) 对应在T中添加该字符

好了，目标明确，感觉像不像 LCS？我们尝试一下：

设f(i,j)表示S的前i位和T的前j位对齐后的最少扣分。

那我们来看看最后一位，对齐的情况

(1) 必须S[i] == T[j], 这时前i – 1和j – 1位都已经对齐了，这部分肯定要最少扣分。这种情况下最少的扣分是f(i-1,j-1)

(2) 和（1）类似，S[i]≠T[j]，这种情况下最少的扣分是f(i -1, j – 1) + 1

(3) S的前i位和T的前（j – 1）位已经对齐了，这部分扣分也要最少。这种情况下最少的扣分是f(i,j-1) + 1

(4) S的前(i-1)位已经和T的前j位对齐了，这部分扣分要最少。这种情况下最少的扣分是f(i,j-1) + 1

具体f(i,j)取什么值，显然是要看哪种情况的扣分最少。

为了方便，我们定义函数same(i,j)表示如果S[i] == T[j]则为0，否则为1。

我们来表示一下递推式：

f(i,j) = min(f(i – 1, j – 1) + same(i,j), f(i – 1,j ) + 1, f(i, j – 1) + 1)

初值是什么？

f(0, j) = j

f(i, 0) = i

这时因为对于S的前0位，我们只能在之前加入“-”，或者说把T全部删掉了。类似地，对于T地前0位，我们只能把S的字符都加进来，别无选择。

注意上述两个式子的重合点 f(0,0) = 0也符合我们的定义，并不矛盾。

时间复杂度？ O(m * n)，空间复杂度？ O(m * n)。同样我们发现到f(i,j)只与本行和上一行有关，可以省掉一维的空间复杂度，从而达到O(n)。

优化后的伪代码：

for j = 0 to n do
    f[j] = j
endfor

for i = 1 to m do
    last = f[0]
    f[0] = i
    for j = 1 to n do 
        temp = f[i,j]
        f[i,j] = min(last + same(i,j), temp + 1, f[j – 1] + 1)
        last = temp
    endfor
endfor

注意： 我们对于i实际上更新j的顺序是由小到达的，所以我们需要保存“旧的”f[i-1,j – 1]。

最长公共子序列问题

一些概念：

（1）子序列： 一个序列A ＝ a1,a2,……an,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。

例如：

对序列 1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。

对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。

请注意：子序列不是子集，它和原始序列的元素顺序是相关的。

（2）公共子序列 ： 顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。

例如：

对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说

序列1,8,7是它们的一个公共子序列。

请注意： 空序列是任何两个序列的公共子序列。

例如： 序列1,2,3和序列4,5,6的公共子序列只有空序列。

（3）最长公共子序列

A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列。

仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5

它们的最长公共子序列是：

1,4,8,7

1,4,6,7

最长公共子序列的长度是4 。

请注意: 最长公共子序列不唯一。

请大家用集合的观点来理解这些概念，子序列、公共子序列以及最长公共子序列都不唯一，所以我们通常说一个最长公共子序列，但显然最长公共子序列的长度是一定的。

我们用Ax表示序列A的连续前x项构成的子序列，即Ax= a1,a2,……ax, By= b1,b2,……by, 我们用LCS(x, y)表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用L(x, y)表示Ax和By的一个最长公共子序列。

让我们来看看如何求LCS(x, y)。我们令x表示子序列考虑最后一项

（1） Ax ＝ By

那么它们L(Ax, By)的最后一项一定是这个元素！

为什么呢？为了方便，我们令t = Ax = By, 我们用反证法：假设L(x,y)最后一项不是t，

则要么L(x,y)为空序列（别忘了这个），要么L(x,y)的最后一项是Aa＝Bb ≠ t, 且显然有a < x, b < y。无论是哪种情况我们都可以把t接到这个L(x,y)后面,从而得到一个更长的公共子序列。矛盾！

如果我们从序列Ax中删掉最后一项ax得到Ax-1,从序列By中也删掉最后一项by得到By-1，(多说一句角标为0时，认为子序列是空序列)，则我们从L(x,y)也删掉最后一项t得到的序列是L(x – 1, y - 1)。为什么呢？和上面的道理相同，如果得到的序列不是L(x - 1, y - 1)，则它一定比L(x - 1, y - 1)短（注意L（，）是个集合！），那么它后面接上元素t得到的子序列L(x,y)也比L(x - 1, y - 1)接上元素t得到的子序列短，这与L(x, y)是最长公共子序列矛盾。

因此L(x, y) = L(x - 1, y - 1) 最后接上元素t

LCS(Ax, By) = LCS(x - 1, y - 1) + 1

（2） Ax ≠ By

仍然设t = L(Ax, By), 或者L(Ax, By)是空序列（这时t是未定义值不等于任何值）。

则t ≠ Ax和t ≠ By至少有一个成立，因为t不能同时等于两个不同的值嘛！

（2.1） 如果t ≠ Ax，则有L(x, y)= L(x - 1, y)，因为根本没Ax的事嘛。

LCS(x,y) = LCS(x – 1, y)

（2.2） 如果t ≠ By,l类似L(x, y)= L(x , y - 1)

LCS(x,y) = LCS(x, y – 1)

可是，我们事先并不知道t，由定义，我们取最大的一个，因此这种情况下,有LCS(x,y) = max(LCS(x – 1, y) , LCS(x, y – 1))。

看看目前我们已经得到了什么结论：

LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By

(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By

这时一个显然的递推式，光有递推可不行，初值是什么呢？

显然，一个空序列和任何序列的最长公共子序列都是空序列！所以我们有:

LCS(x,y) =

(1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By

(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By

(3) 0 如果x = 0或者y = 0

到此我们求出了计算最长公共子序列长度的递推公式。我们实际上计算了一个(n + 1)行(m + 1)列的表格（行是0..n，列是0..m)，也就这个二维度数组LCS(,)。

大概的伪代码如下：

输入序列A, B长度分别为n，m,计算二维表 LCS(int,int):

 for x = 0 to n do
 for y = 0 to m do
    if (x == 0 || y == 0) then 
        LCS(x, y) = 0
    else if (Ax == By) then
        LCS(x, y) =  LCS(x - 1,y - 1) + 1
    else 
        LCS(x, y) = ) max(LCS(x – 1, y) , LCS(x, y – 1))
    endif
 endfor
 endfor

注意： 我们这里使用了循环计算表格里的元素值，而不是递归，如果使用递归需要已经记录计算过的元素，防止子问题被重复计算。

LCS的应用:最长递增子序列LIS

原数组A的子序列顺序保持不变，而且排序后B本身就是递增的，这样，就保证了最长公共子序列的递增特性，如此，若想求数组的最长递增子序列，其实就是求数组A与它的排序B的最长公共子序列。这个问题也可以直接使用动态规划来求解