一、什么是最小编辑距离
通过三种基本的字符操作（插入、删除、替换）将一个字符串s变为另一个字符串t所需要的最少操作次数称为字符串s和t的最小编辑距离。例如this和his的最小编辑距离为1。
由于字符替换可以分解为插入和删除两步，所以又有一些人将最小编辑距离定义为将一个字符串s变为另一个字符串t所需要的最小代价。插入、删除、替换的代价分别是1、1、2。字符替换操作的时候，如果字符从c1和字符c2相同，则将c1替换为c2的代价为0，否则为2。本文给出的最小编辑距离以代价来计算。
二、算法原理
懒得画电脑图，以手工图扫描文件来代替，将就着看吧。
三、环境
Win7中文旗舰版64位 + Python 3.64 64位 + MinGW GCC4.5.2
四、C代码
#include <stdio.h>
#include <string.h>
#define M 100
#define N 100
#define CHAR_LEN_MAX 5
#define INS_COST 1
#define DEL_COST 1
#define SUB_COST 2
char ss[M][CHAR_LEN_MAX], tt[N][CHAR_LEN_MAX];
int getWordsFromSentence(char sen[], char chars[][CHAR_LEN_MAX])
{
int count = 0;
char *p = sen;
char *q = chars[count];
q[0] = '\0';
while (*p)
{
if (*p>0)
{
q[0] = *p;
q[1] = '\0';
}
else
{
q[0] = *p;
q[1] = *(p+1);
q[2] = '\0';
p++;
}
if (*p)
p++;
q = chars[++count];
q[0] = '\0';
}
return count;
}
int main()
{
/* 定义变量 */
int d[N+1][M+1];
char s[M], t[N];
int i, j;
int x, y, z, min;
int m = M+1, n = N + 1;
/* 输入源字符串和目标字符串并求它们的长度 */
do
{
if (m>M || m<1)
{
printf("请输入源字符串(非空字符串，长度不能超过%d个字节，一个汉字算两个字节)：", M);
gets(s);
m = strlen(s);
}
if (n>N || n<1)
{
printf("请输入目标字符串(非空字符串，长度不能超过%d个字节，一个汉字算两个字节)：", N);
gets(t);
n = strlen(t);
}
}
while (m>M || n>N || m<1 || n<1);
/* 将源字符串和目标字符串分解成一个个的字符，存入相应的二维字符数组 */
m = getWordsFromSentence(s, ss);
n = getWordsFromSentence(t, tt);
printf("\ns：");
for (i=0; i<m; i++)
printf("%s ", ss[i]);
printf("\nt：");
for (i=0; i<n; i++)
printf("%s ", tt[i]);
/* 最小距离矩阵赋初值 */
d[0][0] = 0;
for (i=1; i<=m; i++)
d[0][i] = d[0][i-1] + DEL_COST;
for (i=1; i<=n; i++)
d[i][0] = d[i-1][0] + INS_COST;
/* 计算最小距离矩阵的其它元素值 */
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
x = d[i-1][j] + INS_COST;
if (strcmp(tt[i-1],ss[j-1])==0)
y = d[i-1][j-1];
else
y = d[i-1][j-1] + SUB_COST;
z = d[i][j-1] + DEL_COST;
min = (x<y)?x:y;
min = (min<z)?min:z;
d[i][j] = min;
}
}
printf("\n\n最小编辑距离矩阵\n");
for (j=m; j>=0; j--)
{
for (i=0; i<=n; i++)
printf("%5d", d[i][j]);
printf("\n");
}
printf("\n\n源串：%s\n目标串：%s\n最小编辑距离：%d\n", s, t, d[n][m]);
return 0;
}
五、Python代码
六、比较
C代码只给出了最小编辑距离的一种非递归实现，Python代码给出了递归和非递归两种实现方法。经过对同一个字符串对（"intention"和"execution"）求最小编辑距离200次发现：
递归法用时：270.928724 秒
非递归法用时：0.015600 秒
可以看出，递归算法的速速远远比不上非递归算法。
七、结论
虽然递归算法在理解算法方面有优势，但是在运行速度方面实在是不敢恭维，因此，对于一些具体应用，如果能用非递归算法实现就不要用递归算法来实现。
