计算两个字符串的相似度---动态规划实现：关键是填表

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：

　　1.修改一个字符（如把“a”替换为“b”）;

　　2.增加一个字符（如把“abdd”变为“aebdd”）;

　　3.删除一个字符（如把“travelling”变为“traveling”）;

分析与解法　　

　　不难看出，两个字符串的距离肯定不超过它们的长度之和（我们可以通过删除操作把两个串都转化为空串）。虽然这个结论对结果没有帮助，但至少可以知道，任意两个字符串的距离都是有限的。

　　我们还是就住集中考虑如何才能把这个问题转化成规模较小的同样的子问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是相同的，只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行如下的操作（lenA和lenB分别是A串和B串的长度）。

　1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。

　2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。

　3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。

　4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。

　5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。

　6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。

　　在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：

　　1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。

　　2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。

　　3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。
分析如下：

如果source[i] 等于target[j]，则：
d[i, j] = d[i, j] + 0

如果source[i] 不等于target[j]，则根据插入、删除和替换三个策略，
分别计算出使用三种策略得到的编辑距离，然后取最小的一个：

d[i, j] = min(d[i, j - 1] + 1，d[i - 1, j] + 1，d[i - 1, j - 1] + 1 )


d[i, j - 1] + 1 表示对source[i]执行插入操作后计算最小编辑距离
d[i - 1, j] + 1 表示对source[i]执行删除操作后计算最小编辑距离
d[i - 1, j - 1] + 1表示对source[i]替换成target[i]操作后计算最小编辑距离


d[i, j]的边界值就是当target为空字符串（m = 0）或source为空字符串（n = 0）时所计算出的编辑距离：
m = 0，对于所有 i：d[i, 0] = i
n = 0，对于所有 j：d[0, j] = j

3.实现过程
a.首先是有两个字符串,这里写一个简单的 abc和abeb.将字符串想象成下面的结构

A处 是一个标记，为了方便讲解，不是这个表的内容。

	abc	a	b	c
abe	0	1	2	3
a	1	A处
b	2
e	3

c.来计算A处 出得值

它的值取决于：左边的1、上边的1、左上角的0.

按照Levenshtein distance的意思：

上面的值和左面的值都要求加1，这样得到1+1=2。

A处 由于是两个a相同，左上角的值加0.这样得到0+0=0。

这是后有三个值，左边的计算后为2，上边的计算后为2，左上角的计算为0，所以A处 取他们里面最小的0.

d.于是表成为下面的样子

	abc	a	b	c
abe	0	1	2	3
a	1	0
b	2	B处
e	3

在B处 会同样得到三个值，左边计算后为3，上边计算后为1，在B处 由于对应的字符为a、b，不相等，所以左上角应该在当前值的基础上加1，这样得到1+1=2，在（3,1,2）中选出最小的为B处的值。

e.于是表就更新了

 

	abc	a	b	c
abe	0	1	2	3
a	1	0
b	2	1
e	3	C处

C处 计算后：上面的值为2，左边的值为4，左上角的：a和e不相同，所以加1，即2+1，左上角的为3。

在（2,4,3）中取最小的为C处 的值。

f.于是依次推得到

		a	b	c
	0	1	2	3
a	1	A处 0	D处 1	G处 2
b	2	B处 1	E处 0	H处 1
e	3	C处 2	F处 1	I处 1

 

I处: 表示abc 和abe 有1个需要编辑的操作。这个是需要计算出来的。

同时，也获得一些额外的信息。

A处: 表示a      和a      需要有0个操作。字符串一样

B处: 表示ab    和a      需要有1个操作。

C处: 表示abe  和a      需要有2个操作。

D处: 表示a      和ab    需要有1个操作。

E处: 表示ab    和ab    需要有0个操作。字符串一样

F处: 表示abe  和ab    需要有1个操作。

G处: 表示a      和abc   需要有2个操作。

H处: 表示ab    和abc    需要有1个操作。

I处: 表示abe   和abc    需要有1个操作。

d[i][j] ：A[i-1] B[j-1]的距离，在后面的判断中要A[i-1]==B[j-1]???,为什么这个初始化我没有想到，搞到后面全都错了，填这个表有点难度！！
用动态规划更喜欢考虑前缀，但使用前缀时数组最好从位置1开始，因为dp数组的初始化一般要占用位置0，但字符串不方便从1开始读入 

#include
#include
#define Max 500


int d[Max+10][Max+10];
char str1[Max],str2[Max];

    int minValue(int a,int b,int c)
    {
        if(a
            return a;
        else if(b
            return b;
        else
            return c;
    }

    int simofstring(char la[],char lb[])
    {
        //memset(d,0,sizeof(d));
        int lenA=strlen(la);
        int lenB=strlen(lb);

        printf("A: %d B: %d\n",lenA,lenB);
        int i,j;

        for(i=0;i<=lenA;i++)
        {
            d[i][0]=i;//相当于某个字符串为空
        }
        for(j=1;j<=lenB;j++)
        {
            d[0][j]=j;//初始化边界
        }

        //动态规划填表
        for(i=1;i<=lenA;i++)
        {
            for(j=1;j<=lenB;j++)
            {
                if(la[i-1]==lb[j-1])
                {
                    d[i][j]=d[i-1][j-1]+0;
                }
                else
                {
                    d[i][j]=minValue(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1]+1);
                }
            }
        }
        //动态规划填表
        for(i=0;i<=lenA;i++)
        {
            for(j=0;j<=lenB;j++)
            {
                printf("%d ",d[i][j]);
            }
            printf("\n");
        }


    return d[lenA][lenB];
}


int main()
{
    char * A="abeaa";
    char * B="";
    int dis=simofstring(A,B);
    printf("%d\n",dis);
    return 0;
}
/*
A: 5 B: 0
0
1
2
3
4
5
5
Press any key to continue
*/

char * A="abeaa";

char * B="aef";

A: 5 B: 3

0 1 2 3

1 0 1 2

2 1 1 2

3 2 1 2

4 3 2 2

5 4 3 3

3

Press any key to continue