Myers差分算法分析
⽬录
连平中学论⽂地址
摘要
对于两个序列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向右⾛。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议