一、如何量化两个字符串的相似度？
1、编辑距离（Edit Distance）：
<1>、概念：
编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是0。
<2>、编辑距离计算方式分类：
- 莱文斯坦距离（Levenshtein distance）：允许增加、删除、替换字符这三个编辑操作。 莱文斯坦距离的大小表示两个字符串差异的大小。
-
最长公共子串长度（Longest common substring length）：只允许增加、删除字符这两个编辑操作。最长公共子串长度的大小，表示两个字符串相似程度的大小。字符串mitcmu和mtacnu的编辑距离
2、莱文斯坦距离的编程计算方法：
<1>、回溯：
回溯是一个递归处理的过程。如果a[i]与b[j]匹配，递归考察a[i+1]和b[j+1]。如果a[i]与b[j]不匹配，那么有多种处理方式可选：
- 可以删除a[i]，然后递归考察a[i+1]和b[j]；
- 可以删除b[j]，然后递归考察a[i]和b[j+1]；
- 可以在a[i]前面添加一个跟b[j]相同的字符，然后递归考察a[i]和b[j+1];
- 可以在b[j]前面添加一个跟a[i]相同的字符，然后递归考察a[i+1]和b[j]；
- 可以将a[i]替换成b[j]，或者将b[j]替换成a[i]，然后递归考察a[i+1]和b[j+1]
private char[] a = "mitcmu".toCharArray();
private char[] b = "mtacnu".toCharArray();
private int n = 6;
private int m = 6;
private int minDist = Integer.MAX_VALUE; // 存储结果
// 调用方式 lwstBT(0, 0, 0);
public lwstBT(int i, int j, int edist) {
if (i == n || j == m) {
if (i < n)
edist += (n-i);
if (j < m)
edist += (m - j);
if (edist < minDist)
minDist = edist;
return;
}
if (a[i] == b[j]) { // 两个字符匹配
lwstBT(i+1, j+1, edist);
} else { // 两个字符不匹配
lwstBT(i + 1, j, edist + 1); // 删除a[i]或者b[j]前添加一个字符
lwstBT(i, j + 1, edist + 1); // 删除b[j]或者a[i]前添加一个字符
lwstBT(i + 1, j + 1, edist + 1); // 将a[i]和b[j]替换为相同字符
}
}
<2>、动态规划：
在递归树中，每个节点代表一个状态，状态包含三个变量(i, j, edist)，其中， edist表示处理到a[i]和b[j]时，已经执行的编辑操作的次数。
此时的状态转移方程为：
如果： a[i] != b[j]，那么： min_edist(i, j) = min(min_edist(i - 1,j) + 1, min_edist(i,j - 1) + 1, min_edist(i - 1,j - 1) + 1)
如果： a[i] == b[j]，那么： min_edist(i, j) = min(min_edist(i - 1,j) + 1, min_edist(i,j - 1) + 1， min_edist(i - 1,j - 1))
其中， min表示求三数中的最小值
public int lwstDP(char[] a, int n, char[] b, int m) {
int[][] minDist = new int[n][m];
for (int j = 0; j < m; ++j) { // 初始化第0行:a[0..0]与b[0..j]的编辑距离
if (a[0] == b[j]) minDist[0][j] = j;
else if (j != 0) minDist[0][j] = minDist[0][j-1]+1;
else minDist[0][j] = 1;
}
for (int i = 0; i < n; ++i) { // 初始化第0列:a[0..i]与b[0..0]的编辑距离
if (a[i] == b[0]) minDist[i][0] = i;
else if (i != 0) minDist[i][0] = minDist[i-1][0]+1;
else minDist[i][0] = 1;
}
for (int i = 1; i < n; ++i) { // 按行填表
for (int j = 1; j < m; ++j) {
if (a[i] == b[j]) minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]);
else minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
}
}
return minDist[n-1][m-1];
}
private int min(int x, int y, int z) {
int minv = Integer.MAX_VALUE;
if (x < minv) minv = x;
if (y < minv) minv = y;
if (z < minv) minv = z;
return minv;
}
3、最长公共子串长度的编程计算方法：
<1>、回溯思路：
从a[0]和b[0]开始，依次考察两个字符串中的字符是否匹配。
如果a[i]与b[j]互相匹配，将最大公共子串长度加一，并且继续考察a[i+1]和b[j+1]。
-
如果a[i]与b[j]不匹配，最长公共子串长度不变，这个时候，有两个不同的决策路线：
- 删除a[i]，或者在b[j]前面加上一个字符a[i]，然后继续考察a[i+1]和b[j]；
- 删除b[j]，或者在a[i]前面加上一个字符b[j]，然后继续考察a[i]和b[j+1]
<2>、动态规划：
求a[0…i]和b[0…j]的最长公共长度max_lcs(i, j)，只有可能通过下面三个状态转移过来：
- (i-1, j-1, max_lcs)，其中max_lcs表示a[0…i-1]和b[0…j-1]的最长公共子串长度；
- (i-1, j, max_lcs)，其中max_lcs表示a[0…i-1]和b[0…j]的最长公共子串长度；
- (i, j-1, max_lcs)，其中max_lcs表示a[0…i]和b[0…j-1]的最长公共子串长度。
此时的状态转移方程：
如果： a[i] == b[j]，那么： max_lcs(i, j) = max(max_lcs(i - 1,j - 1) + 1, max_lcs(i - 1, j), max_lcs(i, j - 1))；
如果： a[i] != b[j]，那么： max_lcs(i, j) = max(max_lcs(i - 1,j - 1), max_lcs(i - 1, j), max_lcs(i, j - 1))；
其中max表示求三数中的最大值。
public int lcs(char[] a, int n, char[] b, int m) {
int[][] maxlcs = new int[n][m];
for (int j = 0; j < m; ++j) {//初始化第0行： a[0..0]与b[0..j]的maxlcs
if (a[0] == b[j]) maxlcs[0][j] = 1;
else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
else maxlcs[0][j] = 0;
}
for (int i = 0; i < n; ++i) {//初始化第0列： a[0..i]与b[0..0]的maxlcs
if (a[i] == b[0]) maxlcs[i][0] = 1;
else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
else maxlcs[i][0] = 0;
}
for (int i = 1; i < n; ++i) { // 填表
for (int j = 1; j < m; ++j) {
if (a[i] == b[j]) maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
else maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
}
}
return maxlcs[n-1][m-1];
}
private int max(int x, int y, int z) {
int maxv = Integer.MIN_VALUE;
if (x > maxv) maxv = x;
if (y > maxv) maxv = y;
if (z > maxv) maxv = z;
return maxv;
}
