09 | 动态规划（上）：如何实现基于编辑距离的查询推荐？
该思维导图由 AI 生成，仅供参考
编辑距离
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
动态规划：编辑距离与字符串相似度 本文介绍了动态规划在解决编辑距离和衡量字符串相似度方面的实际应用。通过编辑距离的定义和计算过程，读者可以深入了解动态规划的核心思想和具体应用。文章以编辑距离为例，详细介绍了动态规划的分解问题、状态转移规律和状态转移方程的求解过程。通过生动的例子和清晰的逻辑，读者可以领略动态规划的高效计算方法，以及编辑距离的对称性特点。此外，文章还提出了思考题，引导读者思考编辑距离衡量字符串相似度的局限性和优化方案。总的来说，本文为读者提供了一份深入浅出的技术指南，帮助他们快速了解动态规划的应用特点和解决问题的方法思路。
《程序员的数学基础课》，新⼈⾸单¥68
全部留言(53)
- 最新
- 精选
任鹏斌关于编辑距离的计算看了好多遍还是不太理解 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
2019-01-07352- 西北偏北搜索引擎中的自动纠错和提示功能，是对用户输入字符串，计算其相似字符串。 比如mouse就是用户输入mouuse的相似字符串。 一个字符串有哪些相似字符串，无非是把该字符串进行一系列可能的变形编辑。比如把某个字母删掉，或增加一个字母，或替换该字母 最后看变形后的单词，是否是一个合法单词。如果是，则给用户提示。 原始单词或字符变形到一个合法字符串的步数，称为这两个单词之间的编辑距离。 但一个单词随着长度增加，其对应的合法单词，编辑距离计算将会很多。不可取。 所以需要最优解，找出用户输入词，编辑距离最小的目标词即可
作者回复: 分析的很好，在实际项目中还可以考虑其他因素，例如用户搜索的次数、对应的搜索结果数量等等。
2019-01-15215 
somenzz有时候编辑距离最短的字符串并不能代表用户真正想输入的正确字符串，例如用户输出了 worder，实际上是想查 worker，但编辑距离为 1 的有很多，如 warder，wonder，我在想是不是应该按用户输入的字符串前辍最一致的字符串开始再计算编辑距离，例子中的 mouuse 和 mouse ，先直接替换掉前面一样的 mou,直接计算 use 和 se 的编辑距离，再从替换后面一样的 se，这样就是直接计算 u 和空串的编辑距离，这样就可以很快计算出距离为1，不知道这样理解优化是否正确，请老师指点。作者回复: 很好的思考，在不同的应用场景我们可以考虑不同的侧重点。比如你这里说的前缀更重要，你可以考虑一下如何修改编辑距离的定义，以及对应的状态转移方程，来体现前缀更重要。 除基于编辑距离的相似度，还可以考虑其他的因素，例如查询的次数（热度），查询对应的搜索结果数量、个性化等等，不过这是另一个很大的话题
2019-01-069
胖胖程https://www.jianshu.com/p/4678d3f7b6f1 之前写过的一篇编辑距离文章，代码是用动态规划的方式实现的。作者回复: 不错的文章
2020-04-1337
Jerry银银老师，如果让您给计算机相关的职场人推荐一本关于数学的书，您会推荐什么？作者回复: 我会写篇加餐，给大家推荐几本书
2019-01-086
Yang编辑距离没办法刻画语义信息，比如同义词，否定词（编辑距离很短）。作者回复: 是的
2019-10-094
danvid编辑距离解析，其实看看下面这个结合图会好理解一点，其实就是下一个结果基于上一个结果的一种情况去进行加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(上)}作者回复: 结合表格会更容易理解
2019-05-1634
书木子谢明向老师请教几个问题: 1.适应动态规划的要求是 sum(每一步最优解)=最终最优解，这样的理解对吗？应该有问题不适合动态规划求解，如何辨别呢？ 2. 我理解的“编辑的最短距离”描述的是两个字符串相似性的一种方式，这种方式需要逐个迭代字符，在英文环境中该算法可以推荐到单词级别，中文环境貌似只能推荐到词级别。ES中计算搜索结果相似程度也是用的“编辑距离”么？作者回复: 可以这么说，适应动态规划的要求是每一状态的最优解都可以由上一个状态的最优解推导出来，所以动态规划最核心的步骤是找出状态转移方程。如果没有办法通过上一个状态的最优解推导出当前状态的最优解，那么就不适合使用动态规划方法。 ES或者Solr中计算搜索结果的相似度，是使用的信息检索理论，不是简单的“编辑距离”。不过在一些query autocomplete的功能中可能会用到“编辑距离”。编辑距离更适合拉丁文，所以中文的拼音也可用到它，但是中文词就不太适合了。
2019-07-173
等待首先，计算量非常大。我们假设字符串 A 的长度是 n，而 B 字符串中不同的字符数量是 m，那么 A 所有可能的排列大致在 m^n 这个数量级。 这里的m^n是如何得知的呢？这个没看懂，谢谢作者回复: 你可以结合排列组合那一讲的内容来看，大意就是每个位置上有m种可能，那么n个位置就是m的n次方可能性
2020-06-152
伊利丹怒风其实例子的三种操作是对应状态转移表里面分别从：上、左、左上（斜线）变换过来的三种可能性。按这个理解会更容易一些，比如第一个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作者回复: 是的👍
2020-02-202
