写这篇文章，
一、DiffUtil 对比列表item 数据，git 文件对比都用到了这个算法。
二、发现国内的博客，帖子，对这个算法的描述很少很少，算法本身又难以理解。
三、上篇DiffUtil 源码分析时遇到了这个算法，我觉得程序员不能怕算法，要跟算法死磕到底，要往下挖源码。
书读百遍其义自现，阅读算法代码也是如此。
对比原则和图画结合
两个字符串,a = "ACBA" b = "CBA"对比这两个字符的差异，有什么发现？
你会脱口而出 ：
a 比 b 最前面多了一个"A"
为什么不是:
第一位，A≠C,第二位，C≠B,第三位，B≠A,第四位，b少了一位
由此得到我们对比的原则（我总结的）：
- 计算最大重合部分（"CBA"），改变字符最小的原则。
用图片表示，画上斜线的格子就是重合的部分（"CBA"）。（注意这张图片，这个算法是用表格的方式理解的）
ACBA.png
我们最开始的描述： 第一位多了一个"A"，其余不变，是改变最小的
图表的描述就是：x 方向(向右)一步，其余斜线，是横纵走得最少的。
- 向右一步=增加了 "A"，改变最小=横纵走得最少
看图：
ACBA.png
新数据a = "AB" 比上 b= "BB"
有两条最短路径，向右一步，向下一步或者向下一步，向右一步。
我们选择向右一步向下一步的，图表的方式是：向右一步再向下一步，其余斜线。我们的描述是：新数据a相对于旧数据b，第一位增加了a中的A，减去了b中的B，其余不变。
- 向下=减去
上面能做到图画，和逻辑结合了，请看下面这样一个问题：
a = "ABCABBA"
b ="CBABAC"
a的长度7，b的长度等于6
aa.png
它的最小改变的描述是如何？
这个问题可以改成，从 起点 （0，0）到 终点（7，6）的最短横纵路径是怎么走？
aa.png
一目了然，当黄色路径达只要五步就到达的时候，其他路径还没有到达。
迈尔斯的 diff 算法就是比较快速求出这样一条路径的算法。
提出概念
（需要结合图画理解，这些概念的提出是为计算和表达方便，涉及数学，类似设个x ,设个y 的未知数）
snake :一步所走的路径 为 snake，有所不同的是，snake 分为三个点，起点，中点，终点，
一般走一步没有遇到斜线，中点就是终点， 遇到了的话，路径就包含了斜线 ,终点坐标计算也要包含斜线的坐标。k ： 定义x 轴向右增大，y轴 向下增大，定义 k = x-y；
d ： 定义为步数。
看下图：
2566000-f8f59baffd4eb418.png
黄色的线：k线 （注意这些线）
深蓝色的线：snake
浅蓝色的数字：d (步数)
红色的线：算法求出的问题的解（其实这个解有多个这只是求了其中一条）
怎么冒出来的这个k？ 所有k相同的点组成了一条线，他们组成了对角线。并且对于k，我们可以使用一个记录的数组V，用k作为该数组的index，x为value，这样我们可以计算求得 y值
这个算法父问题的求解归结为子问题的求解。要知道d=5时所有k对应的最优坐标，必须先要知道d=4时所有k对应的最优坐标，要知道d=4时的答案，必须先求解d=3，以此类推。
思考：
如何使用最小d（步数） 到达终点（N，M），可以得到外循环。
接下来我们想想如何到达point（x，y）？ 设 k = x - y，那么能到达点（x，y）的 只能从k-1 或者 k+1两条对角线上到k上，步数的递增，内循环应该是k ，内层循环完毕的结果就是，在步数为d，求得对角线k能到达的最远的x坐标。每向下或向右一步，坐标必然会从一条k线上移动到另外一条k线上，也就是说步数固定情况下，k的改变，我们可以求出相应的移动方向从而确定路径，内循环就是k递增，找到最快一条到达终点（N,M）的路，目的就达成了
上伪代码好好理解下：
2566000-b2db4ffe4e5d7e1f.png
伪码分析
一般到这里就会很多的疑惑，很懵逼：
我们拆分下：
-
最外面这个循环
//d 是步数，N 是字符的长度6 ，M 是字符长度7 , //纵然 d 一直右向，再向下，经过斜线，也是大于不了N+M 的 for (int d = 0; d<= N +M ;d++){ ··· } -
里面这层循环
- k = x-y ； 我们可以通过x 求y ，v[]数组里面以k为index,存储最优坐标的x值，取的时候只要知道k值，因为v[k] =x;通过有y =v[k]-k 就可以算出y；
k 结合图形，我们从（0,0）开始，每次只增长一步，向下一步=>k-1，向右一步=>k+1；
第一步：k的极限，k-1<= k <=k+1
第二步：k的极限，k-2<= k <=k+2
第d步： k的极限，k-d<= k <= k+d最短d步到达终点（x,y），假设途中经过 一个 3个斜线，经过横线 i 个,经过竖线 j 个
则x = i+3,y = j+3;终点:（x，y）=>（i+3，j+3）
假设 d 是奇数，i+j 必然是奇数
由k = x-y = i +j +6;
得k 为奇数，d 为奇数，k 只能为奇数，
所以内循环时 ，k +=2（看图，这句话的意思是一个方格不能从对角线到对面的点，不是向下，就是向右）
// 每一步递增
for (int d = 0; d<= N +M ;d++){
//在每一步下面的各个k的取值，k+=2 （见上面地三点）
for( int k = -d ;k <= d ;k +=2){
// 是否向下
//这里注意看图上黄色斜线，起点k=0时；k= -1 是向下一步，当k=-d 时必然向下 ，k=d 必然向右，第一步d=1 ,k=-1向下，k = 1 向右。
//v[ ]数组保存了k上的 x ，看图， 从第一步完成后，执行第二步，d =2 ,k = - 2, 0 ,2三个数，
// k = -2 时，向下; k = 0 ，(这时右边的k线 => v[k+1] =1(第一步记录v[ ]为1)，左边的k线 => v[k-1] =0(第一步结束时记录为零)，
// 所以向下，k =2 , v[k+1] = 0(没有保存) v[k-1] = 1（第一步保存为1）
// 这样写的好处，以k 为基准进行的移动，不会出现重复的情况
bool down = ( k== - d || (k !=d && v[k-1] < v[ k+1] ));
···
//save end point
//保存对应k 的x方向的值（这里的x向右0到7，y向下0到6 ）= 保存d步结束，对应k值上的终点坐标；
//终点坐标(x,y)=> （x=v[k]，y= v[k]-k）
v[k] = xEnd;
}
}
-
整个伪码流程
//新建集合，用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){ //跳出循环 } } }
如果看了我注释还是没有懂，我推荐几个网址：
外文的博客,加载有点慢
从DiffUtil到Myers'差分算法
Git是怎样生成diff的：Myers算法
java实现
算法的论文
如果还没有懂，结合图案，多读几遍，注意他的每走一步其实就是k线上切换。
网友评论