更快加速

Question

我正在研究區分較大的二進制文件。我已經實現了着名的Myers Diff算法，它產生了一個最小差異。然而，它是O（ND），所以要區分兩個非常不同的1 MB文件，我預計需要100萬平方= 1萬億的時間。這不好！

我想要的是一種算法，可以產生一個潛在的非最小差異，但速度更快。我知道一個人必須存在，因爲Beyond Compare會這樣做。但我不知道如何！

可以肯定的是：有些工具如xdelta或bdiff，但是這些工具會生成一個用於計算機消耗的補丁，這與人類可消耗的diff不同。補丁涉及將一個文件轉換爲另一個文件，因此它可以執行諸如從文件的以前部分進行復制的操作。一個人類可消費的差異是在視覺上顯示差異，並且只能插入和刪除。例如，該變換：

「puddi」 - > 「puddipuddipuddi」

將產生一小片 「拷貝[0,4]到[5,9]和[10，14]」，但更大的差異「追加'puddipuddi'」。我對產生更大差異的算法感興趣。

謝謝！

Answer 1

Diffining與生物信息學中用於比對DNA序列的算法基本相同。這些序列往往很大（百萬甚至上億個核苷酸長的），和一個策略，有行之有效的長基因組所使用的程序MUMmer：

1. 迅速找到所有最大獨特的匹配出現在（子兩個文件並且不能在該條件下沿任一方向擴展仍然保持）使用後綴樹
2. 快速找到使用最長增加的子序列動態編程算法在兩個文件中以連續順序出現的MUM的最長子集
3. 修正MUM中的這個子集（即標記那些區塊作爲匹配）
4. 如果認爲有必要，執行較慢（例如，邁爾斯）在MUM區域之間進行區分。在你的情況下，如果你發現最長的MUM的長度低於某個閾值（你會認爲這兩個文件無關），那麼你可能會完全忽略這一步。

只要沒有太多差異，這往往會給出一個非常好的（雖然不是保證最佳的）對齊區域集合（或等價地，一組非常小的差異）。我不確定每一步的確切時間範圍，但我知道沒有n^2或更高的條件。我相信MUMMER程序需要DNA或蛋白質序列，所以它可能不適合你，但這些概念當然適用於一般字符串（如文件），所以如果你準備自己重新實現它，會推薦這種方法。

Answer 2

從性能的角度來看，隨着文件大小的增加，GNU Diffutils可能是最穩健的選擇。對於你的情況，我可能會使用它的side-by-side comparison format，這可能是該地段最友善的人羣。否則，你不得不以另一種格式輸出它的輸出，並且做一些工作來使它更漂亮。

一個好的競爭者，其表現一直在穩步提高，包括衆多的加速，diff-match-patch。它以幾種不同的語言實現了Myers Diff算法，包括Java和JavaScript。請看online demo，以獲得漂亮的打印結果。如果你想做線差異研究wiki的技巧，如何使用它的目的。