最小编辑距离 算法原理

问题

最小编辑距离 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.  把c1变成c2
2.  s1+c1后删除c1              d = (1 + d(s1, s2 + c2))
3.  s1+c1后插入c2              d = (1 + d(s1 + c1, s2))

对于2和3的操作可以等价于:
_2.   s2+c2后添加c1        d = (1 + d(s1, s2 + c2))
_3.   s2+c2后删除c2        d = (1 + d(s1 + c1, s2))

因此可以得到计算编辑距离的性质2。

复杂度分析

从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记,并假设两个串长度都为 n )
可以看到,该问题的复杂度为指数级别 3 的 n 次方,对于较长的串,时间上是无法让人忍受的。
分析: 在上面的结构中,我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

动态规划求解

首先为了避免重复计算子问题,添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s1[i] = s2[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到

M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;

根据性质2得到

M[ i, j ]   = min(  m[i-1,j-1] + E[ i, j ] ,
                    1 + m[i, j-1] ,
                    1 + m[i-1, j]  );

复杂度
从新的计算式看出,计算过程为

      i=1 -> |s1|
             j=1 -> |s2|
                    M[i][j] = ……

因此复杂度为 O( |s1| * |s2| ) ,如果假设他们的长度都为n,则复杂度为 O(n^2)

改进

当s[i]和s[j]相等时,代价为0,必然为最小值,所以首先判断两字符是否相等,若相等则直接判定M[i][j]=M[i-1][j-1],判断下个。这样可以省很多计算。

工具宏:直接用一个宏来完成“求取三者最小值”的功能。不同于递归,宏定义消耗很小,完全可以放心使用。

#ifndef _MIN(xyz)
#define _MIN(xyz) ((x<y)?((x<z)?x:z):((y<z)?y:z))
#endif // _MIN(xyz)

再议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)。

另一种解法?(以下内容有误,13/10/25勘误)

网络上还能找到另一种解决这个问题的方法:

(1)将两个字符串分别以行和列组成矩阵。

(2)计算每个节点行列字符是否相同,如相同则为1。

(3)通过找出值为1的最长对角线即可得到最长公共子串本方法只能得到最长连续公共子串,下列讨论关于最长公共子串全部应替换为最长连续公共子串。

为进一步提升该算法,我们可以将字符相同节点的值加上左上角(d[i-1,j-1])的值,这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

这个方法非常好理解,直观易懂。而不难发现它的时间复杂度,竟然也是O(n^2),空间复杂度也可以由O(n^2)优化到O(n)!

这是巧合吗?

我们来分析一下这个做法。首先我们能总结出这个方法的递推式:d[i][j]=d[i-1][j-1]+same(i,j)。是不是很眼熟?但和上面的还不大一样啊?缺了两种情况呢。

别急,这个方法还需要在全矩阵中找出最大的值。而上面的动归方程,分散在各个状态求max的过程,合并起来,不就是求全矩阵的最大值吗?这段也有错误。详见下方勘误。

殊途同归!

动归解法通过记录各个不同截取位置的方法,避免朴素解法中的重复比较,从而提升了效率。而这个方法中的矩阵,其作用不难发现,也是一种记录的行为。

思想只存于我们的脑子中,我们的思维使算法发生了变化。但其结果,却殊途同归。

算法,是一种哲学。

2013年10月25日勘误

POJ-2240 解题报告

题意简述

输入货币名称以及货币间的汇率(A到B的汇率可能与B到A的不同),判断是否有可能实现套汇(即从某指定货币开始,通过一系列的货币兑换操作,最终换回某货币并实现盈利)。

问题有多组数据,对于每组数据,第一行代表货币类别数量,第二行起的n行为各货币名称;接下来一行是允许的兑换方式总数,而后每行有三个部分,第一个和第三个分别是原始货币和兑换后货币的名称,第二个是汇率。数据的输入以0结束。

对于每组数据,输出是否可能实现套汇(YES或NO)。 Continue reading “POJ-2240 解题报告”

POJ-1125 解题报告

题意简述

股票经纪人之间的关系形成了一个有向关系网。每个股票经纪人向与他关联的另一个人传递一条谣言需要花费的时间各不相同。A向B传播谣言耗时并不一定等于B向A传播耗时。某经纪人收到谣言后会同时开始向他所有关联的经纪人传播谣言。给定股票经纪人之间的关系网以及每个经纪人向特定经纪人传播消息的耗时,问谣言从哪个股票经纪人开始传播能最快的使整个网所有人知道该谣言,并输出最短耗时。如果存在某经纪人无论如何无法得知该谣言,输出disjoint。

Continue reading “POJ-1125 解题报告”

POJ-1062 解题报告

题意简述

你想娶酋长的女儿,但酋长要求你给一定数额金钱的聘礼。除了金钱外,酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。

例:

最高最低等级差不超过1,共4个物品

酋长的女儿    等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元

甲的物品        等级2     要求现金1000元        或丙的物品+200元

乙的物品        等级2     要求现金3000元        或丙的物品+200元

丙的物品        等级2      要求现金50元

在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。

Continue reading “POJ-1062 解题报告”

POJ-2253 解题报告

题意简述

湖中有N(2<=N<=200)块石头,标号从1到N。青蛙1在石头1上,青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2,它可以经由任意石头组成的路径。在所有可能路径中找出一条路径,使其中最长的一步的长度小于其他路径中最长的一步的长度。

本题可以化简为,点1与点2间存在若干条路径,每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

Continue reading “POJ-2253 解题报告”

POJ-1860 解题报告

题意简述

某城市有M(1<=M<=100)个货币兑换站,可以兑换N(1<=N<=100)种货币,每个兑换站只能互换两种货币,且汇率与手续费各不相同。某人初始时手中有V元货币S,问他是否有可能通过货币兑换,在最后换回货币S时实现盈利,有可能则输出YES,否则输出NO。 Continue reading “POJ-1860 解题报告”

POJ-3259 解题报告

题意简述

农夫共有F(1≤F≤5)个农场,每个农场有N块田(1 ≤ N ≤ 500)和M条普通无向路(1 ≤ M ≤ 2500),走过这些路需要一定时间。同时还存在W条有向虫洞(1 ≤ W ≤ 200),走这些虫洞可倒流一定时间。问对于各个农场,农夫是否有可能从某点出发,回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES,否则为NO。 Continue reading “POJ-3259 解题报告”