基础算法：编辑距离

编辑距离又称莱文斯坦距离，是俄国数学家Vladimir Levenshtein在1965年所提出的概念，主要用来判断对于两个字符串的差异化的量化，确认需要多少次处理才能将一个字符串变为另外一个，处理一般分为添加、删除和替换三种。

常见的使用场景

编辑距离在自然语言处理中国可以用于拼写检查，也可以用于DNA之间生物信息之间类似程度的判断，而unix下的diff等命令也是利用编辑距离算法进行文本编辑对比。

示例代码

这里使用最简单的C语言方式进行模拟，效率虽然很低，递归写法是最简洁的，只需要如下即可实现简单的编辑距离的计算：

#include <stdio.h>
#include <string.h>

#define MAX_STRING_LENGTH 100

int min(int a, int b, int c) {
   
    int min = a > b ? b : a;
    return min > c ? c : min;
}

int distance(char* src, char* dst, int src_cnt, int dst_cnt) {
   
    if (src_cnt == -1) return dst_cnt + 1;
    if (dst_cnt == -1) return src_cnt + 1;

    if(src[src_cnt] == dst[dst_cnt]) {
   
        return distance(src, dst, src_cnt-1, dst_cnt-1);
    } else {
   
        return min(distance(src, dst, src_cnt-1, dst_cnt) + 1,
                   distance(src, dst, src_cnt, dst_cnt-1) + 1,
                   distance(src, dst, src_cnt-1, dst_cnt-1) + 1);
    }
}

int main(void) {
   
    char src[MAX_STRING_LENGTH] = {
    0 };
    char dst[MAX_STRING_LENGTH] = {
    0 };
    int  src_cnt = 0, dst_cnt = 0;

    while(scanf("%s",src) != EOF) {
   
        scanf("%s",dst);

        src_cnt = strlen(src);
        dst_cnt = strlen(dst);
        printf("%d\n",distance(src, dst, src_cnt, dst_cnt));
    }
}

结果确认

优化

上述代码理解起来清楚地多，而且也较为简洁，但是由于存在重复路径问题，整体时间复杂度较高，一般较难满足需求，所以这时一般需要使用动态规划表进行优化，比如本文可以使用如下方式进行优化（请注意此处仅为示例，大小和边界请自行确认）

#include <stdio.h>
#include <string.h>

#define MAX_STRING_LENGTH 100
#define DP_ARRAY_SIZE     100
int dp[DP_ARRAY_SIZE][DP_ARRAY_SIZE] = {
    0 };

int min(int a, int b, int c) {
   
    int min = a > b ? b : a;
    return min > c ? c : min;
}

void set_dp(char* src, char* dst, int src_cnt, int dst_cnt) {
   
    for ( int i=0; i<=src_cnt; i++) dp[i][0] = i;
    for ( int i=0; i<=dst_cnt; i++) dp[0][i] = i;

    for (int i=1; i<=src_cnt; i++) {
   
        for ( int j=1; j<=dst_cnt; j++) {
   
            if(src[i-1] == dst[j-1]) {
   
                dp[i][j] = dp[i-1][j-1];
            } else {
   
                dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1);
            }
        }
    }
}

void clear_dp() {
   
    for (int i=0; i<DP_ARRAY_SIZE; i++) {
   
        for (int j=0; j<DP_ARRAY_SIZE; j++) {
   
            dp[i][j] = 0;
        }
    }
}


int main(void) {
   
    char src[MAX_STRING_LENGTH] = {
    0 };
    char dst[MAX_STRING_LENGTH] = {
    0 };
    int  src_cnt = 0, dst_cnt = 0;

    while(scanf("%s",src) != EOF) {
   
        scanf("%s",dst);

        src_cnt = strlen(src);
        dst_cnt = strlen(dst);
        clear_dp();
        set_dp(src, dst, src_cnt, dst_cnt);
        printf("%d\n",dp[src_cnt][dst_cnt]);
    }
}