Diff 在Linux下非常有用, 最近在對定向蜘蛛的研究中, 發(fā)現(xiàn)網(wǎng)頁的信息大部分在Diff部分, 所以考慮了Diff的原理.

1. Unix Diff

Linux Diff 的基本原理在文 [ Dynamic Programming | http://www.sbc.su.se/~pjk/molbioinfo2001/dynprog/dynamic.html ] 中介紹的很詳細了.如果一個文件有n行, 則需要對一個n*n的矩陣進行計算以得到最佳匹配.


2. 貪心算法

在[ Windiff原理初探 | http://www.2maomao.com/blog/how-windiff-works-continued-1/ ]中看到一個貪心算法, 感覺在某種情況下還是比較適合的,但是有些情況還是存在一些問題.

貪心算法的基本思路是: 從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達到某算法中的某一步不能再繼續(xù)前進時，算法停止。

首先還是簡化問題：每個行根據(jù)內(nèi)容映射到一個整型值, 這就將整個問題簡化為整形數(shù)組的比較，姑且稱之為Anew和Aold。

程序處理流程簡述：
while (還沒到頭)
{
?? while (還可以繼續(xù)找，還可以更貪心）
?? {
????? 找到下一個匹配的（依次對ANew的元素，查找其在AOld中的位置）
????? if (找的到)
???????? 計算其貪心值，如果當(dāng)前更貪則用這個匹配做當(dāng)前最佳匹配
????? else
???????? break;
?? }
}
輸出剩余的未匹配節(jié)點。

其中“還可以更貪心”是如何判定的呢？

首先定義左臂（leftHand，Anew里面新匹配位置距上一次被采用的匹配的距離），右臂（rightHand，Aold里面新匹配位置距上一次被采用的匹配的距離）。

要找一個目標(biāo)，在這里我給定的目標(biāo)是左右平衡情況下的最近匹配。比如一個匹配左臂1，右臂10，另一個匹配是左臂3，右臂3，這時候傾向于選擇后一個匹配。
為了公式化和便于計算，我采用一個簡單的具有這個邏輯的函數(shù)：leftHand*leftHand + rightHand*rightHand的值（貪心值）最小。

定義了這個目標(biāo)以后，你會發(fā)現(xiàn)只要左臂過長，lefthand自身的平方超過上個候選匹配的貪心值，則可以停止往下計算了。

然后這個循環(huán)繼續(xù)下去，直到找到所有的匹配，對每兩個匹配之間，如果有內(nèi)容，則表示有Add/Delete/Modify發(fā)生，根據(jù)左臂右臂是否為0可以明顯區(qū)分。

舉個例子：
Anew Aold
1???? 1
2???? 1
3???? 3
2???? 2
4???? 4
首次匹配找到1<-->1，匹配立即停止，因為1*1 + 1*1 = 2，2*2 > 2，所以沒有比較進行下去了.

然后往下找到2<-->2，這時候左臂等于1，右臂等于3，（注意臂長是相對上一次被采用的匹配的），1*1 + 3*3 = 10，當(dāng)前貪心值是10；然后往下找到3<-->3，左臂為2，右臂為2，2*2 + 2*2 = 8，這個匹配優(yōu)于上一個匹配；然后繼續(xù)往下找到2<-->2（左邊第二個2），左臂3，右臂3，3*3本身的平方已經(jīng)超過目前的貪心值8，沒有必要再繼續(xù)往下匹配，這一輪匹配查詢結(jié)束。

這里可以看出采用平方和做貪心算式的好處，很快可以收斂，而且符合“左右平衡”以及“最近匹配”。
后面2和4的分析略去。

但是這個算法存在一個問題,它的算法只針對單行最優(yōu), 而無法實現(xiàn)多行的最優(yōu), 比如
Anew Aold
a??? a
b??? a
c??? b

像上面的兩個文件, Anew:1 匹配 Aold:1, 但是應(yīng)該使 Anew:1 匹配 Aold:2, 這樣子才可以使Anew中序列ab 與 Aold的序列ab匹配.


3. 下一步工作

?* 調(diào)整貪心值計算函數(shù)
?* 貪心算法 + 部分動態(tài)規(guī)劃