前言

為什麼會寫這個，因為遇到了有意思的事情，簡而言之就是，面試某意向公司，沒過；其中一位面試官非常nice，還仔細看了我部落格，覺得是不是面試時沒展現出來，因此第二天專程打電話過來，給了我一個額外機會，就是花幾天時間做一個小專案，過幾天提交給他。

這是背景，專案是關於做一個工具，可以指定兩個目錄進行對比，如果某個檔案如a.txt在兩個目錄都存在，就對比其內容並呈現，呈現效果可以參考beyond compare或者git diff。

花了三天多時間編碼，兩天時間寫檔案，最終做了一個滿足需求的簡陋工具出來，幸不辱命吧；專案麻雀雖小，五臟俱全，也寫了需求分析檔案、概要設計、詳細設計等，專案本身也非常有意思，所以給大家分享一下。
其中一個核心點就是文字差異對比演演算法，因此先來篇文章講解一下，鋪墊鋪墊。

差異對比，很多人會想到beyond compare、git、svn等。這裡以git來說吧，git作為版本管理工具，真的也太方便了，很多時候想推薦給非網際網路行業的朋友們。

版本管理工具，最重要的一點就是不同版本的差異對比，看下圖：

從圖上來說，右邊那一行比左邊，就是多了幾個字元」xxxww「；但是對於軟體來說，怎麼才知道，只是多了幾個字元呢，畢竟，按理來說，插入了幾個字元后，原來在右側的字元被迫右移，其實在程式看來，是從插入的地方開始，兩個字串已經開始是不同的了。

但是軟體並沒有從插入的地方開始的右側字元，全標記為差異，所以，軟體是怎麼識別出來的呢？

字串轉換

其實以上的問題可以用下面的例子來簡單闡述：

假設有一個原始字串是：ABCABBA，現在我們想把它變成：CBABAC，是不是有很多種方式呢？

比如，最簡單的方式，ABCABBA依次刪掉：ABCABBA，現在，是不是變成一個空字串了，刪7個字元，一共操作7次；接下來，再在空字串基礎上，依次加上：CBABAC，加了6次。

最終，操作了13次，就把ABCABBA變成了CBABAC。

但是，這太暴力了，也不是很優雅，直觀的感覺就是，太傻了，好像不需要這麼多次吧？

所以，尋找一個演演算法，以保證：轉換成功的同時，保證儘可能少的編輯次數。

這就是最短diff演演算法，diff就是把原始字串變成目標字串，要進行的各種增刪操作；或者也可以和數學裡的delta對比，我查了下，delta就有變動的意思。

"最短diff"這個演演算法有多種實現，在git diff的程式碼中，就有4種實現供我們選擇，分別是：

myers, minimal, patience, histogram。

在git help diff的檔案中，有簡要介紹：

這篇就簡單說下我對myers的理解，演演算法比較複雜，我也沒怎麼弄懂，大家也跟著有個概念就行了（狗頭）

大佬們想了一個辦法來表示diff。還是上面的例子，ABCABBA轉換為CBABAC。

根據這兩個字串構造下面一張圖，橫軸是原始內容，縱軸是目標內容。

這個圖要這麼看，左上角是零座標，水平是x軸，上下是y軸，x軸從（0，0）點到（1,0）點，為A字元；（1,0）到（2,0）是B字元，依次類推，橫軸上的8個點，有7個空，依次為ABCABBA，即原始字串的內容。y軸也是同理。

現在規定了，（0,0）處，你擁有原始字串ABCABBA，當前指向第一個字元A。此時，向右表示刪除對應的字元，向下表示新增對應字元，對角線則表示原內容保持不動（或者說先刪再加，即不變）

現在舉個例子：

從（0,0）移動到（1,0），需要刪掉A，此時，ABCABBA從當前遊標所在處，刪掉A，變成了BCABBA，此時遊標指向BCABBA的第一個字元B；
從（1,0）再向右移動一格到（2,0），此時要刪去B，變成了CABBA
沿著x軸，繼續移動到（3,0），刪除C，變成ABBA；繼續移動到（4,0），刪除A，變成BBA；繼續到（5,0），刪除B，變成BA；繼續到（6,0），刪除B，變成A；繼續到（7,0），刪除A，變成空。
到目前為止，我們來到了7,0，字串變成空的了；開始往下走，往下走的過程，是增加對應字元，比如，從(7,0)，走到（7,1），增加字元C，變成「C」；再走到（7,2），變成CB；再到（7,3），變成CBA；
最終走到(7,6)，變成了CBABAC.