字符串相似度算法 递归与动态规划求解分析

不点 阅读:360 2020-10-19 15:34:58 评论:0

1.概念

  编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括:(1)将一个字符替换成另一个字符,(2)插入一个字符,(3)删除一个字符。

  相似度等于“编辑距离+1”的倒数。

2.分析

  设有字符串a[0...n],b[0...m]。

  (1)当a[i]=b[j]时,说明这时候不需要编辑操作。编辑距离保持,即f(i,j)=f(i-1,j-1)

  (2)当a[i]!=b[j]时,可以有三种编辑操作。

  其中删除和插入操作,只对一个下标i或者j产生影响。如在下图中,当前匹配到(t1,t2)处,如果采用删除'g',只改变t1的下标。

  

   其中替换操作,会对2个下标都产生影响。如在下图中,当前匹配到(t1,t2)处,如果将'g'替换成'm',则下次就需要执行(t1+1,t2+1)处。

     

   所以可以推导出下面就是递推公式。

  

3.用递归求解代码

#include<stdio.h> 
#include<string.h> 
char *a="abcgh"; 
char *b="aecdgh"; 
int min(int t1,int t2,int t3)   ///求三个数的最小值 
{ 
    int min; 
    min=t1<t2?t1:t2; 
    min=min<t3?min:t3; 
    return min; 
} 
int calculate(int i,int enda,int j,int endb) 
{ 
    int t1,t2,t3; 
    if(i>enda)  ///i指示超过a[]的范围时 
    { 
        if(j>endb) 
            return 0; 
        else 
            return endb-j+1; 
    } 
    if(j>endb)  ///j指示超过b[]的范围时 
    { 
        if(i>enda) 
            return 0; 
        else 
            return enda-i+1; 
    } 
    if(*(a+i) == *(b+j))    ///如果两个相等,则直接求下一个位置 
        return calculate(i+1,enda,j+1,endb); 
    else 
    { 
        t1=calculate(i+1,enda,j,endb);  ///删除a[i]或在b中插入a[i] 
        t2=calculate(i,enda,j+1,endb);  ///删除b[j]或在a中插入b[j] 
        t3=calculate(i+1,enda,j+1,endb);    ///替换 
        return 1+min(t1,t2,t3); 
    } 
} 
int main() 
{ 
    int dis=calculate(0,strlen(a)-1,0,strlen(b)-1); 
    printf("dis=%d",dis); 
    return 1; 
}

 4.用动态规划求解代码

 

#include<stdio.h> 
#include<string.h> 
#define MAX 1000 
int dp[MAX][MAX];   ///dp[i][j]表示当前a[0..i-1]与b[0..j-1]的编辑距离 
char *a="agbgd"; 
char *b="ggd"; 
 
int min(int t1,int t2,int t3)   ///求三个数的最小值 
{ 
    int min; 
    min=t1<t2?t1:t2; 
    min=min<t3?min:t3; 
    return min; 
} 
 
int main() 
{ 
    int i,j; 
    int lena=strlen(a),lenb=strlen(b); 
    memset(dp,0,sizeof(dp)); 
    for(i=0;i<=lena;i++)   ///a作为行,当b为空串时 
        dp[0][i]=i; 
    for(i=0;i<=lenb;i++)   ///b作为列,当a为空串时 
        dp[i][0]=i; 
 
    for(i=1;i<=lena;i++) 
    { 
        for(j=1;j<=lenb;j++) 
        { 
            if(*(a+i)==*(b+j))  ///相等时 
                dp[i][j]=dp[i-1][j-1]; 
            else 
                dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]); ///不相等时,取三种可能操作的最小数值+1 
        } 
    } 
    printf("编辑距离为:dis=%d\n",dp[lena][lenb]); 
    return ; 
}
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号