文本差異應用程序如何工作？

Question

像DiffMerge這樣的應用程序如何檢測文本文件中的差異，以及它們如何確定何時行是新的，而不僅僅是與被檢查的文件不同的行上。

這是相當容易實現的東西嗎？有沒有圖書館這樣做？

Answer 1

這裏的the paper作爲UNIX命令行工具的基礎diff。

Answer 2

它實際上很簡單; DIFF程序 - 大部分時間 - 基於Longest Common Sequence，可以使用圖算法解決。

This web page給出了C＃中的示例實現。

Answer 3

這是一個複雜的問題。執行diff就意味着找到兩個文件之間的最小編輯距離。也就是說，將一個文件轉換爲另一個文件所需的最小數量的更改。這相當於找到兩個文件之間最長的常見子序列，這是各種差異程序的基礎。最長的公共子序列問題是衆所周知的，您應該能夠在google上找到動態編程解決方案。

動態規劃方法的問題在於它是O（n^2）。因此它對大文件非常緩慢，並且對於大的二進制字符串不可用。編寫差異程序的難點在於優化問題域的算法，以便獲得合理的性能（以及合理的結果）。 Hunt和McIlroy撰寫的文章「差分文件比較算法」很好地描述了早期版本的Unix diff實用程序。

Answer 4

有圖書館。這裏有一個：http://code.google.com/p/google-diff-match-patch/

StackOverflow使用超越比較它的差異。我相信它通過從命令行調用Beyond Compare來工作。