一個(gè)有些意思的項(xiàng)目--文件夾對(duì)比工具（一）
前言
為什么會(huì)寫這個(gè)，因?yàn)橛龅搅擞幸馑嫉氖虑?，?jiǎn)而言之就是，面試某意向公司，沒(méi)過(guò)；其中一位面試官非常nice，還仔細(xì)看了我博客，覺(jué)得是不是面試時(shí)沒(méi)展現(xiàn)出來(lái)，因此第二天專程打電話過(guò)來(lái)，給了我一個(gè)額外機(jī)會(huì)，就是花幾天時(shí)間做一個(gè)小項(xiàng)目，過(guò)幾天提交給他。
這是背景，項(xiàng)目是關(guān)于做一個(gè)工具，可以指定兩個(gè)目錄進(jìn)行對(duì)比，如果某個(gè)文件如a.txt在兩個(gè)目錄都存在，就對(duì)比其內(nèi)容并呈現(xiàn)，呈現(xiàn)效果可以參考beyond compare或者git diff。
花了三天多時(shí)間編碼，兩天時(shí)間寫文檔，最終做了一個(gè)滿足需求的簡(jiǎn)陋工具出來(lái)，幸不辱命吧；項(xiàng)目麻雀雖小，五臟俱全，也寫了需求分析文檔、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)等，項(xiàng)目本身也非常有意思，所以給大家分享一下。
其中一個(gè)核心點(diǎn)就是文本差異對(duì)比算法，因此先來(lái)篇文章講解一下，鋪墊鋪墊。
差異對(duì)比，很多人會(huì)想到beyond compare、git、svn等。這里以git來(lái)說(shuō)吧，git作為版本管理工具，真的也太方便了，很多時(shí)候想推薦給非互聯(lián)網(wǎng)行業(yè)的朋友們。
版本管理工具，最重要的一點(diǎn)就是不同版本的差異對(duì)比，看下圖：
從圖上來(lái)說(shuō)，右邊那一行比左邊，就是多了幾個(gè)字符”xxxww“；但是對(duì)于軟件來(lái)說(shuō)，怎么才知道，只是多了幾個(gè)字符呢，畢竟，按理來(lái)說(shuō)，插入了幾個(gè)字符后，原來(lái)在右側(cè)的字符被迫右移，其實(shí)在程序看來(lái)，是從插入的地方開(kāi)始，兩個(gè)字符串已經(jīng)開(kāi)始是不同的了。
但是軟件并沒(méi)有從插入的地方開(kāi)始的右側(cè)字符，全標(biāo)記為差異，所以，軟件是怎么識(shí)別出來(lái)的呢？
字符串轉(zhuǎn)換
其實(shí)以上的問(wèn)題可以用下面的例子來(lái)簡(jiǎn)單闡述：
假設(shè)有一個(gè)原始字符串是：ABCABBA，現(xiàn)在我們想把它變成：CBABAC，是不是有很多種方式呢？
比如，最簡(jiǎn)單的方式，ABCABBA依次刪掉：ABCABBA，現(xiàn)在，是不是變成一個(gè)空字符串了，刪7個(gè)字符，一共操作7次；接下來(lái)，再在空字符串基礎(chǔ)上，依次加上：CBABAC，加了6次。
最終，操作了13次，就把ABCABBA變成了CBABAC。
但是，這太暴力了，也不是很優(yōu)雅，直觀的感覺(jué)就是，太傻了，好像不需要這么多次吧？
所以，尋找一個(gè)算法，以保證：轉(zhuǎn)換成功的同時(shí)，保證盡可能少的編輯次數(shù)。
這就是最短diff算法，diff就是把原始字符串變成目標(biāo)字符串，要進(jìn)行的各種增刪操作；或者也可以和數(shù)學(xué)里的delta對(duì)比，我查了下，delta就有變動(dòng)的意思。
"最短diff"這個(gè)算法有多種實(shí)現(xiàn)，在git diff的代碼中，就有4種實(shí)現(xiàn)供我們選擇，分別是：
myers, minimal, patience, histogram。
在git help diff的文檔中，有簡(jiǎn)要介紹：
默認(rèn)的是myers算法，什么時(shí)候用其他的呢，這邊有篇文檔：https://luppeng.wordpress.com/2020/10/10/when-to-use-each-of-the-git-diff-algorithms/，有需要的同學(xué)可以看看。
這篇就簡(jiǎn)單說(shuō)下我對(duì)myers的理解，算法比較復(fù)雜，我也沒(méi)怎么弄懂，大家也跟著有個(gè)概念就行了（狗頭）
diff的另一種直觀展示
大佬們想了一個(gè)辦法來(lái)表示diff。還是上面的例子，ABCABBA轉(zhuǎn)換為CBABAC。
根據(jù)這兩個(gè)字符串構(gòu)造下面一張圖，橫軸是原始內(nèi)容，縱軸是目標(biāo)內(nèi)容。
這個(gè)圖要這么看，左上角是零坐標(biāo)，水平是x軸，上下是y軸，x軸從（0，0）點(diǎn)到（1,0）點(diǎn)，為A字符；（1,0）到（2,0）是B字符，依次類推，橫軸上的8個(gè)點(diǎn)，有7個(gè)空，依次為ABCABBA，即原始字符串的內(nèi)容。y軸也是同理。
現(xiàn)在規(guī)定了，（0,0）處，你擁有原始字符串ABCABBA，當(dāng)前指向第一個(gè)字符A。此時(shí)，向右表示刪除對(duì)應(yīng)的字符，向下表示新增對(duì)應(yīng)字符，對(duì)角線則表示原內(nèi)容保持不動(dòng)（或者說(shuō)先刪再加，即不變）
現(xiàn)在舉個(gè)例子：
-
從（0,0）移動(dòng)到（1,0），需要?jiǎng)h掉A，此時(shí)，ABCABBA從當(dāng)前光標(biāo)所在處，刪掉A，變成了BCABBA，此時(shí)光標(biāo)指向BCABBA的第一個(gè)字符B；
image-20220801222140579 從（1,0）再向右移動(dòng)一格到（2,0），此時(shí)要?jiǎng)h去B，變成了CABBA
-
沿著x軸，繼續(xù)移動(dòng)到（3,0），刪除C，變成ABBA；繼續(xù)移動(dòng)到（4,0），刪除A，變成BBA；繼續(xù)到（5,0），刪除B，變成BA；繼續(xù)到（6,0），刪除B，變成A；繼續(xù)到（7,0），刪除A，變成空。
image-20220801222800789 到目前為止，我們來(lái)到了7,0，字符串變成空的了；開(kāi)始往下走，往下走的過(guò)程，是增加對(duì)應(yīng)字符，比如，從(7,0)，走到（7,1），增加字符C，變成“C”；再走到（7,2），變成CB；再到（7,3），變成CBA；
最終走到(7,6)，變成了CBABAC.
大家可能發(fā)現(xiàn)了，只要沿著那個(gè)圖一路走，從（0,0）到達(dá)右下角（7,6），原始字符串就能變成目標(biāo)字符串。
當(dāng)然，這條路是比較暴力的，先刪除原始字符串（一路往右），再新增目標(biāo)字符串（一路向下）。
diff的圖形表示之路線演示
我們來(lái)隨便畫個(gè)其他路線試試。
現(xiàn)在（0，0）處，我們?yōu)樵甲址瓵BCABBA，
- 接下來(lái)是向右一步-A，變成BCABBA。
- 向下，+C，變成CBCABBA
- 遇到對(duì)角線，對(duì)角線對(duì)應(yīng)字符B，此時(shí)可以理解為刪掉B，再加上B，相當(dāng)于光標(biāo)前移，依然是CB|CABBA，我們用|表示光標(biāo)位置
- 向下，在當(dāng)前光標(biāo)處+A，變成CBA|CABBA；加B，變成CBAB|CABBA；再-C，變成CBAB|ABBA
- 又遇到對(duì)角線，對(duì)角線對(duì)應(yīng)字符A，此時(shí)光標(biāo)移動(dòng)，變成CBABA| BBA
- 從(4,5)移動(dòng)到（4,6），加C，變成CBABAC|BBA
- 從（4,6）移動(dòng)到(7,6),依次刪除BBA，即變成CBABAC
所以，我們?cè)僖淮纬晒Φ竭_(dá)了右下角，此時(shí)字符串也變成了CBABAC。我們也可以算一下，移動(dòng)了多少次
-A，+C，+A，+B，-C，+C，-B，-B，-A，合計(jì)是9次（走對(duì)角線的話，沒(méi)有實(shí)際修改字符，不算在內(nèi)）。
Myers 算法大概理解
如果前面都理解了的話，我們大概知道，從圖中的左上角，到達(dá)右下角的每一條路線，都是有效的diff。
而Myers的目標(biāo)，應(yīng)該就是從眾多的路線中，選出一條距離最短（向右的次數(shù) + 向下的次數(shù)之和；走對(duì)角線不算）的路線。
而這條最短的路線，就是最短diff算法的答案。
Myers的算法我還不是很理解，但是如果按照我們暴力的思路，就是每條路線的距離都計(jì)算一下（向右的次數(shù) + 向下的次數(shù)之和；走對(duì)角線不算），然后取最短的路線即可。
網(wǎng)上有不少資料，有興趣可以閱讀：
原始論文：
https://neil.fraser.name/writing/diff/myers.pdf
本文由mdnice多平臺(tái)發(fā)布
