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

精选留言(106)

• 

  ext4

  Trie树和编辑距离，很多年前我去Google面试的时候都被考过。还记得Trie树是问我怎么存储美国的10位电话号码，可以最快速查找一个号码是否是空号，我答上来了；不过关于编辑距离我当时没想出来用dp。

  2019-01-02

  

   62
• 

  zixuan

  补充一下，中文纠错很多时候是通过拼音进行的，比如 "刘得花"->"liudehua"->"刘德华". 拼音检索方法也有很多，比如可以把热门词汇的拼音字母组织成Trie树，每个热词的结尾汉字的最后一个拼音字母就是叶子，整体性能就是O(n)的，n为query的拼音总长度. 除了拼音外也有根据字形（二维文字版的编辑距离？）甚至语义等做的纠错策略。
  传统搜索引擎中的查询词智能提示、纠错、同义词、近义词、同好词、相关搜索、知识图谱等系列功能统称为用户的意图识别模块。

  作者回复: 👍好厉害

  2019-01-03

  

   42
• 

  王超

  老师，能帮忙解释下这个公式吗，有一点费解， a[i]==b[j] 时，为什么是：
  min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1)) 而不是
  min(min_edist(i-1,j), min_edist(i,j-1)，min_edist(i-1,j-1))
  为什么要 + 1 啊
  

  2019-01-25

   9

   19
• 

  blacknhole

  有个疑问：
  以下内容涉及“如何编程计算莱文斯坦距离？”一节。
  
  （1）文中对递归树中的状态三元组(i, j, edist)的解释是，“状态包含三个变量 (i, j, edist)，其中，edist表示处理到 a[i] 和 b[j] 时，已经执行的编辑操作的次数。”这里的“处理到a[i]和b[j]时”，其实是在说将要处理但还并未处理a[i]和b[j]。edist并不包括对a[i]和[j]的编辑操作。递归树图片后紧接着的图片中，(i, j, min_edist)的min_edist也并不包括对a[i]和[j]的编辑操作。
  
  （2）而二维状态表图片中每格的值和动态规划的实现代码中minDist[i][j]两者均代表：到处理完a[i]和b[j]之后为止，已经执行的编辑操作的最少次数。根据这个意思，可知状态转移方程中的min_edist(i, j)也是包括对a[i]和[j]的编辑操作的。如果按照（1）中的意思，状态转移方程中的min_edist(i, j)就不应该包括对a[i]和[j]的编辑操作，也不应该判断a[i]和b[j]是否相等，而应该判断的是a[i - 1]和b[j - 1]是否相等；并且动态规划的实现代码中循环终止条件就不应是小于n或m，而应是小于等于n或m。
  
  为什么会有（1）与（2）这样的在文章前后表达上的不一致？

  作者回复: 👍你说的没错 不仅这一节 前面两节课都是这样。递归树是根据回溯算法代码实现写的。但是动规代码用你讲到的另一种思路理解更容易。我当时写的时候 也想能不能统一。最后发现不好统一。你可以分割开来看 或者 把它们当作两种状态表示方法来看 不影响理解

  2019-01-02

   3

   17
• 

  G.S.K

  动态规划问题的思路总结：第一步：如果待解决的问题为func（n），自己可以假设func（n-1）、func（n-2）……func（1）都已经解出，然后就是如何利用这些结果来推导出func（n），经过这么分析就可以得出推导方程。第二步：设计dp数组来保存func（n）（一维数组、二维数组等）。第三步：从0开始遍历，按照状态转移方程计算出func（n）保存到dp数组
  举例，以下这些leetcode动态规划相关的题都可以直接套用这个解题思路
  
  一维dp数组的题目
  322. Coin Change
  121. Best Time to Buy and Sell Stock
  53. Maximum Subarray
  300. Longest Increasing Subsequence
  152. Maximum Product Subarray
  
  二维dp数组的题目
  152. Maximum Product Subarray
  120. Triangle

  2019-03-22

   1

   13
• 

  Jack_Cui

  老师 最长公共子串要求的是连续的 对于编辑距离应该是最长公关子序列吧

  2019-01-17

  

   13
• 

  Sharry

  思考题的解法还是很精妙的
  递推公式:
  a[0...i] 的最长子序列为: a[i] 之前所有比它小的元素中子序列长度最大的 + 1
  
  代码实现:
  ```
  #include<iostream>
  
  using namespace std;
  
  // 动态规划求 a 的最上升长子序列长度
  #include<iostream>
  
  using namespace std;
  
  // 动态规划求 a 的最上升长子序列长度
  int longestSubsequence(int *a, int n) {
  // 创建一个数组, 索引 i 对应考察元素的下标, 存储 arr[0...i] 的最长上升子序列大小
  int *lss_lengths = new int[n];
  // 第一个元素哨兵处理
  lss_lengths[0] = 1;
  // 动态规划求解最长子序列
  int i, j, max;
  for (i = 1; i < n; i++) {
  // 计算 arr[0...i] 的最长上升子序列
  // 递推公式: lss_lengths[i] = max(condition: j < i && a[j] < a[i] value: lss_lengths[j] + 1)
  max = 1;
  for (j = 0; j < i; j++) {
  if (a[i] > a[j] && lss_lengths[j] >= max) {
  max = lss_lengths[j] + 1;
  }
  }
  lss_lengths[i] = max;
  }
  int lss_length = lss_lengths[n - 1];
  delete[]lss_lengths;
  return lss_length;
  }
  
  void main() {
  const int n = 7;
  int arr[n] = { 2, 9, 3, 6, 5, 1, 7 };;
  cout << longestSubsequence(arr, n) << endl;
  getchar();
  }

  2019-01-03

   1

   11
• 

  G.S.K

  第二遍学习，看留言有同学不理解状态转移表的填充过程，现总结一下状态转移表的填充详细过程和对应的字符编辑操作，望老师指正：
  1 minDist[i][j]表示处理完a[i]和b[j]时（a[0...i]已全部转换到b[0...j]），需要的最小编辑次数
  2 a[i]和b[j]不相等时，状态转移公式为：minDist[i][j]=min(minDist(i-1,j)+1, minDist(i,j-1)+1，minDist(i-1,j-1))
     1) 如果minDist[i][j]=minDist(i-1,j)+1，现分析一下这个状态转移的具体过程。minDist(i-1,j)表示a[0...i-1]已全部转换到b[0...j]，如何编辑字符才能从minDist(i-1,j)到达minDist[i][j]这个状态呢？要么将a[i]这个字符删除，要么在b[j]后边添加一个跟a[i]相同的字符（这里编辑的操作跟老师讲的回溯法的操作是不一样的）
     2）如果minDist[i][j]=minDist(i-1,j-1)，现分析一下这个状态转移的具体过程。如何编辑字符才能从minDist(i-1,j-1)到达minDist[i][j]这个状态呢？？将a[i]替换为b[j]或者将b[j]替换为a[i]即可
    3) 如果minDist[i][j]=minDist(i,j-1)+1，跟上边第一种情况类似
  3 a[i]和b[j]相等时比较简单，不需要做字符的编辑

  2019-03-24

   3

   10
• 

  郭霖

  思考题java版解答：
  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;
  }

  2019-01-08

   2

   9
• 

  沉睡的木木夕

  那个状态转移表是怎么填充的？我来回看了几遍还是不知道里面的值怎么来的，感觉跟前面分析的扯不上任何关系

  2019-01-22

   1

   7
• 

  王者归来

  老师，第一行初始化值，如何理解？
  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;

  2019-01-31

   1

   6
• 

  G.S.K

  莱温斯坦距离状态表，初始化第0行和第0列代码逻辑有点复杂，可以简化一下，修改状态表为如下形式
  ∅ m t a c n u
  ∅ 0 1 2 3 4 5 6
  m 1 0 1 2 3 4 5
  i 2 1
  t 3 2
  c 4 3
  m 5 4
  u 6 5
  代码就可以简化了
  int[][] minDist = new int[n+1][m+1]
    for (int j = 0; j <= m; ++j) { 初始化第0行
      minDist[0][j] = j;
    }
    for (int i = 0; i <= n; ++i) { 初始化第0列
      minDist[i][0] = i;
    }
  最终return minDist[n][m];

  2019-03-24

   3

   5
• 

  Kudo

  思考题解答：
  状态转移公式：maxLen[i] = max(maxLen[j]+(1 if j<i else 0)) for any j < i
  python代码：
  def maxOrderedSeq(seq):
      maxLen = [1] * len(seq) # 初始化为1
      
      for i in range(1, len(seq)): # i从1开始
          for j in range(i-1,-1,-1): # j从i-1到0
              if seq[j] <= seq[i]:
                  maxLen[i] = maxLen[j] + 1
                  break # 满足则退出
          if maxLen[i] == 1: # 比前面所有元素小
              maxLen[i] = maxLen[i-1]
              
      print(maxLen)
              
  # usage
  seq = [2, 9, 3, 6, 5, 1, 7]
  maxOrderedSeq(seq)

  2019-01-03

   1

   5
• 

  saber

  老师我有个疑问（急），希望老师能够帮忙回答下，这也是大部分留言中没能解决的疑问。
  在莱文斯坦距离讲解时，那里的状态方程是怎么直接写出来的？这一点是我最不能理解的，当然在问该问题之前，我已经尽我所能的尝试理解老师的文章，并且把留言也都翻了一遍。老师请看我下面的陈述：
  
  一：按照老师文章的讲解顺序，先分析了如何用回溯方法，然后绘制了递归树，从递归树中又分析出了具有重复的子结构，接着又画出了状态简图（递归树下面的图，不知道怎么表达），从这幅简图中清晰的看出来状态的转移方式，接下来重点来了！！！文章接着就写出来状态转移方程（不理解的地方）！我在留言中发现，老师对这点的解释是说「状态转移方程与递归树无关，递归树仅仅表达了问题具有重复子结构」，如果按照老师的说法，不根据递归树分析出状态转移过程，那该怎么直接写出状态转移方程（要能够合理的推断出来，而不是靠经验，否则还是无法掌握动态规划）？目前来看，我在文章中没有发现具有这样的逻辑推断。我之前的理解是说，我们其实可以在递归树中分析出状态转移方程如何写，然后这样就形成了一个闭环，由回溯->递归树->状态转移方程。希望在这里老师能够给出一个合理的解释？
  
  二：抛开上面的一些问题，咱们单独看莱问斯坦距离状态转移公式，先假设，按照递归树和递归树下面的图可以知道状态转移的过程（这是一个前提假设）。在留言中的第 4 条「blacknhole」这位同学的留言中，我也有相同的疑问，(i , j, min_edist) 到底表达的是什么状态？（处理完 a[i] b[j] 后的最小距离？ or 刚要处理 a[i] b[j] 时对应的最小距离？），
  
  接下来按照二种不同的表达来看看状态方程如何推断出来：
  
  1、 如果表达的含义是 「处理完 a[i] b[j] 后的最小距离」
  
  那么其实从回溯算法中可以知道（因为 i j 的前一个状态已经处理完了，比如 min_edist(i-1,j) 就代表了前一个状态。）
  
  if (a[i] != b[j])
  
  ​ min_edist(i, j) =1+ min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1))
  
  if (a[i] == b[j] )
  
  ​ min_edist(i, j) = min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1))
  
  2、如果表达的含义是「刚要处理 a[i] b[j] 时对应的最小距离」
  
  那么我们可以这么想，当前 i,j min_edist 表示还没有处理过 i,j 时对应的状态，因此我们需要考虑之前的状态是怎么传递到这里来的
  
  min_edist(i, j) =
  
  min(min_edist(i-1,j)+1, min_edist(i, j-1)+1, min_edist(i-1, j-1) + (a[i-1] == b[j-1]? 0 : 1))
  
  
  
  从上面的两种推断发现，我觉的都是比较合理的，但是没有一种的结果与老师给的状态转移方程是一致的（这一点比较疑惑）？所以对于老师的状态转移方程肯定不是从递归树中直接推导出来的，那么请问老师这个状态转移方程该怎么合理的推断出来（我觉得这个问题不是靠多做题解决的，必须要知道推理逻辑才能彻底掌握动态规划）？
  
  
  
  三：接下来还有一个问题（前提假设是老师的状态方程是正确的，具体逻辑还不能理解）
  
  那么如果根据状态状态方程，来填充状态表的第 0 行 第 0列呢（留言中也有许多这方面的疑问）？按照我的理解，既然状态转移方程我们知道了，那么其实从状态转移方程中就可以直接填充表格了，比如填充第 0 行时，因为从状态转移方程中我们发现有 i - 1,j-1 因此当计算第 0 行时，带有 i-1 项的就可以省略了，因此状态转移方程就剩下 (i, j-1) 项了。然后其实就不用分 a[i] b[j] 是否相等了，但是回头看老师的代码，却不明白为什么还要分 a[i] b[j] 相等不相等。希望老师能够解释一下！
  
  
  
  综上：如果老师觉得我描述的问题不清楚，那么希望老师看看这篇文章的其他问题留言，总结一下大家到底哪里不理解，并且对不理解的地方从新更新下当前文章，具体解释一下，比如老师在留言中说过「不能从递归树中直接推导出状态转移方程，两者没有联系」，那么希望老师在文章的对应地方直接表明这句话，并且在加上额外的说明，比如如何推断出状态转移方程，这样整篇文章才能让更多的人从本质上理解动态规划！
  
  
  
  最后希望老师能够认真给出我上面几个问题的解答，谢谢老师！

  作者回复: 你这个问题太多了 我写篇文章给你 你关注：小争哥

  2019-09-24

   1

   4
• 

  传说中的成大大

  if (a[i] == b[j]) minDist[i][j] = min(
  minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1])不明白的是为什么minDist[i-1][j]或者mindist[i][j-1] 要+1呢？
  

  作者回复: (i-1,j)这个状态转移到(i, j)这个状态，minDist要加一
  (i, j)同上
  (i-1, j-1)这个状态转移到(i, j)这个状态，minDist保持不变，因为a[i]==b[j]

  2019-02-28

   5

   4
• 

  Kudo

  选这个专栏的初衷就是为了学习动态规划，作者对这部分内容的讲解我还是比较满意的。两个月前，闲来无事刷了几天LeetCode，遇到一道字符串模式匹配的题，不是结果错误就是复杂度不达标，怎么也搞不定。看了论坛里给出的高赞解答，清一色采用了动态规划的解题方法，当时没有算法基础，真的是看不懂啊，遂放弃。现在经过几节课的学习理出一些思路来，收获颇丰，理论看得比较明白了，程序照着文中的例子也能写个大概，但感觉掌握得还是不牢靠，还需要多加练习。谢谢作者！

  2019-01-02

  

   4
• 

  俊杰

  为什么到后面留言这么少？
  
  在编辑距离里面， 状态转移方程，第二种case ,是不是可以改为：
  
  如果：a[i]==b[j]，那么：min_edist(i, j) 就等于：min_edist(i-1,j-1)
  
  a[i]==b[j]
  a[0..i] 和 b[0..j] 的编辑距离就等价于 a[0..i-1] 和 b[0..j-1]的编辑距离
      

  2019-01-31

  

   3
• 

  Ricky

  老师，您好，您这节内容讲的很清晰透彻，我以前做动态规划问题是直接寻找状态转移方程，基本只能处理一些简单的动态规划问题，没有形成系统的解题思路，听了您这一节后，我觉得将回溯简单思路逐步转化为动规思路让我受益匪浅，但是当我试着将这套思路应用于求解最长递增子序列时却感觉回溯更麻烦，不知能否指点一二

  作者回复: 我的讲解并不是为了指导做题。所以，我讲解的时候，从为什么要动态规划讲起，所以废话比较多。实际上，你理解理论之后，解动态规划题目的时候，一般可以直接写最优子结构，也就是状态转移方程，不需要再从回溯解法开始。。。
  

  2019-01-04

  

   3
• 

  菜菜

  老师，为什么当a[i]==b[j]时，minDist[i][j]不能直接等于minDist[i-1][j-1],而要等于min(minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1])

  2019-03-05

  

   2
• 

  feifei

  要自己思考这个问题，感觉真不容易，因为思路错误，走了不少弯路，花了5天的休息时间，终于解出来了，写出来了，感觉是容易了，但这个思考的过程，感觉自己收获不少，尝试了很多种的解法，然后都一一的否决！
  
  
  这是我写的递归求解，
  
  public int recursionCount4(int[] arrays, int index) {
  
      if (index == 0) {
        return 1;
      }
      int max = 0;
      //此问题的解，递归的核心就是在之前的序列中找到最大递增子序列加1
      //所以需要遍历此此之前的全部数据项
      for (int i = 0; i < index; i++) {
        //递归求解每项的最递增序列
        int value = recursionCount4(arrays, i);
        if (arrays[i] < arrays[index]) {
          if (value > max) {
            max = value;
          }
        }
      }
  
      return max + 1;
    }
  
  
  
  public void countDynamic(int[] arrays) {
      int length = arrays.length;
  
      int[] status = new int[length];
  
      status[0] = 1;
  
      int commMax = 0;
  
      for (int i = 1; i < length; i++) {
        int max = 0;
        for (int j = 0; j < i; j++) {
          if (arrays[j] < arrays[i]) {
            if (status[j] > max) {
              max = status[j];
            }
          }
        }
        status[i] = max + 1;
  
        if (status[i] > commMax) {
          commMax = status[i];
        }
      }
  
      System.out.println("最大递增序列为 ：" + commMax);
      int maxComp = commMax;
      System.out.println("递增:" + Arrays.toString(status));
  
      for (int i = length - 1; i >= 0; i--) {
        if (status[i] == maxComp) {
          System.out.print("-->" + arrays[i]);
          maxComp = maxComp - 1;
        }
      }
    }
  
  
  

  2019-01-11

  

   2