编辑距离衡量两个字符串S和T相似程度的一种度量方法。

编辑距离定义:将字符串S通过插入、删除、替换三种编辑操作,转变为字符串T,所需最少的编辑次数。

计算编辑距离的问题,符合动态规划的几个特征:

  • 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
  • 无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
  • 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

因此考虑用动态规划求解。

设字符串S,T长度分别为m, n,记S(i)为S从第1个字符到第i个字符之间的子串。S(0)表示空串,S(m)表示S本身。

因此,S和T间的编辑距离,可由S(i)和T(j)的编辑距离计算而来。

递推公式为:

具体的算法参见维基百科。

这个算法的特点是,S和T字符串左边始终是对齐的。为了更好地理解这个算法中的递推公式,我们把两个字符串按照特定方式对齐。

以字符串S=ALGORITHM和T=ALTRUISTIC为例:

S和T的字符对齐方式为,假设我们已经知道最优的编辑方式:

  • 如果删去S中字符,则该字符对齐T中的空格
  • 如果删去T中字符,则该字符对齐S中的空格
  • 如果替换S中字符为T中字符,则这两个字符对齐

这种对齐方式有助于我们理解上述递推公式。

首先,我们不需要理会S和T左端是否对齐。

其次,注意到S(i)和T(j)的右端,只有三种可能性:

  • S(i)右端在T(j)右端的右侧
  • S(i)右端正对着T(j)右端
  • S(i)右端在T(j)右端的左侧

这也是上述递推公式三种可能性的由来。

参考:Section5.5 — http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-dynprog.pdf

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注