程序员的数学基础课
黄申
LinkedIn 资深数据科学家
83374 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 58 讲
导读 (1讲)
基础思想篇 (18讲)
程序员的数学基础课
15
15
1.0x
00:00/00:00
登录|注册

09 | 动态规划(上):如何实现基于编辑距离的查询推荐?

删除字符
插入字符
替换字符
俄罗斯科学家莱文斯坦提出
子问题称为不同的状态
求解子问题的最优值
划分为更多更小的子问题
单调递增的编辑距离
只保留最优解
每次选择最优解
实际情况复杂
计算量非常大
删除字符
插入字符
替换字符
实时性服务的响应时间
大量计算
编辑操作
定义
每种状态只保留一个当前的最优解
最优解是单调改变的
关心一个最优解
解决问题的方法和思路
动态规划
最优解
排列的思想
复杂性
从一个字符串转换为另一个字符串所需的最少编辑操作次数
编辑距离
对用户输入查找相似关键词并返回
优化方案
局限性
动态规划
学习的过程
计算编辑距离
实现过程
测量文本相似度的指标
核心思想
思考题
小结
状态转移
查询推荐
实现基于编辑距离的查询推荐
动态规划

该思维导图由 AI 生成,仅供参考

你好,我是黄申。
上一篇讲组合的时候,我最后提到了有关文本的关键字查询。今天我接着文本搜索的话题,来聊聊查询推荐(Query Suggestion)的实现过程,以及它所使用的数学思想,动态规划(Dynamic Programming)。
那什么是动态规划呢?在递归那一节,我说过,我们可以通过不断分解问题,将复杂的任务简化为最基本的小问题,比如基于递归实现的归并排序、排列和组合等。不过有时候,我们并不用处理所有可能的情况,只要找到满足条件的最优解就行了。在这种情况下,我们需要在各种可能的局部解中,找出那些可能达到最优的局部解,而放弃其他的局部解。这个寻找最优解的过程其实就是动态规划。
动态规划需要通过子问题的最优解,推导出最终问题的最优解,因此这种方法特别注重子问题之间的转移关系。我们通常把这些子问题之间的转移称为状态转移,并把用于刻画这些状态转移的表达式称为状态转移方程很显然,找到合适的状态转移方程,是动态规划的关键。
因此,这两节我会通过实际的案例,给你详细解释如何使用动态规划法寻找最优解,包括如何分解问题、发现状态转移的规律,以及定义状态转移方程。

编辑距离

当你在搜索引擎的搜索框中输入单词的时候,有没有发现,搜索引擎会返回一系列相关的关键词,方便你直接点击。甚至,当你某个单词输入有误的时候,搜索引擎依旧会返回正确的搜索结果。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
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-07
    3
    52
  • 西北偏北
    搜索引擎中的自动纠错和提示功能,是对用户输入字符串,计算其相似字符串。 比如mouse就是用户输入mouuse的相似字符串。 一个字符串有哪些相似字符串,无非是把该字符串进行一系列可能的变形编辑。比如把某个字母删掉,或增加一个字母,或替换该字母 最后看变形后的单词,是否是一个合法单词。如果是,则给用户提示。 原始单词或字符变形到一个合法字符串的步数,称为这两个单词之间的编辑距离。 但一个单词随着长度增加,其对应的合法单词,编辑距离计算将会很多。不可取。 所以需要最优解,找出用户输入词,编辑距离最小的目标词即可

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

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

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

    2019-01-06
    9
  • 胖胖程
    https://www.jianshu.com/p/4678d3f7b6f1 之前写过的一篇编辑距离文章,代码是用动态规划的方式实现的。

    作者回复: 不错的文章

    2020-04-13
    3
    7
  • Jerry银银
    老师,如果让您给计算机相关的职场人推荐一本关于数学的书,您会推荐什么?

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

    2019-01-08
    6
  • Yang
    编辑距离没办法刻画语义信息,比如同义词,否定词(编辑距离很短)。

    作者回复: 是的

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

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

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

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

    2020-06-15
    2
  • 伊利丹怒风
    其实例子的三种操作是对应状态转移表里面分别从:上、左、左上(斜线)变换过来的三种可能性。按这个理解会更容易一些,比如第一个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-20
    2
收起评论
显示
设置
留言
53
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部