精选留言(52)

• 
  任鹏斌

  2019-01-07

  关于编辑距离的计算看了好多遍还是不太理解 1、A、B都为空A转化为B或者B转化为A不需要做任何操作编辑距离为0（可以理解） 2、A增加一个字符a1，B保持不动，编辑距离为1。或者B增加一个字符b1，A保持不动，编辑距离为1.（初始为空的情况，可以理解） 3、如何A和B有一个字符那么情况就有点复杂了，具体如下： （1）插入字符的情况，A字符串为a1的时候，B空串增加一个字符变为b1，或者B字符串为b1的时候，A空串增加一个字符变为a1。很明显这种情况下编辑距离都要增加1 问题：这时候如果b1和a1是一样的字符A或者B再插入后已经是一样的了也不需要再做转化了，这时候编辑距离是否应该就是1？下面的表格中A、B串的m与m处的插入情况与这里一样插入的编辑距离为什么是2？ （2）替换字符的情况，可以理解为不相等的情况下才替换所以此时编辑距离加1，如果相等不需要替换则编辑距离为0？ 麻烦老师解答一下，谢谢！

  展开

  作者回复: （2）基本是对的，只是明确一下，“如果相等不需要替换则编辑距离 “加” 0” （1）中的情况比较绕，你可以这么来看，一开始A、B都是空串，A增加一个字符m，两者编辑距离是1，然后B增加一个字符m，即使两个m相等，编辑距离也会由1变为2，而不是维持在1，也不会降到0。因为编辑距离2表示的是A添加一个m字符，B再添加一个m字符。虽然在人看来两者相等，但对于计算机而言要遍历这种情况。至于两者相等的情况，由替换操作表示，因此可以取到最小值0

  共 3 条评论

  51
• 
  西北偏北

  2019-01-15

  搜索引擎中的自动纠错和提示功能，是对用户输入字符串，计算其相似字符串。 比如mouse就是用户输入mouuse的相似字符串。 一个字符串有哪些相似字符串，无非是把该字符串进行一系列可能的变形编辑。比如把某个字母删掉，或增加一个字母，或替换该字母 最后看变形后的单词，是否是一个合法单词。如果是，则给用户提示。 原始单词或字符变形到一个合法字符串的步数，称为这两个单词之间的编辑距离。 但一个单词随着长度增加，其对应的合法单词，编辑距离计算将会很多。不可取。 所以需要最优解，找出用户输入词，编辑距离最小的目标词即可

  展开

  作者回复: 分析的很好，在实际项目中还可以考虑其他因素，例如用户搜索的次数、对应的搜索结果数量等等。

  共 2 条评论

  14
• 
  somenzz

  2019-01-06

  有时候编辑距离最短的字符串并不能代表用户真正想输入的正确字符串，例如用户输出了 worder，实际上是想查 worker，但编辑距离为 1 的有很多，如 warder，wonder，我在想是不是应该按用户输入的字符串前辍最一致的字符串开始再计算编辑距离，例子中的 mouuse 和 mouse ，先直接替换掉前面一样的 mou,直接计算 use 和 se 的编辑距离，再从替换后面一样的 se，这样就是直接计算 u 和空串的编辑距离，这样就可以很快计算出距离为1，不知道这样理解优化是否正确，请老师指点。

  展开

  作者回复: 很好的思考，在不同的应用场景我们可以考虑不同的侧重点。比如你这里说的前缀更重要，你可以考虑一下如何修改编辑距离的定义，以及对应的状态转移方程，来体现前缀更重要。 除基于编辑距离的相似度，还可以考虑其他的因素，例如查询的次数（热度），查询对应的搜索结果数量、个性化等等，不过这是另一个很大的话题

  

  7
• 
  Ricky

  2019-01-10

  #include <iostream> using namespace std; void levenshteinDis(const char* str1, const char* str2, int m, int n, int i, int j, int edist, int &mind) { if (i == m || j == n) { if (i < m) edist += (m-i); if (j < n) edist += (n-j); if (edist < mind) mind = edist; return; } if (str1[i] == str2[j]) { levenshteinDis(str1, str2, m, n, i+1, j+1, edist, mind); } else { // 删除或增加 levenshteinDis(str1, str2, m, n, i+1, j, edist+1, mind); levenshteinDis(str1, str2, m, n, i, j+1, edist+1, mind); // 替换操作 levenshteinDis(str1, str2, m, n, i+1, j+1, edist+1, mind); } } int levenshteinDis(const char* a, const char* b, int m, int n) { int mind = 0xfffffff; levenshteinDis(a, b, m, n, 0, 0, 0, mind); return mind; } /* * 状态转移方程 * 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) * 2.当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)) */ int levenshteinDisDP(const char* a, const char* b, int m, int n) { // 初始化dp数组 int dp[m][n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { dp[i][j] = 0; } } // 初始化第0列 for (int i = 0; i < m; ++i) { if (a[i] == b[0]) dp[i][0] = i; else if (i != 0) dp[i][0] = dp[i-1][0] + 1; else dp[i][0] = 1; } // 初始化第0行 for (int i = 0; i < n; ++i) { if (a[0] == b[i]) dp[0][i] = i; else if (i > 0) dp[0][i] = dp[0][i-1] + 1; else dp[0][i] = 1; } // 填表余下部分 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, a[i] == b[j] ? dp[i-1][j-1]:dp[i-1][j-1]+1); } } return dp[m-1][n-1]; }

  展开

  

  6
• 
  Jerry银银

  2019-01-08

  老师，如果让您给计算机相关的职场人推荐一本关于数学的书，您会推荐什么？

  作者回复: 我会写篇加餐，给大家推荐几本书

  

  6
• 
  胖胖程

  2020-04-13

  https://www.jianshu.com/p/4678d3f7b6f1 之前写过的一篇编辑距离文章，代码是用动态规划的方式实现的。

  作者回复: 不错的文章

  共 2 条评论

  6
• 
  Yang

  2019-10-09

  编辑距离没办法刻画语义信息，比如同义词，否定词（编辑距离很短）。

  作者回复: 是的

  

  4
• 
  danvid

  2019-05-16

  编辑距离解析，其实看看下面这个结合图会好理解一点，其实就是下一个结果基于上一个结果的一种情况去进行加0还是加0，老师说的真的一头雾水，大家可以参考一下 解析： i相当于第几行，j相当于第几列 1.如果i或者j=0就是edit(i,j)=j或者i； 2.左(i-1,j)，上(i,j-1)，左上(i-1,j-1)相当于前一个子集可能出现的三种情况的下求最小值，其中左+1，上+1，右上(如果当前i=j，则+0，不等则+1)，，求这三者的最小值例如：左=1，左上=0，上=1则 edit(左)=1+1=2，如果当前格子对应行列的数据相等则edit(左上)=0+0=0，否则edit(左上)=0+1=1，edit(上)=1+1=2,所以结果就是edit(i,j)=min{edit(左),edit(左上),edit(上)}

  展开

  作者回复: 结合表格会更容易理解

  共 3 条评论

  4
• 
  cwtxz

  2019-12-27

  我所接触到的程序员，大多数的数学水平其实是比较差的，究其原因还是在于平常自己从事的工作大多用不上什么数学知识，就算要用，也只是一些简单基础的应用，甚至于有些直接找现成的工具来解决而不是依靠自己的思考，亲自动手去推敲原理。渐渐地，他们会发现，我不需要懂太多的数学知识，只需要简单的加减乘除四则运算、会开个根号、会求多元一次方程的解、做一些简单的幂运算、会一些简单的三角函数运算，其实就够了，不需要什么微积分、线性代数、数理统计这些高等数学的知识，至于更高深的泛函分析、矩阵分析、数理方程就更加不用说了。如果只是这样，注定了只能做一个平庸的开发者，甚至职业生涯的寿命也会变得很短暂。我是一个有追求的技术人，期待着能够成为大神，所以数学我是一定要坚持学的，加油!!!

  展开

  

  3
• 
  书木子谢明

  2019-07-17

  向老师请教几个问题: 1.适应动态规划的要求是 sum(每一步最优解)=最终最优解，这样的理解对吗？应该有问题不适合动态规划求解，如何辨别呢？ 2. 我理解的“编辑的最短距离”描述的是两个字符串相似性的一种方式，这种方式需要逐个迭代字符，在英文环境中该算法可以推荐到单词级别，中文环境貌似只能推荐到词级别。ES中计算搜索结果相似程度也是用的“编辑距离”么？

  展开

  作者回复: 可以这么说，适应动态规划的要求是每一状态的最优解都可以由上一个状态的最优解推导出来，所以动态规划最核心的步骤是找出状态转移方程。如果没有办法通过上一个状态的最优解推导出当前状态的最优解，那么就不适合使用动态规划方法。 ES或者Solr中计算搜索结果的相似度，是使用的信息检索理论，不是简单的“编辑距离”。不过在一些query autocomplete的功能中可能会用到“编辑距离”。编辑距离更适合拉丁文，所以中文的拼音也可用到它，但是中文词就不太适合了。

  

  3
• 
  l c

  2020-07-01

  个人认为这里对于编辑距离的讲解确实不够清晰，思考了很久分享一下我的理解： 首先初始化边界解，为什么，因为边界解是相对于空串的，我们知道空串到长度为n的字符串的最小操作数就是n，即全部添加或删除。 现在我们来思考这个问题，(mo, m)(3, 1, 2)是怎么来的呢？ 1. 从mo往m添加，即表中从上往下添加。 我们知道mo已经大于了m，对于这样一个情况，我们还想做添加，唯一的方法是清空mo（2），然后添加一个m（1）。 这是3的真实由来。 编程中我们这样思考，我们知道mo变为empty最少需要2，那么mo变为empty再添加一个数，那么就是3了。 2. 从m往mo添加，即表中从左往右添加。 即添加o(1)。 一样的思路，我们知道m变为m需要0， 再添加一个数，就是1。 3. 替换，在做替换时，为什么我们要看左上？因为交换是基于左上的，我们相当于对mo, m各减少一个字符，得到（o, m）。然后思考这两个字符是否需要交换。 由于o不等于m，所以是需要的，那么交换。 我们知道m变为empty需要1，那么再交换一下把o变成m，就是2。 从上述中我们大概总结出来了一个具体实现： 1. 从上往下做添加操作，我们的操作数一定是，将当前行字符串先变为列字符串.substring(0, n - 1)。 再进行添加操作。 则总操作为T(i, j - 1) + 1。 2. 从左往右做添加操作，我们的操作一定是，将当前列字符串先变为行字符串.substring(0, m - 1)， 所需操作数为T(i - 1, j)， 再进行添加操作，则总操作为T(i - 1, j) + 1。 3. 做替换操作，从行字符串.substring(0, m - 1) 和 列字符串.substring(0, n-1) 开始考虑，我们已知二者转化操作为T(i - 1, j - 1)。 如果新加入的两个字母相等，说明没必要替换，总操作为T(i - 1, j - 1) + 0, 反之为T(i - 1, j - 1) + 1。 取得所有可能的操作的最小值，就确立了当前行列字符串的转化所需最小操作数，从而解决了问题。

  展开

  共 1 条评论

  2
• 
  等待

  2020-06-15

  首先，计算量非常大。我们假设字符串 A 的长度是 n，而 B 字符串中不同的字符数量是 m，那么 A 所有可能的排列大致在 m^n 这个数量级。 这里的m^n是如何得知的呢？这个没看懂，谢谢

  作者回复: 你可以结合排列组合那一讲的内容来看，大意就是每个位置上有m种可能，那么n个位置就是m的n次方可能性

  

  2
• 
  伊利丹怒风

  2020-02-20

  其实例子的三种操作是对应状态转移表里面分别从：上、左、左上（斜线）变换过来的三种可能性。按这个理解会更容易一些，比如第一个A：m、B：m的理解： 1、从“左”过来：A：m，B：0，由于B：0->m，所以需要增加一个“插入”操作，也就是1+1=2 2、从“上”转移过来：A：0，B：m，由于A：0->m，所以需要增加一个“删除”操作，也就是1+1=2 3、从“左上”转移过来：A：0，B：0，由于A，B都增加了一个字符，所以需要增加一个“替换”操作，由于这里A、B增加的字符相等，所以无需“替换”，因此0+0 = 0

  展开

  作者回复: 是的👍

  

  2
• 
  caohuan

  2019-01-21

  本篇所得：动态规划 为寻找的最优解，它只关心 最优的一个解，其他的不会再考虑，比如求解 数组的最大 和最小值，一般只有一个（可能有重复的最值，但最值是相等的）。 工作和生活中，我们一般把大问题分解为小问题，再把小问题 分解为容易解答的问题，动态规划 就是在 容易解答的问题中选择最优解。 黄老师 在文中提到：搜索引擎输入的搜索词的查询和推荐，就是对 缺失和错误的字符串进行操作，比如我们输入错误的字符串A，和正确的字符串B，需要把字符串A改到B，需要把字符串 分解到字符 的小问题，然后进行‘增、删、改’等操作，这里运用 动态规划 寻找最优解，不需要使用排列 这么复杂的方法 因为排列计算消耗的时间会很长，运用动态规划 很节能。 今天所得：解决问题的方法 （1）不断的分解问题，把大问题分解为小问题，把小问题 再分解...直至到可以解答的问题;（2）使用动态规划 求解 小问题的 最优解。 回答老师的问题：用编辑距离对字符串状态转移资源消耗的标记，会浪费很多 内存和运算资源，可以把 字符串 再分割成字符，把 二个字符串的不同的字符 掏出来，再用编辑距离 处理，应该会更快一下、占用资源也少一些，老师是否同意，也期待 黄老师的指正。 老师 可以用 斐波那契数列 来说明 动态规划的问题，更让我们易理解。

  展开

  作者回复: 感谢你关于斐波那契数列的建议，我之前也考虑过，由于这个例子非常直观，也可以使用迭代实现，所以担心无法体现状态转移的特点。

  

  2
• 
  菩提

  2019-01-06

  老师，表格中插入一个字符m，编辑距离增加1。为什么说整体编辑距离是2呢？ 如果推导表格往下移动一格，字符串A变成mo，字符串B变成了m，这时应该如何推导啊？希望您帮忙解答一下，第一次实际接触动态规划，谢谢！ 最近反复看这两篇动态规划，表格推导看的有点似懂非懂。望老师指导一下

  作者回复: 你问题的第一句，具体是指表格中三种情况的第一种，是吧？这是指AB两者一开始都为空，那么A字符串增加1个m，编辑距离加1，然后B再增加一个m，所以编辑距离再加1变为2，当然这种不是最小值，最小值是0，也就是表中第三种情况

  

  2
• 
  建强

  2019-11-02

  如果词库中的词条数量很大，利用编辑距离来匹配词条的相似度效率会比较低，因为编辑距离的计算是逐个字符进行匹配扫描的，做相似度匹配时需要选出编辑距离最短的那个词条，这样就需要扫描整个词库，才能获得具有最短距离的词条。 我个人的优化方案：预先把每个词条的前缀全部剥离出来，某些词条的前缀可能是重复的，建立前缀与词条的一对多关系，利用哈希算法，得到每个前缀的哈希值，同时把各个前缀存贮于哈希表中，哈希表中除了存贮前缀哈希值，同时还存贮该前缀属于哪个词条，即词条的索引号，这样每次查询时，先把要查询的词条按相同的哈希算法，算出哈希值，再根据哈希值，得到该前缀所属的所有词条，这样就缩小了查询范围，然后再计算每个词条和被查询的词条的编辑距离，得到相近的词。 以上是我个人的一点浮浅理解，请老师指正。

  展开

  作者回复: 是个很好的想法，不过这里有个假设就是比较相似度的词它们拥有同样的前缀，对吧？例如，我们可以比较mouse和mouuse，但是可能没法处理mouse和nouse

  

  1
• 
  Hesher

  2019-03-14

  似乎终于理解了表格里的内容： 对于前两种插入情况，都是空串插入，A和B各插入一个m，一共做了两次插入所以编辑距离为2； 对于第三种替换情况：A、B都插入m，不需要替换，所以全程替换操作一次都没有，所以编辑距离为0（插入操作不算在编辑距离的计数中吗？）。 不知道这样理解对不对？

  展开

  作者回复: 前面的理解是对的，对于第三种情况，如何替换的字母相同，那么就是0，否则是1

  共 2 条评论

  1
• 
  microsnow

  2019-01-17

  看懵了。下一节表格下面说明，三种编辑距离分别是：替换、插入和删除字符。 本节：三种编辑距离 2,2,0。最后一个是替换。 替换操作理解，插入和删除不理解。老师帮忙分析下。 一种情况： A字符为：m B字符为：mo 第二种情况： A字符为：mo B字符为：mo

  展开

  共 2 条评论

  1
• 
  ncubrian

  2019-01-02

  黄老师，这期怎么没有sample code

  作者回复: 我会在下一期放出sample code

  

  1
• 
  杨芸芸

  2022-12-06 来自湖北

  “编辑距离来衡量字符串之间的相似程度有什么局限性”：A、A’之间的编辑距离小于B、B'之间的编辑距离，但是B的长度比A大很多，这个时候不能认为A、A’的相似度大于B、B'的相似度，甚至有可能B、B'的相似度更高。优化方案，使用相似度p=编辑距离/字符串长度 衡量字符串间的相似程度

  

  