首页 > 编程学习 > 迈尔斯差分算法

迈尔斯差分算法

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

文章目录

      • 说点什么
      • 算法简介
      • 算法
        • 名词解释
        • 将字符串转换用图表示出来
      • 算法中的几个定义
        • 1. Snake(蛇形线)
        • 2. d contours(d步轮廓线)
        • 3. K线
          • 解释看不懂,一看图就明白了:
      • 算法的原理
        • ZERO:怎样才能解决问题
        • 第一步:如何走(迭代)
        • 第二步:每一步如何走
        • 第三步:每条K线上如何走到最远点
        • 第四步:走好前两步
        • 最后一个问题:我们能走出第一步吗?
      • 引用,参考
            • 我的个人博客,有空来坐坐

说点什么


最近在关注Git diff的原理,其实就是将一个文件转换成另一个相似文件的过程。再简化一定就是如何将一个字符串转化成另一个字符串的问题。只不过文件转换的时候操作的原子是一行数据,字符串转换操作的原子是一个字符。

算法简介


来源:Eugene W. Myers的一篇论文,于1986年11月发表在“Algorithmica”杂志上
An O(Nd) difference Algorithm and Its Variations
思想:贪心算法 + 动态规划

算法


名词解释

  1. 字符串A 和 字符串B
     我们的目标是将A转换成B,这里要注意,A和B应该比较相似,这样才能体现出diff,如果两个字符串毫无关系,那么这个算法是没有意义的。
  2. Shortest Edit Script(SES)
     最短编辑次数,就是我们最少经过几次删除(删除的是A中的字符)和新增(新增B中的字符)操作,才能完成转换
  3. Longest Common Subsequence ( LCS )
     最长公共序列,不同于Longest Common Substring(最长公共子串),LCS不要求相同字符必须相连,比如AdBABC的LCS是AB

不难发现,2和3之间是有关联的,一般一个LCS会对应一个SES,而LCS也可能有多个(比如ABCACBABAC都是LCS),所以这个算法,并不是唯一解的。

将字符串转换用图表示出来

  • 图表示
  • 字符串A:ABCABBA
  • 字符串B:CBABAC
    其中,x轴代表字符串A,长度N = 7,y轴代表字符串B,长度M = 6

图的基本操作:

  • 横着走:表示删除字符串A中的元素
  • 竖着走:表示增加字符串B中的元素
  • 斜着走:表示此处AB的元素是一致的,不需要删除也不需要新增

算法中的几个定义


1. Snake(蛇形线)

  • 蛇形线

图解:

左上角当作是(0, 0)

从(0,0)到(0,1)是蛇形线(竖着走一步)

从(0,0)到(1,0)也是蛇形线(横着走一步)

从(1,0)到(2,0)再到(3,1)整体也是蛇形线

通俗的讲:蛇形线就是 单个长度的横着走或者竖着走 + 任意长度的斜着走
数学角度来讲:单个删除或插入,后跟零个或多个对角线。

2. d contours(d步轮廓线)

  • 1步到达轮廓

可以看出,从(0,0)开始,走一步,分别可以到达(1,0)和(0,1)

  • 2步到达轮廓

在第一步的基础上,再走一步(一个蛇形线)发现可以到达三个地点,到达点的连线就是所说的轮廓

d表示一个量词,表示1,2,3…
d contours表示d步可以走到的点的连线,横着走一格或者竖着走一格都是一步,斜着走不算步数(其实就是走一个蛇形线)

3. K线

  • 与对角线平行的直线,不要受坐标限制,注意是直线

  • (0,0)点的K线定义成 K = 0 K = 0 K=0K向右增加,向左减少,(0,1)处 K = − 1 K = -1 K=1,(1,0)处 K = 1 K = 1 K=1

  • 数学表示: k = x − y k = x - y k=xy

解释看不懂,一看图就明白了:

K线

算法的原理

ZERO:怎样才能解决问题

如何解决问题

当到达上图中的右下角时就找到了一个解决方案,但是不能随便走,只有字符串相同时才能够走斜线。d的最大值时 N + M N + M N+M(即字符串A和字符串B完全不同),这个时候就需要N个删除M个插入

这里需要特别注意的是:

d步的起点是d-1步的终点,即走下一步的时候是以上一步的终点为起点的。

确定了解决问题的方式:

不断增加d直到,到达右下角,而我们找这个点,其实也就是找在K线上最远的距离

第一步:如何走(迭代)

迭代的计算,不同的d在K线上到达的最远距离。当到达右下角时就找到了一个解决方案。d的最大值时 N + M ​ N + M​ N+M(即字符串A和字符串B完全不同),这个时候就需要N个删除M个插入

这里需要特别注意的是:

d步的起点是d-1步的终点,即走下一步的时候是以上一步的终点为起点的。

// 我们确认使用迭代的方式寻找能走到右下角的步数,0 开始,最大是 (N + M)
for (int d = 0; d <= N + M; d++)

第二步:每一步如何走

定理:对于给定的d,可以到达的唯一** k k k**行位于 [ − d . . + d ] [-d .. +d] [d..+d] 范围内
当所有移动都向下时,最远会有 k = − d k = -d k=d ,而当所有移动都在右边时, k = d k = d k=d 是最远的边界

多想一点:d如果是奇数,那么是不是只能走到奇数值的K线上???

如何解决问题
如图,走1步的话,只能走到K = 1 或者 k = -1处,走两步只能走到**-2,0,2**处

//  我们确认了要计算多少条K线
for ( int k = -d; k <= d; k += 2)

第三步:每条K线上如何走到最远点

思考:

  1. 想要走到一个** K K K线上,只能从 K + 1 K+1 K+1 向下走,或者从 ​ K − 1 K-1 K1** 向右走
    d d d的起点是 d − 1 d - 1 d1 步 的终点,即走下一步的时候是以上一步的终点为起点的。(回忆一下)
  2. 如果我们知道 d − 1 d - 1 d1 中,到达各个K线的最远距离,那么我们就能知道d步可以到达的最远点

如何走:

  1. 如果 K = − d ​ K = -d​ K=d ,只能通过往下走
  2. 如果 K = d K = d K=d ,只能往右走
    这是两种边缘的情况,试想走d步,想要到达K或者-K,只能一直朝着一个方向走
  3. 如果 K K K 位于 − d -d d d d d 之间,我们遵循先删除的原则,如果** ( k − 1 ) (k -1) k1处的x值 小于 ( k + 1 ) (k + 1) k+1的x值**,就向下移动(因为此时,在 d − 1 d-1 d1 步的时候,发生了删除)
    当然这里也可以遵循先增加的原则,那么就需要选择向右移动
// V[K - 1]表示在K-1这条线上,x轴的值
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
// 要注意的是,无论向哪个方向走,都需要判断接下来是否有相同的字符,如果有就能走的更远

第四步:走好前两步

如何解决问题

  1. 走第一步的时候, d = 1 ​ d = 1​ d=1,根据上面第二步的分析,我们需要考虑 k = − 1 , 1 ​ k = -1,1​ k=11 k = − 1 ​ k = -1​ k=1时向下((0,0)=> (0,1)), k = 1 ​ k = 1​ k=1向右((0,0)=>(1,0))
  2. 走第二步的收, d = 2 d = 2 d=2,需要考虑 k = − 2 , 0 , 2 k = -2,0,2 k=202
  • k = − 2 ​ k = -2​ k=2 时,需要往下(0,1)=>(0,2),但是这时候还不算结束,因为两个字符串中有相同的字符,可以斜着走,所以最终是(0,1)=>(0,2)=>(2,4)
  • k = 0 k = 0 k=0 时, V [ K − 1 ] V[ K - 1] V[K1] = V [ − 1 ] V[ -1 ] V[1] = 0, V [ k + 1 ] V[ k + 1 ] V[k+1] = V [ 1 ] V[ 1 ] V[1] = 1,根据我们第三步的想法,需要向下((1,0)=>(1,1)),此时发现还可以斜着走,最终(1,0)=>(1,1)=>(2,2)
  • k = 2 k = 2 k=2 时,k = d,所以向右,也可以斜着走,所以(1,0)=>(2,0)=>(3,1)

最后一个问题:我们能走出第一步吗?

 从上面了解到每次走都需要依靠上一步的最远到达点,但是第一步怎么办,去依赖谁?

为了解决这个问题,我们需要为 d = 0 d = 0 d=0 设定一个起点,我们设置** V [ 1 ] = 0 V[1]= 0 V[1]=0,这表示 k = 1 k = 1 k=1 线上, x = 0 x = 0 x=0** 的点,所以这个点是(0,-1)。
我们需要做的就是保证从这一点向下移动,把我们带到(0,0)点
结合上面的分析,当 d = 0 d = 0 d=0 时, k = 0 k = 0 k=0,这个时候向下移动, 发现是可以将我们带回(0,0)点的

就是那个点

引用,参考


CodeProject - Investigating Myers’ diff algorithm

我的个人博客,有空来坐坐

http://www.wangyanan.online

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000