Myers'diff
前言
在學(xué)習(xí)完上一篇文章Myers'Diff之貪婪算法 之后钦奋，我對(duì)Android源碼中的DiffUtil類進(jìn)行了閱讀發(fā)現(xiàn)其算法的實(shí)現(xiàn)和文章中的方式并不盡相同座云，而是在其基礎(chǔ)之上再次進(jìn)行的優(yōu)化。所以本篇文章是以上一篇Myers'Diff之貪婪算法 文章內(nèi)容基礎(chǔ)之上對(duì)它的變體進(jìn)行再次研究的過(guò)程付材。
上一篇文章Myers'Diff之貪婪算法 講述diff怎么從一個(gè)抽象的問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題朦拖，并對(duì)一些名詞做了專有的定義（為解決問(wèn)題的過(guò)程提供輔助），Myers'Diff之貪婪算法講述了利用輔助的k線進(jìn)行迭代求解厌衔，整改過(guò)程并不考慮時(shí)間和空間的消耗璧帝。所以這篇文章主要是在其基礎(chǔ)之上進(jìn)行時(shí)間和空間復(fù)雜度的優(yōu)化。
<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">
@TOC
逆向算法
Myers'Diff之貪婪算反 是從(0,0)到(N,M)進(jìn)行移動(dòng)的富寿，它的反向工作是從(N,M)到(0,0)睬隶。
從該圖可以看出，該解決方案不同于通過(guò)向前工作而生成的解決方案页徐，但是其LCS和SES的長(zhǎng)度相同苏潜。 但這是完全正確的，因?yàn)橥ǔ变勇？梢杂性S多等效的解決方案恤左，并且該算法只是選擇找到的第一個(gè)解決方案。
Delta
因?yàn)樾蛄?code>A和
B的長(zhǎng)度可以不同搀绣，所以正向和反向算法的k線可以不同飞袋。 將此差異作為變量delta = N-M隔離是有用的。在示例中链患，N = 7和M = 6給出了delta =1巧鸭。這是從前k行到后k行的偏移量。 您可以說(shuō)正向路徑以k = 0為中心麻捻，反向路徑以k = delta為中心纲仍。
Middle Snake
可以對(duì)D的連續(xù)值同時(shí)運(yùn)行正向和反向算法。在D的某個(gè)值處贸毕，兩條路徑將在k線上重疊巷折。 本文證明這些路徑之一是解決方案的一部分。 由于它將位于中間的某個(gè)地方崖咨，因此稱為中間路徑锻拘。
該示例的中間路徑在此圖中以粉紅色顯示：
這很有用，因?yàn)樗鼘?wèn)題分為兩部分击蹲，然后可以分別遞歸解決署拟。
這在空間上是線性的，因?yàn)橹挥凶詈蟮腣向量必須存儲(chǔ)歌豺，給出O（D）推穷。對(duì)于時(shí)間，此線性算法仍為O（（N + M）D）类咧。
這也有助于找到中間路徑馒铃，其D必須是正向和反向算法D的一半蟹腾。這意味著隨著D的增加，所需時(shí)間接近基本算法的一半区宇。
偽代碼：
for d = 0 to ( N + M + 1 ) / 2
{
for k = -d to d step 2
{
calculate the furthest reaching forward and reverse paths
if there is an overlap, we have a middle snake
}
}
Odd and Even Deltas
每個(gè)差異水平刪除或垂直插入都是從k行移到其相鄰行娃殖。由于增量是正向和反向算法中心之間的差異，因此我們知道需要檢查中間路徑的d值议谷。
對(duì)于奇數(shù)增量炉爆，我們必須尋找差異為d的前向路徑與差異為d-1的反向路徑重疊。
下圖顯示卧晓，對(duì)于delta = 3芬首，當(dāng)正向d為``2而反向d為1時(shí)發(fā)生重疊：
類似地，對(duì)于偶數(shù)增量逼裆，當(dāng)正向和反向路徑的差異數(shù)相同時(shí)郁稍，就會(huì)出現(xiàn)重疊。
下圖顯示胜宇，對(duì)于delta = 2艺晴，當(dāng)正向和反向 的 d均為2時(shí)，發(fā)生重疊：
因此掸屡，這是查找中間路徑的完整偽代碼：
delta = N - M
for d = 0 to ( N + M + 1 ) / 2
{
for k = -d to d step 2
{
calculate the furthest reaching forward path on line k
if delta is odd and ( k >= delta - ( d - 1 ) and k <= delta + ( d - 1 ) )
if overlap with reverse[ d - 1 ] on line k
=> found middle snake and SES of length 2D - 1
}
for k = -d to d step 2
{
calculate the furthest reaching reverse path on line k
if delta is even and ( k >= -d - delta and k <= d - delta )
if overlap with forward[ d ] on line k
=> found middle snake and SES of length 2D
}
}
-
(N+M+1) / 2從兩端同時(shí)出發(fā)封寞，意味著外循環(huán)次數(shù)大于等于最長(zhǎng)路徑的二分之一； - 如果
delta是偶數(shù)那么中間路徑在向前的方向中出現(xiàn)仅财； - 如果
delta是偶數(shù)那么中間路徑在向后的方向中出現(xiàn)狈究；
遞歸解決
我們需要以遞歸方法包裝中間路徑算法≌登螅基本上抖锥，我們需要找到一條中間的路徑，然后求解保留在左上角和右下角的矩形碎罚。
偽代碼：
Compare( A, N, B, M )
{
if ( M == 0 && N > 0 ) add N deletions to SES
if ( N == 0 && M > 0 ) add M insertions to SES
if ( N == 0 || M == 0 ) return
calculate middle snake
suppose it is from ( x, y ) to ( u, v ) with total differences D
if ( D > 1 )
{
Compare( A[ 1 .. x ], x, B[ 1 .. y ], y ) // top left
Add middle snake to results
Compare( A[ u + 1 .. N ], N - u, B[ v + 1 .. M ], M - v ) // bottom right
}
else if ( D == 1 ) // must be forward snake
{
Add d = 0 diagonal to results
Add middle snake to results
}
else if ( D == 0 ) // must be reverse snake
{
Add middle snake to results
}
}
我將在稍后解釋幾個(gè)邊緣情況磅废。
Edge case
上面的偽代碼需要考慮兩個(gè)邊界case，d=0和d=1荆烈。
如果中間路徑算法找到D = 0的解拯勉，則兩個(gè)序列相同。這意味著增量為零憔购，即為偶數(shù)宫峦。因此，中間路徑是一條正好匹配（對(duì)角線）的反向路徑玫鸟。因此导绷，我們要做的就是將這條路徑添加到結(jié)果中。
如果中間的路徑算法找到D = 1的解屎飘，那么就存在一個(gè)插入或刪除妥曲。這意味著delta是1或-1贾费，這是奇數(shù)，因此中間的路徑是前向路徑檐盟。 對(duì)于這種情況褂萧，我們可以通過(guò)計(jì)算d = 0對(duì)角線并將其與中間路徑一起添加到結(jié)果中來(lái)完成解決方案。
總結(jié)對(duì)比
這次的優(yōu)化還是以遞歸方法進(jìn)行的遵堵，與Myers'Diff之貪婪算法 的遞歸不同的是箱玷。這次的遞歸我們需要找到一條中間的路徑怨规，然后進(jìn)行左上角和右下角的矩形拆分陌宿，將拆分之后的矩形再進(jìn)行遞歸。O((M+N)lg(????M+N)+D2) 為最壞的情況波丰。時(shí)間約為 O(N + M)D) 其D必須是正向和反向算法 D的一半壳坪。這意味著隨著D的增加，所需時(shí)間接近基本算法的一半掰烟。
算法實(shí)踐：DiffUtil和它的差量算法
參考鏈接：
代碼:diff-match-patch
diff2論文
Myers diff alogrithm:part 1
Myers diff alogrithm:part 2
文章到這里就全部講述完啦爽蝴，若有其他需要交流的可以留言哦！纫骑！
