动态规划求最小编辑距离

动态规划求最小编辑距离
neuclil

2017.12.06 阅读 237 评论 0 喜欢 0

我们需要去计算两个字符串之间的相似度,这个在拼写校正和在生物中计算蛋白质序列距离非常有用。

编辑距离定义

The minimum edit distance between two strings is the minimum number of editing operations(Insertion, Deletion, Substitution) needed to transform one into the other.

For two stings X of length n, Y of length m, we define D(i,j) :

  • i.e., the first i characters of X and the first j characters of Y
  • The edit distance between X and Y is thus D(n,m)

动态规划求解最小编辑距离

在求解动态规划问题的时候,都需要回答以下几个问题:

  • 状态是什么❓ 在最小编辑距离中,我们定义D[i][j]为长度为i的字符串X和长度为j的字符串Y的最小编辑距离,我们要求解的就是最终的状态D[m][n]
  • 初始状态值是多少❓有了状态的定义,我们就可以找出初始状态的值,因为在动态规划中,我们要做的是求解最终的状态, 这必须依赖于初始状态和转移方程。一般来说,初始状态都是边界值,就是D[i][0]和D[0][j]。在最小编辑距离问题中,D[i][0]表示长度为i的字符串和长度为0的字符串的最小编辑距离,显然只能通过删除操作,得到长度为0的字符串,所以有D[i][0]=i。同理D[0][j]=j
  • 转移方程❓转移方程是动态规划中的重点,这个方程应具体问题具体分析,在本问题中,看下面示意图:
    dp.png

这里我用 # I N T E N T I O N 表示字符串X,# E X E C U T I O N表示字符串Y。假设现在要计算的是D[i][j],此时i指向T,j指向E,我们要定义转移方程,也就是如何用已知的状态来推出现在的状态,换句话说,就是将当前状态D[i][j]用之前状态来求解。

那么怎么表示呢?虽然这个方程需要具体问题具体分析得到,但是分析的过程一般是一样的,如何做分析呢?

  1. 数型结合,可以先画出示意图,方便我们分析,如上面我画的这个示意图;
  2. 转化化归,要知道,我们是想通过用已知来表示未知,所以在示意图画出来后,我们要明白要做的是将未知的D[i][j]转化为前面已知状态表示。
  3. 分类整合,这里实际上有两个小步骤:
    • 分类:用已知表示未知,或者从已知走向未知,路径往往不唯一!可以说在动态规划问题里肯定是不唯一的,也就是说D[i][j]可以有多条路径得到。这时候我们就要分类讨论,在这个问题中,我在示意图画出了三种颜色的线,分别表示三种不同的路径:
      • 红色: D[i][j]可以这样得到,先将X(1..i)转化为Y(1...j-1),此时应该求他们的最小编辑距离D[i][j-1],然后呢插入Y(j),所以,最后总的编辑距离为
        D[i][j] = D[i][j-1] + 1 (insert)
      • 蓝色: D[i][j]可以这样得到,先将X(1..i-1)转化为Y(1…j),此时应该求他们的最小编辑距离D[i-1][j],删除X(i),所以,最后总的编辑距离为
        D[i][j] = D[i-1][j] + 1 (delete)
      • 黄色: D[i][j]可以这样得到,先将长度为i-1的字符串转化为长度为j-1的字符串,此时应该求他们的最小编辑距离D[i-1][j-1],然后呢做一下判断X(i)是否等于Y(j),如果相等就不要做替换操作,否则需要做替换操作,所以,最后总的编辑距离为
        D[i][j] = D[i-1][j-1] + 0 if X(i) = Y(j)
        D[i][j] = D[i-1][j-1] + 2 if X(i) != Y(j) 注意,替换操作编辑距离为2
    • 整合: 这一步就是对上述所有路径求最小值(或者最大值)

所以最后的转移方程如下:

image

最后,得到的dp表如下:


dp_table.png

添加Backtrace来记录如何转化的:

backtrace.png

时间、空间复杂度

时间复杂度: O(nm)

空间复杂度: O(nm)

Backtrace : O(n+m)

带权编辑距离

带权编辑距离只是将delete insert subtitude 三个操作用一个权值函数表示,整个动态规划的过程并没有改变。

生活 转载请联系作者,并注明出处。

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

春光支付宝

支付宝

春光微信

微信


喜欢  |  0

0条评论