algorithm - 比较五个不同的来源

Question

我需要编写一个函数来比较 2-5 个"file"(实际上是 2-5 组数据库行，但概念相似)，但我不知道该怎么做。生成的差异应该并排显示 2-5 个文件。输出应显示添加、删除、更改和未更改的行，每个文件都有一列。

我应该使用什么算法来遍历行以保持较低的复杂性？每个文件的行数小于 10,000。我可能不需要 External Merge因为总数据大小在兆字节范围内。简单易读的代码当然也很好，但这不是必须的。

编辑:这些文件可能来自某些未知来源，没有其他 1-4 个文件可以与之比较的“原始”文件；所有文件都必须以某种方式与其他文件进行比较。

编辑 2: 我，或者更确切地说是我的同事，意识到内容可以排序，因为输出顺序是无关紧要的。该解决方案意味着对应用程序的这一部分使用额外的领域知识，而且 diff 的复杂性是 O(N) 和不太复杂的代码。这个解决方案很简单，当我关闭赏金时，我将忽略对此编辑的任何答案。不过，我会回答我自己的问题以供将来引用。

Answer 1

如果所有的 n 文件(例如 2 <= n <= 5)都必须与其他文件进行比较，那么在我看来要比较的组合数将是 C(n,2)，定义为(例如，在 Python 中):

def C(n,k): 
    return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

因此，对于 n = 2、3、4、5，您将分别进行 1、3、6 或 10 次成对比较。

时间复杂度将是 C(n,2) 乘以您选择使用的成对diff 算法的复杂度，这将是预期的 O( ND)，在 Myers' 的情况下算法，其中N是要比较的两个序列A和B的长度之和，D是A和B的最小编辑脚本的大小。

我不确定您需要此代码的环境，但是 difflib例如，在 Python 中，它可用于查找各种序列之间的差异 - 不仅仅是文本行 - 因此它可能对您有用。 difflib 文档没有确切说明它使用的是什么算法，但它对其时间复杂度的讨论让我认为它与 Myers 的相似。