Dayi Lin, Ph.D.

Staff Researcher, AI & Software Engineering

Tag: 动态规划

最小编辑距离 算法原理

问题 最小编辑距离 Minimum Edit Distance关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。例如 s1 = “12433” 和 s2 = “1233”;则可以通过在s2中间插入4得到12433与s1一致。即 d(s1,s2) = 1 (进行了一次插入操作) 性质 计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“c1″,”c2”) = c1 == c2 ? 0 : 1; 2. d(s1+c1,s2+c2) = min( d(s1,s2)+ c1==c2 ? 0 : 1 , 1 + d(s1+c1,s2), 1 + d(s1,s2+c2) ); 第一个性质是显然的。第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法,于是对c1,c2可能的操作只有: 1.

LCS(最长公共子序列)

上次在实验室作《从分治到动归 – 最优问题解法》的讲座的时候,举了LCS(最长公共子序列)作为例子: LCS问题 LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。 例如: X={A,B,C,B,D,A,B} Y={B,D,C,A,B,A} 则X和Y的最长公共子序列(之一)是{B,C,B,A} 传统动归解LCS 设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]} 其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。 初值:f[i][0]=0; f[0][i]=0; f[1][1] = same(1,1) 这个动归方程乍看可能不好理解。它的思想是这样的。 对于已知f[i][j]的值,要往后拓展,有这两种情况:其末位i和j相同,或不相同。 考虑相同情况。因为i和j相同,它们必然已被记入最长公共子序列的部分。此时要想延长这个公共子序列,只得令i和j都向后移,看看它们后一位是否也相同。这就是f[i][j]+same(i+1,j+1)。 而对于不同情况,有这几种可能: 虽然第i和j位不相同,但i和j+1是相同的。此时要想延长,便是f[i][j+1]的情况。当然也可能i+1和j相同,便是f[i+1][j]的情况。 综上,写成递归式,因为不知道前一个状态的情况,所以便在这三种可能中取最大值。此时f[i][j]变为f[i-1][j-1],f[i][j+1]变为f[i-1][j],f[i+1][j]变为f[i][j-1]。便得到了上面的递归式。而初值很好理解,这里就不赘述了。 不难算出,这个算法的时间复杂度是O(n^2),空间复杂度也是O(n^2),但因为状态只与上一行有关,所以可以将空间复杂度优化至O(n)。