编辑距离

发表于   |   分类于   |  

先给出编辑距离的定义：设A和B是2个字符串，要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
(1)删除一个字符(delete)；
(2)插入一个字符(insert)；
(3)将一个字符改为另一个字符(substitute)。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离(edit distance)。

  • if i == 0 且 j == 0，edit(i, j) = 0
  • if i == 0 且 j > 0，edit(i, j) = j
  • if i > 0 且j == 0，edit(i, j) = i
  • if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

由公式可以看出，(i-1,j)对应删除操作，(i,j-1)对应插入操作。可以这样理解，现在耗费了di-1,j步操作将字符串a(1,i-1)转换成了b(1,j)，则在将a(1,i)转换成b(1,j)时，我们可以直接删掉字符a(i)，问题变成a(1,i-1)转换成b(1,j)，从而dij就等于di-1,j+1。同理，现在耗费了di,j-1步操作将字符串a(1,i)转换成了b(1,j-1)，则在将a(1,i)转换成b(1,j)时，我们可以将b(j)添加到a(1,i)末尾（此时a(1,i)已转换成b(1,j-1)）构成b(1,j)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int minOne(int a,int b)
    {
        if(a<b) return a;
        return b;
    }
    int minDistance(string word1, string word2) {
        int len1=word1.length();
        int len2=word2.length();
        if(len1==0) return len2;
        else if (len2==0) return len1;
        int dis[1000][1000];
        for(int i=0;i<=len1;i++)
        {
            dis[i][0]=i;
        }
         for(int i=0;i<=len2;i++)
        {
            dis[0][i]=i;
        }
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                int cost;
                if(word1[i-1]==word2[j-1]) //这儿要注意，dis中的i对应word中的i-1
                    cost=0;
                else 
                    cost=1;
                dis[i][j]=minOne(dis[i-1][j-1]+cost,minOne(dis[i-1][j]+1,dis[i][j-1]+1));
            }
        }
        return dis[len1][len2];
    }