基础算法：编辑距离

「爱情、让人受尽委屈。」 2022-12-12 15:04 219阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]

编辑距离又称莱文斯坦距离，是俄国数学家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));
        }
    }

结果确认  
![在这里插入图片描述][20201007194144345.png_pic_center]

# 优化 #

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

#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]);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e5fb3c0a15ce4ac5bab9d479c39f5682.png
[20201007194144345.png_pic_center]: /images/20221123/e43a5920fc5240b3976f3515993b04ae.png