Chinaunix首页 | 论坛 | 博客
  • 博客访问: 261728
  • 博文数量: 41
  • 博客积分: 2013
  • 博客等级: 大尉
  • 技术积分: 523
  • 用 户 组: 普通用户
  • 注册时间: 2010-01-08 23:13
文章分类

全部博文(41)

文章存档

2010年(41)

我的朋友

分类: C/C++

2010-04-23 19:10:58

两个字符串之间的相似度可以用编辑距离来定义。所谓编辑,指的是,对字符串中的任一字符进行插入删除替换这三种操作。经过一定步骤的编辑,一个字符串可以变换为另一个字符串,那么最少的编辑步数称为两个字符串的编辑距离。

这是一个递归或动态规划的问题。比如长度分别为m,n的字符串str1和str2,其编辑距离为d(m,n), 则显然有

d(m,n) = min((str1[m]==str2[n])?d(m-1,n-1):d(m-1,n-1)+1, 
             d(m,n-1)+1,
             d(m-1,n)+1)


其意思是,编辑距离只与三种情况有关。假设将str1转化为str2: 
第一种情况,让str1的前m-1个字符和str2的前n-1个字符进行转化,str1最后一个字符替换成str2最后一个字符。这样(str1[m]==str2[n])?d(m-1,n-1):d(m-1,n-1)+1这一句就好理解了。即两字符串最后一个字符相等的话,就用不着替换,否则就要替换。
第二种情况,将str1转化为str2的前n-1个字符,然后插入str2最后一个字符,变成str2。其编辑步骤数显然是d(m,n-1)+1。
第三种情况,和第二种情况类似,将str1的前m-1个字符转化为str2,然后删除str1最后一个字符。

这三种情况各得到一个编辑步骤数,取其最小值即可。
这样,我们得到一个递归式。其初始条件是

d(0,k)=k, 1<=k<=n
d(k,0)=k, 1<=k<=m

初始条件也是显然的,0个字符转化为任何字符串只有一直插入的份。

因此,我们就可以据此递推式构造一个动态规划过程,假设两个字符串分别为"china"和"unix",则
 
 c h i  n  a
   0 1  2  3  4  5
 u  1  1  2  3 4  5
 n  2  2  2  3  3  4
 i  3  3  3  2  3  4
 x  4  4  4  3  3  4

图中黑色加粗部分是初始值,而红色部分是一条可能的路径。若将"china"变成"unix",则可能的步骤是
c->u, h->n, delete n, a->x

编程实现时,可以直接在一个矩阵中进行。但为节约空间,也可以只用两个数组,每次更新一行。但要注意,较长的字符串要置于水平方向。

#include<iostream>
#include<cstring>
using namespace std;

int min(int x,int y, int z){
    int m = x;
    if(m > y) m = y;
    if(m > z) m = z;
    return m;
}

int stringDistance(const char* str1, const char* str2){
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    const char* longStr, *shortStr;
    int longLen, shortLen;
    if(len1 > len2){
        longStr = str1;
        shortStr = str2;
        longLen = len1;
        shortLen = len2;
    }else{
        longStr = str2;
        shortStr = str1;
        longLen = len2;
        shortLen = len1;
    }
    int *dist1 = new int[longLen+1];
    int *newdist = new int[longLen+1];
    for(int i=1;i<=longLen;i++){
        dist1[i] = i;
    }
    dist1[0] = 0;
    
    for(int j=0;j<=longLen;j++){
        cout << j << " " ;
    }
    cout << endl;
    for(int i=1;i<=shortLen; i++){
        newdist[0] = i;
        cout << i << " ";
        for(int j=1;j<=longLen;j++){
            newdist[j] = min(
                     (longStr[j-1]==shortStr[i-1])?dist1[j-1]:dist1[j-1]+1,
                    newdist[j-1]+1, dist1[j]+1);
            cout << newdist[j] << " ";
        }
        cout << endl;
        memcpy(dist1, newdist, sizeof(int)*(longLen+1));
    }
    int result = dist1[longLen];
    delete [] dist1;
    delete [] newdist;
    return result;
}


int main(int argc, char* argv[]){
    if(argc != 3){
        cout << "USAGE: " << argv[0] << " str1  str2" << endl;
        return 0;
    }
    cout << "Edit Distance is: " << stringDistance(argv[1],argv[2]) << endl;
    return 0;
}


阅读(3807) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~