编辑距离又称莱文斯坦距离，是俄国数学家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]); } } 淼叔 认证博客专家 神经网络 TensorFlow NLP 资深架构师，PMP、OCP、CSM、HPE University讲师，EXIN DevOps Professional与DevOps Master认证讲师，曾担任HPE GD China DevOps & Agile Leader，帮助企业级客户提供DevOps咨询培训以及实施指导。熟悉通信和金融领域，有超过十年金融外汇行业的架构设计、开发、维护经验，在十几年的IT从业生涯中拥有了软件开发设计领域接近全生命周期的经验和知识积累，著有企业级DevOps技术与工具实战。