A05

文字比對

逐行或逐字比對兩段文字,自寫 Myers 差異演算法,不送出任何內容。

原理

這裡用的是 Myers 1986 年那篇論文的演算法:它把「把左邊改成右邊最少要動幾下」當成在編輯圖上找最短路徑,複雜度是 O((N+M)·D),D 是實際的差異量。換句話說,兩段很像的文字比得飛快,兩段毫不相干的文字才會慢——而「貼兩段毫不相干的東西」剛好是任何人都會試一次的操作。

所以在跑演算法之前會先把兩邊共同的開頭與結尾切掉。真實的修改幾乎都只動中間一小段,切完之後要比的長度常常只剩原本的百分之幾。剩下的部分若還是太大(超過一萬兩千個片段),它會直接告訴你比不動,而不是把你的分頁凍住——那種凍住在瀏覽器裡跟當掉是一樣的,唯一的出路是關掉分頁。

逐字模式對中文有特別處理:中文沒有空格,若照英文那樣用空白切詞,一整段中文會變成一個片段,改一個字就報告整段被換掉。這裡把中日韓字元逐字切開,標點與全形字元也算在內,所以「一段」改成「兩段」就只會標出那一個字。