前言
搜索引擎在用户体验方面的优化还有很多，比如你可能经常会用的拼写纠错功能。
当你在搜索框中，一不小心输错单词时，搜索引擎会非常智能地检测出你的拼写错误，并且 用对应的正确单词来进行搜索。
如何量化两个字符串的相似度？
计算机只认识数字，所以要解答上面的问题，我们就要先来看，如何量化两个字符串之间的相似程度呢？有一个非常著名的量化方法，那就是编辑距离（Edit Distance）。
编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。
- 编辑距离越大，说明两个字符串的相似程度越小；
- 编辑距离越小，说明两个字符串的相似程度越大。
- 两个完全相同的字符串来说，编辑距离就是0。
编辑距离有多种不同的计算方式，比较著名的有莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。
- 莱文斯坦距离：允许增加、删除、替换字符；莱文斯坦距离大小，表示两个字符串差异。
- 最长公共子串长度：允许增加、删除字符；最长公共子串大小，表示两个字符串相似程度的大小。
这里有两个字符串mitcmu和mtacnu，其中莱文斯坦距离是3，最长公共子串长度是4。
如何编程计算莱文斯坦距离？
上面的问题是求把一个字符串变成另一个字符串，需要的最少编辑次数。整个求解过程，涉及多个决策阶段，需要依次考察一个字符串中的每个字符，跟另一个字符串中的字符是否匹配，匹配的话如何处理，不匹配的话又如何处理。所以这个问题符合多阶段决策最优解模型。
第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]。
翻译成代码：
public class Solution {
private char[] a = "mitcmu".ToCharArray ();
private char[] b = "mtacnu".ToCharArray ();
private int n = 6;
private int m = 6;
private int minDist = int.MaxValue;
public int MinDist { get { return minDist; } }
// 调用LwstBT(0, 0, 0);
public void LwstBT (int i, int j, int edist) {
if (i == n || j == m) { // 考察结束，剩余的子串长度要累加到edist
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]时，已经执行的编辑操作的次数。
在递归树中，(i, j)两个变量重复的节点很多，对于相同的节点，只需要保留edist最小的，继续递归处理。所以状态就从(i, j, edist)变成了(i, j, min_edist)。
第3步：找状态转移方式
状态(i, j)可能从(i - 1, j)，(i, j - 1)，(i - 1, j - 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) + 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表示求三数中的最小值。
第4步：根据递推关系填表
第5步：翻译代码
public class Solution2 {
public int LwstDP (char[] a, int n, char[] b, int m) {
int[, ] minEdist = new int[n, m];
for (int j = 0; j < m; j++) { // 初始化第0行
if (a[0] == b[j]) minEdist[0, j] = j;
else if (j != 0) minEdist[0, j] = minEdist[0, j - 1] + 1;
else minEdist[0, j] = 1;
}
for (int i = 0; i < n; i++) { // 初始化第0列
if (a[i] == b[0]) minEdist[i, 0] = i;
else if (i != 0) minEdist[i, 0] = minEdist[i - 1, 0] + 1;
else minEdist[i, 0] = 1;
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
if (a[i] == b[j]) {
minEdist[i, j] = Math.Min (minEdist[i - 1, j] + 1,
Math.Min (minEdist[i, j - 1] + 1, minEdist[i - 1, j - 1])
);
} else {
minEdist[i, j] = Math.Min (minEdist[i - 1, j] + 1,
Math.Min (minEdist[i, j - 1] + 1, minEdist[i - 1, j - 1] + 1)
);
}
}
}
return minEdist[n - 1, m - 1];
}
}
如何编程计算最长公共子串长度？
第1步：回溯算法实现
如果a[i]与b[j]匹配，最大公共子串长度加1，并继续考察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]；
翻译成代码：
public class Solution3 {
private char[] a = "mitcmu".ToCharArray ();
private char[] b = "mtacnu".ToCharArray ();
private int n = 6;
private int m = 6;
private int maxLen = int.MinValue;
public int MaxLen { get { return maxLen; } }
// 调用LcslBT(0, 0, 0);
public void LcslBT (int i, int j, int len) {
if (i == n || j == m) { // 考察结束
if (len > maxLen) maxLen = len;
return;
}
if (a[i] == b[j]) { // 两个字符匹配
LcslBT (i + 1, j + 1, len + 1);
} else { // 两个字符不匹配
LcslBT (i + 1, j, len); // 删除a[i]，或者在b[j]前面加上一个字符a[i]
LcslBT (i, j + 1, len); // 删除b[j]，或者在a[i]前面加上一个字符b[j]
}
}
}
第2步：定义状态&画递归树
在递归树中，每个节点代表一个状态，状态包含三个变量(i, j, len)，其中len表示处理到a[i]和b[j]时，公共子串长度。
在递归树中，(i, j)两个变量重复的节点很多，对于相同的节点，只需要保留len最大的，继续递归处理。所以状态就从(i, j, len)变成了(i, j, max_len)。
第3步：找状态转移方式
状态(i, j)可能从(i - 1, j)，(i, j - 1)，(i - 1, j - 1)三个状态中的任意一个转移过来。
基于上面的分析，用公式把状态转移方程写出来，如下：
- 如果：a[i] != b[j]，那么：max_len(i, j) = max(max_len(i - 1, j), max_len(i, j - 1), max_len(i - 1, j - 1))
- 如果：a[i] == b[j]，那么：max_len(i, j) = max(max_len(i - 1, j), max_len(i, j - 1), max_len(i - 1, j - 1) + 1)
- 其中，max表示求三数中的最大值。
第4步：根据递推关系填表
手画，暂无。
第5步：翻译代码
public class Solution4 {
public int LcslDP (char[] a, int n, char[] b, int m) {
int[, ] maxLen = new int[n, m];
for (int j = 0; j < m; ++j) { // 初始化第0行
if (a[0] == b[j]) maxLen[0, j] = 1;
else if (j != 0) maxLen[0, j] = maxLen[0, j - 1];
else maxLen[0, j] = 0;
}
for (int i = 0; i < n; ++i) { // 初始化第0列
if (a[i] == b[0]) maxLen[i, 0] = 1;
else if (i != 0) maxLen[i, 0] = maxLen[i - 1, 0];
else maxLen[i, 0] = 0;
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
if (a[i] == b[j]) maxLen[i, j] = Math.Max (Math.Max (maxLen[i - 1, j], maxLen[i, j - 1]), maxLen[i - 1, j - 1] + 1);
else maxLen[i, j] = Math.Max (Math.Max (maxLen[i - 1, j], maxLen[i, j - 1]), maxLen[i - 1, j - 1]);
}
}
return maxLen[n - 1, m - 1];
}
}
解答开篇
当用词在搜索框内，输入一个拼写错误的单词时，我们就拿这个单词跟词库中的单词一一进行比较，计算编辑距离，将编辑距离最小的单词，作为纠正之后的单词，提示给用词。
这是拼写纠正最基本的原理。