字元串相似度算法(編輯距離)

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 ;
}