编辑距离问题
一、问题描述
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符。
将字符串A变换为字符串B 所用的最少字符操作次数也称为字符串A到B 的编辑距离，记为 d(A,B)。 试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。
算法设计：对于给定的字符串A和字符串B，计算距离d(A,B)。
数据输入：input.txt提供输入数据，第一行输入字符串A，第二行输入数据串B。输出结构，将d(A,B)的结果输入output.txt。
备注：题目来源——计算机算法设计与分析
二、原理分析
假设序列S和T的长度分别为m和n, 两者的编辑距离表示为edit[m][n]. 则对序列进行操作时存在以下几种情况:
A、当S和T的末尾字符相等时, 对末尾字符不需要进行上述定义操作中(亦即"编辑")的任何一个, 也就是不需要增加计数. 则满足条件: edit[m][n] = edit[m - 1][n - 1].
B、当S和T的末尾字符不相等时, 则需要对两者之一的末尾进行编辑, 相应的计数会增加1.
b1、对S或T的末尾进行修改, 以使之与T或S相等, 则此时edit[m][n] = edit[m - 1][n - 1] + 1;
b2、删除S末尾的元素, 使S与T相等, 则此时edit[m][n] = edit[m - 1][n] + 1;
b3、删除T末尾的元素, 使T与S相等, 则此时edit[m][n] = edit[m][n - 1] + 1;
b4、在S的末尾添加T的尾元素, 使S和T相等, 则此时S的长度变为m+1, 但是此时S和T的末尾元素已经相等, 只需要比较S的前m个元素与T的前n-1个元素, 所以满足edit[m][n] = edit[m][n - 1] + 1;
b5、在T的末尾添加S的尾元素, 使T和S相等, 此时的情况跟b4相同, 满足edit[m][n] = edit[m - 1][n] + 1;
C、比较特殊的情况是, 当S为空时, edit[0][n] = n; 而当T为空时, edit[m][0] = m; 这个很好理解, 例如对于序列""和"abc", 则两者的最少操作为3, 即序列""进行3次插入操作, 或者序列"abc"进行3次删除操作.
所以, 以上我们不难推出编辑距离的动态规划方程为:
具体分析过程：
由编辑距离的动态规划方程我们可以看出, edit[m][n]可以由edit[m - 1][n - 1], edit[m - 1][n], edit[m][n - 1]得出, 而如果edit是一个二维数组的话, edit[m][n]可以由它的上, 左, 左上三个位置的元素通过条件判断得出. 亦即我们可以通过遍历二维数组, 然后通过回溯来计算当前值。
1、例如对于字符串S = "sailn"和T = "failing", 对二维数组进行初始化为:
2、因为S[0] = s, T[0] = f, 则S[0] != T[0], 则对应于上述二维矩阵, edit[1][1] = min(edit[0][0], edit[0][1], edit[1][0]) + 1即edit[1][1] = min(0, 1, 1) + 1即edit[1][1] = 0 + 1 = 1.
3、而对于S[1] = a, T[1] = a, S[1] = T[1], 则对应于二维矩阵, edit[2][2] = edit[1][1], 所以edit[2][2] = 1. 所以按照这种规则, 将上述二维矩阵填满则如下:
4、所以, 两者的编辑距离为edit[m][n] = edit[5][7] = 3.
三、实现代码
#include <iostream>
#include <algorithm>// 调用min函数
#include <memory.h>
#include <cstdio>
#include <string>
using namespace std;
int num[1000][1000];
char str1[1000], str2[1000];
int min_three(int a, int b, int c) // 输出三个值中最小的值
{
int temp = min(a, b);
return min(temp, c);
}
int dist_edit(string str1, string str2)
{
int i, j;
int len1 = str1.length(), len2 = str2.length();
for (i = 0; i < len1+1; i++)//对矩阵行列进行初始化
{
num[i][0] = i;
}
for (i = 0; i < len2+1; i++)
{
num[0][i] = i;
}
for (i = 1; i < len1+1; i++) {
for (j = 1; j < len2+1; j++) {
if (str1[i-1] == str2[j-1]) {
num[i][j] = num[i - 1][j - 1];
}
else {
num[i][j]=min_three(num[i][j - 1], num[i - 1][j - 1], num[i - 1][j]) + 1;
}
}
}
int return_value = num[len1 - 1][len2 - 1];
return return_value;
}
int main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> str1 >> str2;
cout << dist_edit(str1, str2) << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
四、补充
本质是利用一个表，逐个对比，然后计算移位，得到最小操作数，明白实现原理之后，再变成实现，相对较为简单！
重点是怎么用表去记性对比！
num[i][j]=min_three(num[i][j - 1], num[i - 1][j - 1], num[i - 1][j]) + 1;
参考链接——https://www.cnblogs.com/littlepanpc/p/7895810.html
