存档

文章标签 ‘分治与动规区别’

字符串相似度(编辑距离)

2012年6月13日 4 条评论

---

个人认为,大部分情况下,DP寻找子问题还是“从后向前”比较直观一些,像这道题目,个人觉得《编程之美》对它的分析就有些别扭,它“从前向后”寻求的子问题使得状态转移矩阵的初始化变得不太方便,不过“从后向前”分析和从前向后效果和原理都是一样的,本节通过三种实现方式来加深理解。

定义字符串的相似度有很多种度量,像前面说的最长公共子序列就是其中的一种,本节所说的“编辑距离”也算是一种,简单来说,编辑距离就是将两个字符串变成相同字符串所需要的最小操作次数。所需的操作可能有:

  1. 修改一个字符(如把“a”替换为“b”)
  2. 增加一个字符(如把“abdd”变为“aebdd”)
  3. 删除一个字符(如把“travelling”变为“traveling”)

例如,对于“abcdefg”和“abcdef”两个字符串来讲,可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的“编辑距离”。如何计算两个字符串的“编辑距离”?

鉴于DP自底向上求解子问题的性质,我们还是对字符串从后向前分析,这样寻找编辑距离的子问题比较直观,而且分解的子问题使得递归做备忘录变得容易理解,也使得自底向上实现时对状态转移矩阵的初始化更为简便易懂。

寻找子问题时,我们完全可以像分析最长公共子序列那样分析这个问题,我觉得它们是灰常相似的,都是“从后向前”看,假设有两个串X=abcdaex,Y=fdfax,它们的最后一个字符是相同的,只要计算X[1,…,6]=abcdae和Y[1,…,4]=fdfa的距离就可以了;但是如果两个串的最后一个字符不相同,那么就可以进行如下的操作来达到目的(xlen和ylen是X串和Y串的长度):

阅读全文...