我需要编写一个简单的源代码管理系统，并想知道我将用于文件差异的算法？源代码管理系统的算法？
由于许可证问题，我不想查看现有的源代码。我需要在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