预计阅读时间:8 分钟前几天在网上看到一份鹅场的面试题,算法部分大半是动态规划,最后一题就是写一个计算编辑距离的函数,今天就专门写一篇文章来探讨一下这个经典问题。 我个人很喜欢编辑距离这个问题,因为它看起来十分困难,解法却出奇得简单漂亮,而且它是少有的比较实用的算法(是的,我承认很多算法问题都不太实用)。下面先来看下题目: 为什么说这个问题难呢,因为显而易见,它就是难,让人手足无措,望而生畏。 为什么说它实用呢,因为前几天我就在日常生活中用到了这个算法。之前有一篇公众号文章由于疏忽,写错位了一段内容,我决定修改这部分内容让逻辑通顺。但是公众号文章最多只能修改 20 个字,且只支持增、删、替换操作(跟编辑距离问题一模一样),于是我就用算法求出了一个最优方案,只用了 16 步就完成了修改。 再比如高大上一点的应用,DNA 序列是由 A,G,C,T 组成的序列,可以类比成字符串。编辑距离可以衡量两个 DNA 序列的相似度,编辑距离越小,说明这两段 DNA 越相似,说不定这俩 DNA 的主人是远古近亲啥的。 下面言归正传,详细讲解一下编辑距离该怎么算,相信本文会让你有收获。 一、思路编辑距离问题就是给我们两个字符串 前文 最长公共子序列 说过,解决两个字符串的动态规划问题,一般都是用两个指针 设两个字符串分别为 'rad' 和 'apple',为了把 根据上面的 GIF,可以发现操作不只有三个,其实还有第四个操作,就是什么都不要做(skip)。比如这个情况: 因为这两个字符本来就相同,为了使编辑距离最小,显然不应该对它们有任何操作,直接往前移动 还有一个很容易处理的情况,就是 类似的,如果 下面详解一下如何将这个思路转化成代码,坐稳,准备发车了。 二、代码详解先梳理一下之前的思路: base case 是 对于每对儿字符 if s1[i] == s2[j]: 有这个框架,问题就已经解决了。读者也许会问,这个「三选一」到底该怎么选择呢?很简单,全试一遍,哪个操作最后得到的编辑距离最小,就选谁。这里需要递归技巧,理解需要点技巧,先看下代码: 下面来详细解释一下这段递归代码,base case 应该不用解释了,主要解释一下递归部分。 都说递归代码的可解释性很好,这是有道理的,只要理解函数的定义,就能很清楚地理解算法的逻辑。我们这里 dp(i, j) 函数的定义是这样的:
记住这个定义之后,先来看这段代码: if s1[i] == s2[j]: 如果
dp(i - 1, j) + 1, # 删除
现在,你应该完全理解这段短小精悍的代码了。还有点小问题就是,这个解法是暴力解法,存在重叠子问题,需要用动态规划技巧来优化。 怎么能一眼看出存在重叠子问题呢?前文 动态规划之正则表达式 有提过,这里再简单提一下,需要抽象出本文算法的递归框架: def dp(i, j): 对于子问题 三、动态规划优化对于重叠子问题呢,前文 动态规划详解 介绍过,优化方法无非是备忘录或者 DP table。 备忘录很好加,原来的代码稍加修改即可:
主要说下 DP table 的解法: 首先明确 dp 数组的含义,dp 数组是一个二维数组,长这样:
def dp(i, j) -> int 有了之前递归解法的铺垫,应该很容易理解。dp 函数的 base case 是 既然 dp 数组和递归 dp 函数含义一样,也就可以直接套用之前的思路写代码,唯一不同的是,DP table 是自底向上求解,递归解法是自顶向下求解: 三、扩展延伸一般来说,处理两个字符串的动态规划问题,都是按本文的思路处理,建立 DP table。为什么呢,因为易于找出状态转移的关系,比如编辑距离的 DP table: 还有一个细节,既然每个 你可能还会问,这里只求出了最小的编辑距离,那具体的操作是什么?之前举的修改公众号文章的例子,只有一个最小编辑距离肯定不够,还得知道具体怎么修改才行。 这个其实很简单,代码稍加修改,给 dp 数组增加额外的信息即可:
我们的最终结果不是 重复此过程,可以一步步回到起点 这就是编辑距离算法的全部内容,希望本文对你有帮助。 |
|