diff程式的算法

diff程式很重要，linux中的源代碼更新檔都是diff作出來的，diff在比較兩個文本檔案的不同方面很高效，它是基于行的，diff會将兩個檔案都按照行分成若幹部分，然後計算這些行每一行的校驗碼，之後的問題就是比較這兩個檔案的所有行的校驗碼序列的不同了，這就把問題歸結為了序列比對，diff用的是動态規劃算法，動态規劃和貪心算法相似，但是其思想卻是相反的，貪心算法保證每一步都是最小代價的，但是不能保證最終代價最小，而動态規劃每一步什麼也不知道，它從起點開始，隻管局部地按照要求将無所謂的結果鋪滿全局，然後回溯，在這些繁複的資料之間找到一條從開始到最後的一條路徑，為何這條路徑就是結果呢？因為每一步都符合要求，是以無論如何最終随便一條按照要求的回溯路線都符合要求，可是可以看出，這條回溯路線的結果是一個正确結果但是卻不是唯一的結果，正所謂條條大道通羅馬。和貪心算法一樣，随便的一條回溯路線不一定是最佳的，尋找最佳結果還要靠别的機制，貪心算法比動态規劃好的就是靠近最佳結果的幾率更大些，而動态規劃隻是一個結果，它旨在找到一種方案，然而動态規劃有自己的優勢，就是如果你的模型建的好，那麼它可以在每一步很輕松的情況下達到同樣的效果，關鍵就是模組化。

diff的算法就是一個動态規劃的例子，比如一個校驗碼序列P有M個元素，另一個Q有N個元素，它建構一個(M+1)*(N+1)的矩陣，然後引出一條蛇，蛇頭勇往直前，呵呵，其實就是往矩陣裡面的元素裡填數字，從(0,0)一直到(M+1,N+1)的大方向填數字，保證所填的數字單調增長，也就是填入的數字不能比它的參照值小，将要填入的是Vi,j,那麼它的參照值就是Vi-1,j-1，Vi-1,j和Vi,j-1，具體怎麼做到呢？V值的增加隻有一種可能性就是在Pi和Qj相等的情況下，其它情況下都是不增加的，是以Vi,j的值就是三者中最大的，Vi,j的參考值不是有三個嗎？那麼這種增加的情況和哪個參考值有關聯呢？事實上是和對角的那個，也就是和Vi-1,j-1,仔細想一下，隻有i和j同步增長才是P和Q的同步推進引起的比較，i和j的單獨推進隻是P序列或者Q序列的單獨向前推進，也就是說在序列比對的時候就是一個gap，這種方式填表很簡單，隻要有左上，上，左三個值就可以求出目前的這個值，每一步都是那麼的局部，最終填完後，找到最大的這個值的位置，很顯然是最右下角的這個，然後回溯，怎麼回溯呢？一個一個的找到目前值的前驅值所在的位置就可以了，最後将回溯的道路進行标注，得到了P和Q的兩條路徑，每寫一個字元，如果路徑和字元序列的方向垂直，那麼就寫一個空格，最終的結果就是diff的結果，很巧妙吧。不過以上的方式回溯寫出來的路徑不止一條，每一條路徑都是一個結果。

我們可以看出，每一步都是機械的既定規律的模仿，沒有什麼技巧可言，和貪心算法幾乎一樣，都是局部的，但是diff算法的每一步并沒有和全局的聯系起來，知道完成了整個填充之後才在回溯的時候和全局的結果相聯系，而貪心算法的每一個都記着自己在幹什麼，不需要回溯，這個意義上可以看出diff算法的填充過程更像是一個規整過程而不是一個十足的計算過程，貪心算法顯得一直很努力，而diff這裡所用的算法會耍一些技巧，你不是看不出我在做社麼嗎，别急，等會我回溯，一條路徑被勾勒出來了。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1273520