编辑距离

逃离我推掉我的手 2022-06-10 09:08 256阅读 0赞

**一、问题描述**

设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：

（1）删除一个字符；

（2）插入一个字符；

（3）将一个字符改为另一个字符；

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。

**二、分析解答**

设所给的两个字符串为A\[1:m\]和B\[1:n\]。定义D\[i\]\[j\]=d(A\[1:i\],B\[1,j\])。单字符a,b间的距离定义为：

d(a,b)=0 (a=b)

d(a,b)=1(a!=b)

考察从字符串A\[1:i\]到字符串B\[1:j\]的变换。可分成以下几种情况：  
（1）字符A\[i\]改为字符B\[j\]；需要d(A\[i\],B\[j\])次操作。

（2）删除字符A\[i\]；需要1次操作。

（3）插入字符B\[j\]；需要1次操作。  
因此，D\[i\]\[j\]可递归地计算如下。

D\[i\]\[j\]=min\{D\[i-1\]\[j-1\]+d(A\[i\],B\[j\]),D\[i-1\]\[j\]+1,D\[i\]\[j-1\]+1\}。

**三、算法描述**

int dist(A\[0…m-1\],B\[0…n-1\])

int D\[0…m,0…n\]

int i,j,cost

对于i等于0至m

D\[i, 0\]=i

对于j等于0至n

D\[0,j\]=j

对于i等于1至m

对于j等于1至n

若A\[i-1\]=B\[j-1\]则cost=0 否则 cost=1

D\[i\]\[j\]=min(D\[i-1,j\]+1,//删除

D\[i,j-1\]+1,//插入

D\[i-1,j-1\]+cost//替换

)

返回d\[m,n\]

**四、代码实现**

定义一个二维数组D\[\]\[\]存储中间结果，如下图所示，为已经初始化后的情况。然后从D\[1,1\]开始从左到右，从上到下依次按填表，表的最后一个元素D\[m,n\]就是要求的最终结果。

<table> 
 <tbody> 
 <tr> 
 <td> <code>#include&lt;iostream&gt; #include&lt;string&gt; using namespace std; int D[100][100]; int dis[100]; int min(int a,int b,int c) { &nbsp;&nbsp;&nbsp;&nbsp;returnc&lt;(a&gt;b?b:a)?c:(a&gt;b?b:a); } int dist(char * A,char * B) { &nbsp;&nbsp;&nbsp;&nbsp;intm=strlen(A); &nbsp;&nbsp;&nbsp;&nbsp;intn=strlen(B); &nbsp;&nbsp;&nbsp;&nbsp;inti,j; &nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i&lt;=m;++i) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D[i][0]=i; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;for(j=0;j&lt;=n;++j) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D[0][j]=j; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;intcost; &nbsp;&nbsp;&nbsp;&nbsp;for(i=1;i&lt;=m;++i) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(j=1;j&lt;=n;++j) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(A[i-1]==B[j-1]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cost=0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cost=1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;D[i][j]=min(D[i-1][j-1]+cost,D[i-1][j]+1,D[i][j-1]+1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;returnD[m][n]; } int dist2(char * A,char * B) { &nbsp;&nbsp;&nbsp;&nbsp;intm=strlen(A); &nbsp;&nbsp;&nbsp;&nbsp;intn=strlen(B); &nbsp;&nbsp;&nbsp;&nbsp;inti,j; &nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i&lt;=n;++i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[i]=i; &nbsp;&nbsp;&nbsp;&nbsp;intcost; &nbsp;&nbsp;&nbsp;&nbsp;for(i=1;i&lt;=m;++i) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;inty=i-1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(j=1;j&lt;=n;++j) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;intx=y; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y=dis[j]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;intz=j&gt;1?dis[j-1]:i; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cost=A[i-1]==B[j-1]?0:1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[j]=min(x+cost,y+1,z+1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;returndis[n]; } int main(int argc, char* argv[]) {&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;char* ch1="bcdefghijklmnopq"; &nbsp;&nbsp;&nbsp;&nbsp;char* ch2="abcdefghijklmnopadfsafwe"; &nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;dist(ch1,ch2)&lt;&lt;endl; &nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;dist2(ch1,ch2)&lt;&lt;endl; &nbsp;&nbsp;&nbsp;&nbsp;return0; } </code> </td> 
 </tr> 
 </tbody> 
</table>

`五、优化方法`

从上面算法可以看出，该算法时间复杂性为0(m\*n),空间复杂性为O（m\*n）。同时可以看出，当对第i行进行填表时，只需要用到第i-1行的数据，因此可以用一个一维数组dis\[0…n\]代替二维数组D\[0…m,0…n\]，因此空间复杂性降为O(n)。实现代码如上面函数dist2()所示。  
``

`文章来源：http://blog.sina.com.cn/s/blog_6473891f0100grx6.html`