算法设计与分析课件 30 编辑距离

算法设计与分析本节要点CONTENTS编辑距离编辑距离人类的DNA由4个基本字母{A，C，G，T}构成，包含了多达30亿个字符。如果两个人的DNA序列相差0.1%，仍然意味着有300万个位置不同，所以我们通常看到的DNA亲子鉴定报告上结论有：相似度99.99%，不排除亲子关系。怎么判断两个基因的相似度呢？生物学上给出了一种编辑距离的概念。编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。怎么找到两个字符串x[1，…，m]和y[1，…，n]的编辑距离呢？编辑距离例如：X=（A，B，C，D，A，B），Y=（B，D，C，A，B）。如果穷举，有很多种对齐方式，暴力穷举是不可取的。那么怎么找到编辑距离呢？首先考虑能不能把原问题变成规模更小的子问题，如果可以，就会容易得多。求X={x1，x2，x3，…，xm}和Y={y1，y2，y3，…，yn}的编辑距离，可以求其前缀Xi={x1，x2，x3，…，xi}和Yj={y1，y2，y3，…，yj}的编辑距离，当i=m，j=n时就得到了所有字符的编辑距离。编辑距离那么能不能用动态规划算法呢？下面我们分析该问题是否具有最优子结构性质。（1）分析最优解的结构特征假设已经知道d[i][j]是Xi={x1，x2，x3，…，xi}和Yj={y1，y2，y3，…，yj}的编辑距离最优解。这个假设很重要，我们都是这样假设已经知道了最优解。那么两个序列无论怎么对齐，其右侧只可能有如下3种对齐方式：编辑距离结构定义1)需要删除xi，付出代价1，那么我们只需要求解子问题Xi={x1，x2，x3，…，xi-1}和Yj={y1，y2，y3，…，yj}的编辑距离再加1即可，即d[i][j]=d[i−1][j]+1。d[i−1][j]是Xi−1和Yj的最优解。编辑距离结构定义2)需要插入yj，付出代价1，那么我们只需要求解子问题Xi={x1，x2，x3，…，xi}和Yj={y1，y2，y3，…，yj-1}的编辑距离再加1即可，即d[i][j]=d[i][j−1]+1。d[i][j−1]是Xi和Yj-1的最优解。编辑距离结构定义3)如果xi=yj，付出代价0，如果xi≠yj，需要替换，付出代价1，用函数diff(i,j)来表达，xi=yj时，diff(i,j)=0；xi≠yj时，diff(i,j)=1。那么只需要求解子问题{x1，x2，x3，…，xi−1}和{y1，y2，y3，…，yj−1}的编辑距离再加diff(i,j)即可，即d[i][j]=d[i−1][j−1]+diff(i,j)。d[i−1][j−1]是Xi−1和Yj−1的最优解。编辑距离（2）建立最优值递归式设d[i][j]表示Xi和Yj的编辑距离，则取以上三者对齐方式的最小值。编辑距离递归式：编辑距离（3）自底向上计算最优值，并记录最优值和最优策略i=1时：{x1}和{y1，y2，y3，…，yn}中的字符一一比较，按递归式求解并记录编辑距离。i=2时：{x2}和{y1，y2，y3，…，yn}中的字符一一比较，按递归式求解并记录编辑距离。……i=m时：{xm}和{y1，y2，y3，…，yn}中的字符一一比较，按递归式求解并记录编辑距离。编辑距离（4）构造最优解如果仅仅需要知道编辑距离是多少，上面的求解过程得到的编辑距离就是最优值。如果还想知道插入、删除、替换了哪些字母，需要从d[i][j]表格中倒推，输出结果。编辑距离结构定义以字符串s1=”FAMILY”，s2=”FRAME”为例，求解它们的编辑距离。取上面+1，左侧+1，左上角数值+diff[i][j]三者最小值编辑距离构造最优解：从右下角开始，逆向查找d[i][j]的来源：上面（即d[i][j]=d[i−1][j]+1）表示需要删除，左侧（即d[i][j]=d[i][j−1]+1）表示需要插入，左上角（即d[i][j]=d[i−1][j−1]+diff[i][j]）要判断是否字符