107.04.16 程式語言作業(二) diff

前言

程式語言的作業二是用 Lisp 寫一個 diff 程式

題外話
其實作業二有三小項可選，後面是寫該項目可以拿幾分
1: 80、2: 90、1+2: 100、3: 100
我懶得寫 1+2 而切那個好像還要說明一堆東西所以直接挑戰 3 也就是本篇主題啦

所謂 diff 程式就是可以比較兩個檔案的差異，如下圖

不要問我為啥有 end 這個東西，因為助教的說明文件就打這樣，可能是新版的 endl 吧(誤



我有找到一篇好像很猛的 paper: An O(ND) Difference Algorithm and Its Variations
可惜我太嫩了看不下去
只好使用我知道的方法，以後有時間在來實作看看 (又欠債

程式流程

1. 讀檔案

因為題目說要寫死讀 file1.txt 和 file2.txt 兩個檔案，但若是從 argument list 讀應該也是可行的
所以要解決的就是把兩個檔案一行一行讀進各自的 list 中

2. 比較，利用 LCS (Longest Common Subsequence)

LCS 可以找出最長相似子字串，詳細步驟就去參考演算法筆記吧 (被揍
但若是要分辨某個字串是否為 LCS 還要多做一件事，就是記錄 LCS 在 list 中出現的位置

3. 輸出

利用剛剛做好的位置陣列，就可以從頭跑 file1.txt 的 list
若發現這個位置不是 LCS 就輸出 - 直到一個 LCS 然後還不能輸出 LCS
這時候換成跑 file2.txt，一樣若發現這個位置不是 LCS 就輸出 + 直到出現剛剛的 LCS
此時再輸出這個 LCS，接著回到 file1.txt 繼續找下一個 LCS，記住找到之前同樣輸出 - 
就這樣一直到最後一個 LCS 輸出
此時還不能鬆懈，有可能最後幾個不是 LCS，所以就繼續先把 file1.txt 的 list 跑完，記得加 - 
最後再把 file2.txt 跑完，一樣加 + 

這樣就完成了 OuO

小小小小範例

file1.txt:
a
b
c
d
f
file2.txt:
b
g
d
e
1. 形成兩個 list，分別是("a", "b", "c", "d", "f")、("b", "g", "d", "e")
2. 找出 LCS 為 ("b", "d")，分別對應的位置：file1: (1, 3)、file2: (0, 2)
3. 開始輸出，以下用 i 表示 file1 的 list 的索引 (i 為 0 跑到 4)，j 表示 file2 的 (j 為 0 跑到 3)
從 file1 開始跑
i 為 0，i 不等於 1，所以輸出 -a
i 為 1 等於 1 所以是 LCS
換 file2
j 為 0 剛好是 LCS，因此輸出 b
回到 file1
i 為 2 不是，所以輸出 -c
i 為 3 時是 LCS
換 file2
j 為 1 不是，所以輸出 +g
j 為 2 是，所以輸出 d
這樣所有 LCS 就輸出完畢
再來先把所有 file1 的字串輸出，所以輸出 -f
最後是 file2 的，所以輸出 +e
完成

所以 diff 輸出結果如下
-a
 b
-c
+g
 d
-f
+e

後記

其實方法不難，難的是用 Lisp 實作
邏輯跟平常寫得有些差異所以要有耐心，要有對程式的愛 QuQ
由於繳交時間還沒截止所以我還沒 push 到 GitHub
到時候網址會在這裡


參考資料：
Diff Algorithm
Longest Common Subsequence - 演算法筆記