我需要編寫一個簡單的源代碼管理系統，並想知道我將用於文件差異的算法？源代碼管理系統的算法？
由於許可證問題，我不想查看現有的源代碼。我需要在MPL下獲得許可，所以我不能查看任何現有的系統，如CVS或Mercurial，因爲它們都是GPL許可的。
爲了給出一些背景知識，我只需要一些非常簡單的功能 - 文件夾中的二進制文件。沒有子文件夾和每個文件的行爲就像它自己的存儲庫。沒有元數據，除了某些權限。
總的來說真的很簡單，我唯一關心的就是如何在不浪費太多空間的情況下僅存儲文件從修訂版到修訂版的差異，而且不會太低效（也許每X次更改都會存儲一個完整版本，有點像視頻中的關鍵幀？）
最長的通用子序列算法是類似diff工具所使用的主要機制，可由源代碼控制系統利用。
「Reverse Deltas」是一種常見的存儲方法，因爲您主要需要從最新修訂版中及時向後移動。
其實我在想什麼類似這樣的一天...（奇，是吧？）
我沒有給你一個偉大的答案，但我並得出這樣的結論，如果我是編寫一個文件比較工具，我會這樣做的算法（用於發現差異），其功能有點像REGEX的貪婪功能。
至於存儲DIFFs ...如果我是你，而不是存儲前向DIFF（即你開始你的原始文件，然後計算機150與你使用版本151時相反），使用存儲DIFF爲您的歷史記錄，但將您的最新文件存儲爲完整版本。如果你這樣做，那麼每當你使用最新的文件（這可能是99％的時間）時，你會得到最好的性能。
雖然化石是GPL，增量算法是基於rsync的和描述here
Patience Diff是找到兩個文件有可能是有意義的人與人之間的增量好的算法。這通常會比天真的「最長的公共子序列」算法獲得更好的結果，但結果是主觀的。儘管如此，許多現代版本控制系統在每個階段存儲完整的文件，並且僅在需要時才計算實際差異。對於二進制文件（這可能不是非常可壓縮的），您可能會發現存儲反向增量可能最終會更有效。
這很酷。 LCS算法家族仍然是一個變體，但它是一個非常漂亮的改進。 – JasonTrue 2010-04-18 05:40:13
有趣！ （墊，墊......） – 2010-04-18 06:26:02
基因邁爾斯寫了一篇很好的論文An O(ND) Difference Algorithm and its Variations。談到比較序列，邁爾斯是男人。您可能還應該閱讀Walter Tichy關於RCS的論文;它解釋瞭如何通過存儲最新版本和差異來存儲一組文件。
存儲增量（向前或向後）的想法在版本控制方面很經典。問題一直是，「你存儲哪個三角洲？「
很多源代碼控制系統存儲基本上由」diff「計算的增量，例如，最長公共子序列的面向行的補充。但是，您可以按特定於這些文檔的方式計算特定類型文檔的增量，以獲得更小（並且通常更容易理解）的增量
對於編程語言的源代碼，我們可以計算程序結構上的Levenshtein距離，可以在這裏找到一系列用於各種流行編程語言的工具。 Smart Differencer
如果您要存儲非文本文件，您可能可以利用其結構來計算s麥芽三角洲。
當然，如果你想要的是一個最小的實現，那麼僅僅存儲每個文件版本的完整圖像是很容易的。太字節磁盤使得該解決方案如果不美觀可行。 （PDP10文件系統用於隱含地執行此操作）。
嗯，我更喜歡你的答案。看起來，你確實知道你在說什麼。 :-P – Jaxidian 2010-04-18 05:02:51