Diff算法

Question

我一直在尋找一種解析差異算法的解釋，並且效率很高。

我得到的最接近是this link to RFC 3284（從幾個埃裏克庫博客文章），這完全可以理解的術語，其中DIFF結果存儲在數據格式描述。然而，它並沒有提到一個程序如何在做差異時達到這些結果。

我試圖研究這個出於個人好奇心，因爲我確定在實施差異算法時必須進行權衡，有時當你看差異並且奇怪「爲什麼diff程序選擇了這是作爲一個改變，而不是那個？「...

有誰知道在哪裏可以找到一個有效的算法，最終會輸出VCDIFF的描述？順便說一下，如果你碰巧找到了SourceGear的DiffMerge使用的實際算法的描述，那會更好。

注意：最長的公共子序列似乎不是VCDIFF使用的算法，看起來他們正在做更聰明的事情，因爲它們使用的數據格式不同。

謝謝！

Answer 1

An O(ND) Difference Algorithm and its Variations是一個夢幻般的紙，你可能想從那裏開始。它包含了僞代碼以及在執行差異時涉及的圖遍歷的一個很好的可視化。

本文的第4部分介紹了算法的一些改進，使其非常有效。

成功實施此操作將爲您提供一個非常有用的工具（可能還有一些非常棒的體驗）。生成你需要的輸出格式有時可能會很棘手，但如果你對算法內部有了解，那麼你應該能夠輸出任何你需要的東西。您還可以引入啓發式方法來影響輸出並進行某些折衷。

Here is a page其中包括一些文檔，full source code，以及使用上述算法中的技術的差異算法的示例。

source code似乎遵循基本算法密切和易於閱讀。

準備輸入也有一點，您可能會覺得有用。當您通過字符或標記（單詞）進行區分時，輸出會有很大差異。

祝你好運！

Answer 2

我將首先看實際的源代碼爲差異，其中GNU使available。

對於理解的是源代碼實際上是如何工作的，該包中的文檔引用啓發它的文件：

的基本算法中「的O（ND）差分算法描述和它的變體「，尤金W.邁爾斯，'Algorithmica'卷。 1986年第1期，第251-266頁;和「A檔案 比較程序」，Webb Miller和Eugene W. Myers，'Software - Practice and Experience'Vol。 1985年11月15日，第1025-1040頁。該算法是獨立發現的，如在E. Ukkonen的「信息與控制」Vol.5的「用於近似字符串匹配的算法」中所述。 64，1985，第100-118頁。

閱讀論文，然後查看實現的源代碼應該足夠了解它是如何工作的。

Answer 3

見http://code.google.com/p/google-diff-match-patch/

「的DIFF匹配和補丁庫 提供強大的算法來進行同步 純文本所需的 操作。...在Java中，JavaScript的，C++，C＃和目前市面上 蟒」

另見wikipedia.org Diff page和 - 「Bram Cohen: The diff problem has been solved」

Answer 4

基於Emmelaich給出的鏈接，差異策略在Neil Fraser's website (one of the authors of the library)上也有很大的下滑。

他涵蓋了基本的策略，並在文章的最後進展到Myer的算法和一些圖論。

Answer 5

我來這裏尋找差異算法，然後做出我自己的實現。對不起，我不知道vcdiff。

Wikipedia：從一個最長的公共子序列，它只是一小步獲得不同樣的輸出：如果一個項目在子序列中不存在但存在於原始項目中，它必須已被刪除。 （下面的' - '標記。）如果它在子序列中不存在但是存在於第二序列中，則它必須已經添加。（'+'標記。）

好的動畫LCS algorithm here。

鏈接到一個快速的LCS ruby implementation here。

我的緩慢和簡單的紅寶石適應如下。

def lcs(xs, ys) 
    if xs.count > 0 and ys.count > 0 
    xe, *xb = xs 
    ye, *yb = ys 
    if xe == ye 
     return [xe] + lcs(xb, yb) 
    end 
    a = lcs(xs, yb) 
    b = lcs(xb, ys) 
    return (a.length > b.length) ? a : b 
    end 
    return [] 
end 

def find_diffs(original, modified, subsequence) 
    result = [] 
    while subsequence.length > 0 
    sfirst, *subsequence = subsequence 
    while modified.length > 0 
     mfirst, *modified = modified 
     break if mfirst == sfirst 
     result << "+#{mfirst}" 
    end 
    while original.length > 0 
     ofirst, *original = original 
     break if ofirst == sfirst 
     result << "-#{ofirst}" 
    end 
    result << "#{sfirst}" 
    end 
    while modified.length > 0 
    mfirst, *modified = modified 
    result << "+#{mfirst}" 
    end 
    while original.length > 0 
    ofirst, *original = original 
    result << "-#{ofirst}" 
    end 
    return result 
end 

def pretty_diff(original, modified) 
    subsequence = lcs(modified, original) 
    diffs = find_diffs(original, modified, subsequence) 

    puts 'ORIG  [' + original.join(', ') + ']' 
    puts 'MODIFIED [' + modified.join(', ') + ']' 
    puts 'LCS  [' + subsequence.join(', ') + ']' 
    puts 'DIFFS  [' + diffs.join(', ') + ']' 
end 

pretty_diff("human".scan(/./), "chimpanzee".scan(/./)) 
# ORIG  [h, u, m, a, n] 
# MODIFIED [c, h, i, m, p, a, n, z, e, e] 
# LCS  [h, m, a, n] 
# DIFFS  [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]