首页 > 编程学习 > Myers差分算法分析

Myers差分算法分析

发布时间:2022/1/17 12:36:53

目录

  • 论文地址
  • 摘要
  • 定义
  • 编辑图
  • 解决方案
  • 概念
  • 贪婪算法
  • 最优坐标
  • snake坐标组
  • 算法实现(伪代码)

论文地址

paper论文地址: https://neil.fraser.name/writing/diff/myers.pdf

摘要

对于两个序列A、B,寻找其最长公共子序列的问题与寻找其最短编辑过程(从A到B)的问题一直被认为是一对对偶问题。
本文证明了它们等价于在一个编辑图中找到最短/最长路径。
基于这个观点,我们找到了一个简单的O(ND)时间与空间复杂度的算法,其中N为A与B的长度和,D为AB间最短编辑过程的长度

定义

在这里插入图片描述

编辑图

本文使用与论文相同的示例。
文件A包含 ABCABBA,文件B包含CBABAC。
这些被表示为两个字符数组:A []和B []。
A []的长度为N,B []的长度为M。

我们就可以求解从A数组变成B数组的问题,转换成为求解从A字符串变成B字符串的问题。
在这里插入图片描述

解决方案

解决问题:从左上角(0,0)到右下角(7,6)的最短路径。

动态规划解决方案
当一个问题
(1)依赖于子问题的最优解
(2)子问题重叠
(3)问题存在边界
(4)子问题独立
就可以考虑使用动态规划来解决。

该问题中,点(n,m)的最优解依赖于(n,m-1),(n-1,m)两个点所在对角线上所有能够走一步到达(n,m)的点。可以使用动态规划求解。

Myers差分解决方案:

数组A沿x轴放在顶部。数组B沿y轴向下放置。

始终可以水平或垂直移动一个字符。
水平(右)移动表示从文件A中删除,垂直(向下)移动表示在文件B中插入。
如果存在匹配的字符,则还可以对角移动,以匹配结束。
解决方案是尽量走对角边让操作变得最少,目的是走到右下角。只要 A[i] == B[j] 那么 (i,j) 就可以从 (i-1, j-1) 走过来,否则只能从 (i-1, j) 或者 (i, j-1) 走过来,所以一碰上 A[i] == B[j] 的话,就存在了一条斜边。

LCS是轨迹中的对角线,SES是轨迹中的水平和垂直移动。例如,LCS的长度为4个字符,SES的长度为5个差异。
在这里插入图片描述

概念

根据 Myers 的论文,他提出了三个概念:

snake : 一条snake代表走一步。例如从(0,0)->(0,1) / (0,0)->(1,0) / (0,1)->(0,2)->(2,4) 这分别为三条snake,走对角线不计入步数。

k line: 定义 k = x - y (好吧,我习惯写成 y = x - k,这是相同斜率的平行斜线组成的一个集合)

d contour: 走一步算一个 d

贪婪算法

该算法是迭代的。它计算连续 d 的每条 k 线上最远的到达路径。当路径到达右下角时,将找到解决方案。

这里面有很重要的几点:

  1. 路径的终点必然在k线上。迭代进行,所以k线的上一步操作是k+1向下移动或者k-1向右移动;

  2. 计算连续的d每条k线上最远的到达路径(偶数d的端点在偶数k线,奇数类似);

  3. 路径到达右下角结束;

其中1和2都是在论文中进行了证明!

k line:棕色线是k的奇数值的k条线。黄线是k的偶数值的k线。

snake:深蓝色的线条是蛇。红蛇显示溶液痕迹。

d contours:淡蓝色的线是差异轮廓。
例如,标记为“ 2”的直线上的三个端点全部具有2个水平或垂直移动。
在这里插入图片描述

外循环次数
从(x、y)组成的矩形左上角,到右下角。最长的路径莫过于所有对角线都不经过。也就是只走X和Y的长度即最大长度=N+M。
for ( int d = 0 ; d <= N + M ; d++ )

内循环的次数
在此循环内,我们必须为每条k线找到最远的到达路径。对于给定的d,只能到达的k线位于[-d … + d]范围内。
当所有移动都向下时,k = -d 是可能的;
当所有移动都在右侧时,k = + d 是可能的。
for ( int k = -d ; k <= d ; k += 2 )
看到这里也许就有人产生疑问,为什么是k+=2?因为d和k同奇同偶!

最优坐标

我们可以得到每一步d的最优坐标组,如下图所示
在这里插入图片描述

snake坐标组

我们发现d和k同奇同偶!最短路径就是红色标识路径。
举例说明(d=3)
从d = 3的示例进行研究,这意味着k的取值范围是[-3,-1,1,3]

k = -3:这种情况下,只有当k = -2,d = 2时,向下移动一步(k = -4, d = 2这种情况不存在)。所以,我们可以这么来走,从(2,4)点开始向下走到(2,5),由于(2,5)和(3,6)之间存在一个对角线,可以走到(3,6)。所以着整个snake是:(2,4) -> (2,5) -> (3,6)。

k = -1:有两种情况需要来讨论:分别是k = 0,d = 2向下走;k = -2 ,d = 2向右走。

当k = 0,d = 2时,是(2,2)点。所以当从(2,2)点向下走一步,到达(2,3),由于(2,3)没有对角线连接,所以整个snake是:(2,2) -> (2,3)。
当k = -2 ,d = 2时,是(2,4)点。所以当从(2,4)点向右走一步,到达(3,4),由于(3,4)与(4,5)存在对角线,所以整个snake是:(2,4) -> (3,4) -> (4,5)。
在整个过程中,存在两条snake,我们选择是沿着k line走的最远的snake,所以选择第二条snake。
在这里插入图片描述

算法实现(伪代码)

//新建集合,用k值保存对应的x
v[ 1 ] = 0; 
 //步数递增
for (int d= 0; d <= N+M ;d++){
    //每一步下面的各个k 的取值循环,    
    for( int k = -d ; k <= d ; k+=2){
        // 是否向下
        bool down = ( k== - d || (k !=d && v[k-1] < v[ k+1] )); 
        //得到上次移动的k,如果这次向下,上次的kPrev = k+1;
        int kPrev = down ? k+1 : k -1; 
        //起点,因为每次移动保存是 k+2 ,所以如果这次的index全是奇数,上一次就全是偶数,在一个数组里面不会进行覆盖
        int xStart = v[kPrev]
        int yStart = xStart - v[kPrev]
        //中点,之前说的,如果没有遇到斜线,它是等于终点的
        int xMid = down ? xStrat : xStart +1;
        int yMid = xMid - k;
        //终点,没有遇到斜线的样子
        int xEnd = xMid;
        int yEnd = yMid;
        //斜线数量
        int s= 0
        //这就是遇到斜线,只有数据相等,才会是斜线,然后,x,y 各加一
        while(xEnd < N && yEnd <M && A[xEnd] ==B[yEnd]){
            xEnd++;
            yEnd++;
            s++;
        }
        // 保存到数组
        v[k] = xEnd;
        //到了最终点(N,M),找到了最短步数的方案
        if(xEnD >= N && yEnd > = M){
          //跳出循环  
        }
    }     
} 
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000