41动态规划实战：如何实现搜索引擎中的拼写纠错功能

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

对于搜索引擎，除了利用 Trie 树实现搜索引擎的关键词提示功能外，还经常用到拼写纠错功能。如下图所示，那这个功能是如何实现的呢？

如何量化两个字符串的相似度？

计算机只认识数字，那么如何量化两个字符串之间的相似程度呢？这需要用到著名的量化方法——编辑距离（Edit Distance）。它指的是将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；对于两个完全相同的字符串来说，编辑距离就是 0。

根据所包含的编辑操作种类的不同，编辑距离有多种不同的计算方式，比较著名的有莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。而且，莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。

如下所示，两个字符串 mitcmu 和 mtacnu 的莱文斯坦距离是 3，最长公共子串长度是 4。看下面左图，一共使用了三个操作，删除 i 、a，替换了 n，所以莱文斯坦距离是 3。而下面右图，经过操作后，最长公共子串长度为4。

如何编程计算莱文斯坦距离？

这个问题是求把一个字符串变成另一个字符串，需要的最少编辑次数。整个决策过程，涉及多个决策阶段，需要依次考察一个字符串中的每个字符，跟另一个字符串中的字符是否匹配，匹配的话如何处理，不匹配的话又如何处理。所以，这个问题符合多阶段决策最优解模型。

之前说过，贪心、回溯、动态规划可以解决的问题，都可以抽象成这样一个模型。我们先用最简单的回溯算法看如何解决这个问题。

回溯是一个递归处理的过程。如果 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) {
    // 当一个遍历完毕，而另一个没有遍历完时，需要删除多余字符串中所有字符，所以就有了 edist 的计算方法
    if (i < n) edist += (n - i);
    if (j < m) edist += (m - j);
    // 如果两个字符串更新完了，则看是否要更新 minDist
    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]替换为相同字符，从下一个字符开始匹配
  }
}

根据回溯算法的实现画出递归树，看是否存在重复子问题。如果存在重复子问题，就可以考虑能否用动态规划来解决；如果不存在重复子问题，那回溯就是最好的解决方法。

在递归树中，每个节点代表一个状态，状态包含三个变量 (i, j, edist)，其中，edist 表示处理到 a[i]和 b[j]时，已经执行的编辑操作的次数。

在递归树中，(i, j) 变量重复的节点很多，(3, 2, 1) 和 (3, 2, 2) 。对于 (i, j) 相同的节点，只需要保留 edist 最小的，继续递归处理就可以了，剩下的节点都可以舍弃。

在上一节讲的矩阵最短路径问题中，到达状态 (i, j) 只能通过 (i-1, j) 或 (i, j-1) 两个状态转移过来，而本节这个问题，状态 (i, j) 可能从 (i-1, j)，(i, j-1)，(i-1, j-1) 三个状态中的任意一个转移过来。

注意上图中前面两种情况 (i-1, j) 想要达到 (i, j) ，必须是 +(1, 0, 1)；同样的，从 (i, j-1) 到达 (i, j)，必须是 +(0, 1, 1)；而(i-1, j-1) 到达 (i, j) 可以是 +(1, 1, 1) 或者+(1, 1, 0)。

将这个状态转移过程使用公式写出来，就是我们前面讲的状态转移方程。下面分为两种情况讨论，主要是上图中最后一种情况有两种途径。

如果：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;
}

对于这种复杂的问题，经常会感觉到无从下手，这是经常的，这里有一些小经验和小技巧来分享。

当我们拿到一个问题的时候，可以先不思考，计算机会如何实现这个问题，而是单纯考虑“人脑”会如何去解决这个问题。人脑比较倾向于思考具象化的、摸得着看得见的东西，不适合思考过于抽象的问题。所以，我们需要把抽象问题具象化。具体而言，可以实例化几个测试数据，通过人脑去分析具体实例的解，然后总结规律，再尝试套用学过的算法，看是否能够解决。

如何编程计算最长公共子串长度？

这个问题解决思路，跟莱文斯坦距离的解决思路非常相似，也可以用动态规划解决。首先定义状态，每个状态还是包含三个变量 (i, j, max_lcs)，max_lcs 表示 a[0…i]和 b[0…j]的最长公共子串长度。接着看 (i, j) 这个状态可以由哪些状态转移过来？

同样的，先来看回溯的解决思路。从 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]。

反过来说，如果要求 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]的最长公共子串长度。

把这个转移过程，使用状态转移方程写出来，如下所示。其中，(i-1, j) 要想变到 (i, j)，那么肯定存在 a[i-1] != b[j] ，此时 max_lcs(i-1, j) 不需要加 1 即可得到 max_lcs(i, j)；同理可以推断从 (i, j-1) 到 (i, j)。而从 (i-1, j-1) 到 (i, j) 需要根据 a[i] 与 b[j] 是否相等分情况讨论。

如果：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;
}

解答开篇

当用户在搜索框中，输入一个拼写错误的单词时，就拿这个单词跟词库中的单词一一进行比较，计算编辑距离，将编辑距离最小的单词，作为纠正之后的单词，提示给用户。

不过，一方面，单纯利用编辑距离来纠错，效果并不一定好；另一方面，词库中的数据量可能很大，搜索引擎每天要支持海量的搜索，所以对纠错的性能要求很高。

针对纠错效果不好的问题，有如下几种参考的优化思路：

• 不仅仅取出编辑距离最小的那个单词，而是取出编辑距离最小的 TOP 10，然后根据其他参数（如搜索热度），决策选择哪个单词作为拼写纠错单词；
• 综合多种编辑距离计算方法；
• 通过统计用户的搜索日志，得到最常被拼错的单词列表，以及对应的拼写正确的单词。搜索引擎在拼写纠错的时候，首先在这个最常被拼错单词列表中查找；
• 还可以引入个性化因素。针对每个用户，维护这个用户特有的搜索喜好，也就是常用的搜索关键词。当用户输入错误的单词的时候，首先在这个用户常用的搜索关键词中，计算编辑距离，查找编辑距离最小的单词。

对于纠错性能方面，作者说到了两种分治的优化思路：

• 如果纠错功能的 TPS 不高（服务器每秒处理的事务数），则可以部署多台机器，每台机器运行一个独立的纠错功能。当有一个纠错请求时，通过负载均衡，分配到其中一台机器，来计算编辑距离，得到纠错单词。
• 如果纠错系统的响应时间太长，也就是，每个纠错请求处理时间过长，我们可以将纠错的词库，分割到很多台机器。当有一个纠错请求时，就将这个拼写错误的单词，同时发送到这多台机器，让多台机器并行处理，分别得到编辑距离最小的单词，然后再比对合并，最终决定出一个最优的纠错单词。

内容小结

动态规划的理论尽管并不复杂，总结起来就是“一个模型三个特征”，但是要想灵活应用并不简单，一定要多加练习。这三节课，加上课后思考题，共有8个动态规划问题，它们都很经典，很多动态规划问题其实都可以抽象成这几个问题模型，所以，你一定要多看几遍，多思考一下，争取真正搞懂它们。

课后思考

假设有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。

答：参考代码

public int longestIncreaseSubArrayDP(int[] array) {
    if (array.length < 2) return array.length;
    int[] state = new int[array.length];
    state[0] = 1;
    for (int i = 1; i < state.length; i++) {
        int max = 0;
        for (int j = 0; j < i; j++) {
            if (array[j] < array[i]) {
                if (state[j] > max) max = state[j];
            }
        }
        state[i] = max + 1;
    }
    int result = 0;
    for (int i = 0; i < state.length; i++) {
        if (state[i] > result) result = state[i];
    }
    return result;
}