编辑距离问题

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 动态规划,编辑距离问题,问题描述：,设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：,（1）删除一个字符；,（2）插入一个字符；,（3）将一个字符改为另一个字符。,将字符串A变换为字符串B所用的,最少字符操作数,称为字符串A到B的,编辑距离,，记为 。,算法设计：,对于给定的字符串A和字符串B，计算其,编辑距离 。,数据输入：输入数据的第一行是一个正整数，表示一共有几组数据。每组数据两行，每行一个字符串。,*每个字符串长度不超过1000,结果输出：输出编辑距离 。对于每组数据，请输出一个整数表示两个字符串的编辑距离。每个答案占一行。,Sample Input ： Sample Output：,2 4,david 3,vivian,abc,aabbcc,分析与解答：,设所给的两个字符串为,A1:m和B1:n,，定义一个二维数组,dpij,表示状态，,dpij= (,A1:i,B1:j,),表示字符串,A1:m的子串A1:i变换到B1:n的子串B1:j的编辑距离，即子串A1:i至少要经过多少次操作（插入、删除、修改）可以变为B1:j。单字符a,b间的编辑距离定义为,例如，字符串A:AGTAAGTAGGC转换为,字符串B:AGTCTGACGC 。,操作一,：,A,串：,A G T A A G T * A G G C,B串,：,A G T * C * T G A C G C,需要5步操作（2次删除，2次修改，1次删除）,操作二：,A,串：,A G T A A G T A G G C,B串,：,A G T C T G * A C G C,需要4次操作（3次修改，1次删除）,我们计算的编辑距离是变换的最小步数，所以要取,其中的最小值。,考察从字符串A1:i到字符串B1:j的转换，有三种情况可以导致上面设计的状态发生转移：,（1）可以删除字符Ai需要1次操作。只将字符Ai从A串中删除，对序列B1:j没有任何影响，此时问题的最优子结构形式为将A1:i-1 变为B1:j ，再加一步删除操作，可得dpij = dpi-1j + 1。,（2）可以在Ai后面插入一个字符ch（ch=Bj）需要1次操作。在进行插入操作时，串A1:i 无任何变化，在A串i+1,位置上插入字符Bj,问题的最优子结构形式为将A1:i变,为B1:j-1,再加一步插入操作，可得dpij = dpi j-1 + 1。,（3）可以修改字符Ai，使它变为Bj，若Ai=Bj，修改,其实相当于用了0步；若Ai != Bj，修改相当于用了1步。,所以dpij = dpi - 1j - 1 + （Ai = Bj ? 0：1）。,最后的,dpij就是选择上述3种状态转移中的最小值。,综上所述，状态转移方程dpij可归结为如下情况：,(1)当两个字符相同，即Ai=Bj时，,dpij = mindpij-1+1, dpi-1j+1, dpi-1j-1,(2)当两个字符不同，即Ai != Bj时，,dpij = mindpij-1+1, dpi-1j+1, dpi-1j-1+1,需要注意的是，要对dp00:m，dp0:n0进行初始化。,*dp0i,就是说A串是一个空串，而B串是个长度为i的串，很显然A串变为B串就是插入i个字符，即dp0i=i。,*dpi0 ，就是说A串是个长度为i的串，而B串是一个空串，很显然A串变为B串就是删除i个字符，即dpi0=i。,根据上述分析，编辑最短距离的算法可描述如下：,i,nt DP(char *s1,char *s2),int i,j,m=strlen(s1),n=strlen(s2),tem;,/,/初始化,f,or(i=0;i=n;i+) dp0i=i;,/从0个字符转换为i个字符，需要插入i次,一重循环时间复杂度为T(n),for(i=0;i=m;i+) dpi0=i; /从i个字符转换为0个字符，需要删除i次,一重循环时间复杂度为T(m),/用动态规划方法计算编辑距离,for(i=1;i=m;i+),for(j=1;j=n;j+),if(s1i-1=s2j-1),te,m=dpi-1j-1; /,当两个字符相同时，替换操作代价为0 ，,直接将dpi-1,j-1, 转移过来,else,tem=dpi-1j-1+1; /当s1i-1!=s2j-1时, 替换操作代价为1,tem=min(tem,dpij-1+1); /dpij-1+1为在s1的i+1位置上插入字符s2j,tem=min(tem,dpi-1j+1); /dpi-1j+1为在s1的i位置上删除字符s1i,dpij=tem; /dpij取3种状态的最小值,return dpmn; / /返回dpmn,二重循环：时间复杂度为T(n*m),时间复杂度：,总的时间复杂度为T(n*m+n+m)=O(m*n),最坏的时间复杂度为O(n2),运行结果示例：,The end,thank you!,