程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23338 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

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

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

编辑距离

当你在搜索引擎的搜索框中输入单词的时候,有没有发现,搜索引擎会返回一系列相关的关键词,方便你直接点击。甚至,当你某个单词输入有误的时候,搜索引擎依旧会返回正确的搜索结果。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(36)

  • 任鹏斌
    关于编辑距离的计算看了好多遍还是不太理解
    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
    2
    22
  • 西北偏北
    搜索引擎中的自动纠错和提示功能,是对用户输入字符串,计算其相似字符串。
    比如mouse就是用户输入mouuse的相似字符串。
    一个字符串有哪些相似字符串,无非是把该字符串进行一系列可能的变形编辑。比如把某个字母删掉,或增加一个字母,或替换该字母
    最后看变形后的单词,是否是一个合法单词。如果是,则给用户提示。

    原始单词或字符变形到一个合法字符串的步数,称为这两个单词之间的编辑距离。

    但一个单词随着长度增加,其对应的合法单词,编辑距离计算将会很多。不可取。

    所以需要最优解,找出用户输入词,编辑距离最小的目标词即可

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

    2019-01-15
    6
  • 银时空de梦
    1.表格里边的三种情况,第一种跟第二种写的一样
    2.分析到总体编辑距离是2,2,0,后边总结又说1,1,0
    麻烦老师能不能把步骤分解解释一下

    作者回复: 应该是2,2,0。我稍后改一下
    具体的分解你可以看图表中的注释,分三种情况,每种情况都对应于红色箭头的指向

    2019-01-07
    5
  • 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
    1
    3
  • Ricky
    #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];
    }
    2019-01-10
    3
  • Jerry银银
    老师,如果让您给计算机相关的职场人推荐一本关于数学的书,您会推荐什么?

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

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

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

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

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

    2019-01-06
    2
  • caohuan
    本篇所得:动态规划 为寻找的最优解,它只关心 最优的一个解,其他的不会再考虑,比如求解 数组的最大 和最小值,一般只有一个(可能有重复的最值,但最值是相等的)。

    工作和生活中,我们一般把大问题分解为小问题,再把小问题 分解为容易解答的问题,动态规划 就是在 容易解答的问题中选择最优解。

    黄老师 在文中提到:搜索引擎输入的搜索词的查询和推荐,就是对 缺失和错误的字符串进行操作,比如我们输入错误的字符串A,和正确的字符串B,需要把字符串A改到B,需要把字符串 分解到字符 的小问题,然后进行‘增、删、改’等操作,这里运用 动态规划 寻找最优解,不需要使用排列 这么复杂的方法 因为排列计算消耗的时间会很长,运用动态规划 很节能。

    今天所得:解决问题的方法 (1)不断的分解问题,把大问题分解为小问题,把小问题 再分解...直至到可以解答的问题;(2)使用动态规划 求解 小问题的 最优解。

    回答老师的问题:用编辑距离对字符串状态转移资源消耗的标记,会浪费很多 内存和运算资源,可以把 字符串 再分割成字符,把 二个字符串的不同的字符 掏出来,再用编辑距离 处理,应该会更快一下、占用资源也少一些,老师是否同意,也期待 黄老师的指正。

    老师 可以用 斐波那契数列 来说明 动态规划的问题,更让我们易理解。

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

    2019-01-21
    1
  • microsnow
    看懵了。下一节表格下面说明,三种编辑距离分别是:替换、插入和删除字符。
    本节:三种编辑距离 2,2,0。最后一个是替换。

    替换操作理解,插入和删除不理解。老师帮忙分析下。
    一种情况:
    A字符为:m B字符为:mo

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

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

    2019-01-06
    1
  • ncubrian
    黄老师,这期怎么没有sample code

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

    2019-01-02
    1
  • aoe
    原来动态规划适合解决:通常只关心一个最优解,而这个最优解是单调改变的。第一次感觉动态规划没那么恐怖了!

    作者回复: 没错,这是最基本的原则,很高兴课程对你有帮助

    2019-11-30
  • Eleven
    老师,表格中的三种情况:
    1.插入字符:B字符串为m的时候,A空串增加一个字符变为m,编辑距离增加1,整体编辑距离距离为2(这里A从空串插入一个字符m编辑距离不就是1么?为什么会是2)
    2.反过来我也有一样的疑问
    这里我不解是因为为什么要从空串算起,按照图表中的情况A和B不都是m么?

    作者回复: 动态规划穷举了到当前状态的所有的可能性,然后去最优的。所以虽然都是m,有一种可能是先删除1个m,再添加1个m。从人的角度看这是多于的,不过机器需要这样一个过程,确保不会漏掉最优解

    2019-11-21
    1
  • Eleven
    黄老师,
    我们先考虑最简单的情况。假设字符串 A 和 B 都是空字符串,那么很明显这个时候编辑距离就是 0。如果 A 增加一个字符 a1,B 保持不动,编辑距离就增加 1。同样,如果 B 增加一个字符 b1,A 保持不动,编辑距离增加 1。但是,如果 A 和 B 有一个字符,那么问题就有点复杂了,我们可以细分为以下几种情况。(这个可以理解。)
    我们先来看插入字符的情况。A 字符串是 a1 的时候,B 空串增加一个字符变为 b1;或者 B 字符串为 b1 的时候,A 空串增加一个字符变为 a1。很明显,这种情况下,编辑距离都要增加 1。(这个也可以理解。)
    我们再来看替换字符的情况。当 A 和 B 都是空串的时候,同时增加一个字符。如果要加入的字符 a1 和 b1 不相等,表示 A 和 B 之间转化的时候需要替换字符,那么编辑距离就是加 1;如果 a1 和 b1 相等,无需替换,那么编辑距离不变。(这个有点懵啊)
    最后,我们取上述三种情况中编辑距离的最小值作为当前的编辑距离。注意,这里我们只需要保留这个最小的值,而舍弃其他更大的值。这是为什么呢?因为编辑距离随着字符串的增长,是单调递增的。所以,要求最终的最小值,必须要保证对于每个子串,都取得了最小值。有了这点,之后我们就可以使用迭代的方式,一步步推导下去,直到两个字符串结束比较。(这里也有点懵)
    2019-11-19
  • 建强
    如果词库中的词条数量很大,利用编辑距离来匹配词条的相似度效率会比较低,因为编辑距离的计算是逐个字符进行匹配扫描的,做相似度匹配时需要选出编辑距离最短的那个词条,这样就需要扫描整个词库,才能获得具有最短距离的词条。
           我个人的优化方案:预先把每个词条的前缀全部剥离出来,某些词条的前缀可能是重复的,建立前缀与词条的一对多关系,利用哈希算法,得到每个前缀的哈希值,同时把各个前缀存贮于哈希表中,哈希表中除了存贮前缀哈希值,同时还存贮该前缀属于哪个词条,即词条的索引号,这样每次查询时,先把要查询的词条按相同的哈希算法,算出哈希值,再根据哈希值,得到该前缀所属的所有词条,这样就缩小了查询范围,然后再计算每个词条和被查询的词条的编辑距离,得到相近的词。
    以上是我个人的一点浮浅理解,请老师指正。

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

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

    作者回复: 是的

    2019-10-09
  • Paul Shan
    我个人觉得编辑距离可以看作是一个数学归纳法的问题,不过这里的归纳是基于两个值而非一个。假设两个字符串的长度分别是m和n,编辑距离定义为d(m,n),为了让末尾匹配有三种做法,删除第一个字符串最后一个(等价为添加第一个字符串最后一个到第二个字符串),这样问题规约为d(m-1,n)+1.同样我们也可以删除第二个字符串最后一个,距离规约为d(m,n-1)+1。还有第三种就是同时删除两个字符串的末尾,这里又分为两种情况,分别对应于两个字符串最后一个是否相等(是否需要一次替换操作)d(m-1,n-1)+ (0 or 1),综合这三种,选取一种最小的,我们就可以得到一个递归式子。
    请问老师,这种基于二维数学归纳法的方法和动态规划法是否在原理上等效,多谢!

    作者回复: 过程上确实有类似,但是本质上有点不同。数学归纳法是可以归纳出结论的,而动态规划有的时候不行,我们需要把整个动态规划的过程跑完才能知道最终的结果。

    2019-08-21
  • 风在身后
    编辑距离是从一个字符串变成另一个字符串的距离,那么拿suggestion来说,开始为空,然后人输入a,计算机生成a。就对应老师说的下面的情况。这个时候不应该把人输的a计算一个距离,所以应该是1,不应该是2

    (1)中的情况比较绕,你可以这么来看,一开始A、B都是空串,A增加一个字符m,两者编辑距离是1,然后B增加一个字符m,即使两个m相等,编辑距离也会由1变为2,而不是维持在1,也不会降到0。因为编辑距离2表示的是A添加一个m字符,B再添加一个m字符。

    作者回复: 是的,更详细的解释

    2019-05-30
  • 梦倚栏杆
    感觉有点像运筹学里的最大流最小割问题的处理思路,但是现在已经忘记的差不多了,需要重新看看了
    2019-03-23
收起评论
36
返回
顶部