Diff 在Linux下非常有用, 最近在對(duì)定向蜘蛛的研究中, 發(fā)現(xiàn)網(wǎng)頁(yè)的信息大部分在Diff部分, 所以考慮了Diff的原理.
1. Unix Diff
Linux Diff 的基本原理在文 [ Dynamic Programming | http://www.sbc.su.se/~pjk/molbioinfo2001/dynprog/dynamic.html ] 中介紹的很詳細(xì)了.如果一個(gè)文件有n行, 則需要對(duì)一個(gè)n*n的矩陣進(jìn)行計(jì)算以得到最佳匹配.
2. 貪心算法
在[ Windiff原理初探 | http://www.2maomao.com/blog/how-windiff-works-continued-1/ ]中看到一個(gè)貪心算法, 感覺(jué)在某種情況下還是比較適合的,但是有些情況還是存在一些問(wèn)題.
貪心算法的基本思路是: 從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。
首先還是簡(jiǎn)化問(wèn)題：每個(gè)行根據(jù)內(nèi)容映射到一個(gè)整型值, 這就將整個(gè)問(wèn)題簡(jiǎn)化為整形數(shù)組的比較，姑且稱(chēng)之為Anew和Aold。
程序處理流程簡(jiǎn)述：
while (還沒(méi)到頭)
{
?? while (還可以繼續(xù)找，還可以更貪心）
?? {
????? 找到下一個(gè)匹配的（依次對(duì)ANew的元素，查找其在AOld中的位置）
????? if (找的到)
???????? 計(jì)算其貪心值，如果當(dāng)前更貪則用這個(gè)匹配做當(dāng)前最佳匹配
????? else
???????? break;
?? }
}
輸出剩余的未匹配節(jié)點(diǎn)。
其中“還可以更貪心”是如何判定的呢？
首先定義左臂（leftHand，Anew里面新匹配位置距上一次被采用的匹配的距離），右臂（rightHand，Aold里面新匹配位置距上一次被采用的匹配的距離）。
要找一個(gè)目標(biāo)，在這里我給定的目標(biāo)是左右平衡情況下的最近匹配。比如一個(gè)匹配左臂1，右臂10，另一個(gè)匹配是左臂3，右臂3，這時(shí)候傾向于選擇后一個(gè)匹配。
為了公式化和便于計(jì)算，我采用一個(gè)簡(jiǎn)單的具有這個(gè)邏輯的函數(shù)：leftHand*leftHand + rightHand*rightHand的值（貪心值）最小。
定義了這個(gè)目標(biāo)以后，你會(huì)發(fā)現(xiàn)只要左臂過(guò)長(zhǎng)，lefthand自身的平方超過(guò)上個(gè)候選匹配的貪心值，則可以停止往下計(jì)算了。
然后這個(gè)循環(huán)繼續(xù)下去，直到找到所有的匹配，對(duì)每?jī)蓚€(gè)匹配之間，如果有內(nèi)容，則表示有Add/Delete/Modify發(fā)生，根據(jù)左臂右臂是否為0可以明顯區(qū)分。
舉個(gè)例子：
Anew Aold
1???? 1
2???? 1
3???? 3
2???? 2
4???? 4
首次匹配找到1<-->1，匹配立即停止，因?yàn)?*1 + 1*1 = 2，2*2 > 2，所以沒(méi)有比較進(jìn)行下去了.
然后往下找到2<-->2，這時(shí)候左臂等于1，右臂等于3，（注意臂長(zhǎng)是相對(duì)上一次被采用的匹配的），1*1 + 3*3 = 10，當(dāng)前貪心值是10；然后往下找到3<-->3，左臂為2，右臂為2，2*2 + 2*2 = 8，這個(gè)匹配優(yōu)于上一個(gè)匹配；然后繼續(xù)往下找到2<-->2（左邊第二個(gè)2），左臂3，右臂3，3*3本身的平方已經(jīng)超過(guò)目前的貪心值8，沒(méi)有必要再繼續(xù)往下匹配，這一輪匹配查詢(xún)結(jié)束。
這里可以看出采用平方和做貪心算式的好處，很快可以收斂，而且符合“左右平衡”以及“最近匹配”。
后面2和4的分析略去。
但是這個(gè)算法存在一個(gè)問(wèn)題,它的算法只針對(duì)單行最優(yōu), 而無(wú)法實(shí)現(xiàn)多行的最優(yōu), 比如
Anew Aold
a??? a
b??? a
c??? b
像上面的兩個(gè)文件, Anew:1 匹配 Aold:1, 但是應(yīng)該使 Anew:1 匹配 Aold:2, 這樣子才可以使Anew中序列ab 與 Aold的序列ab匹配.
3. 下一步工作
?* 調(diào)整貪心值計(jì)算函數(shù)
?* 貪心算法 + 部分動(dòng)態(tài)規(guī)劃