比较五种不同的来源

Question

我需要编写一个函数来比较2-5“文件”(实际上是2-5组数据库行，但概念相似)，我不知道如何做。由此产生的差异应该并排显示2-5文件。输出应显示已添加、删除、更改和未更改的行，并为每个文件设置一列。

为了保持低复杂度，我应该使用什么算法来遍历行？每个文件的行数小于10,000行。我可能不需要外部合并，因为总数据大小在兆字节范围内。当然，简单易懂的代码也不错，但这不是必须的。

编辑：文件可能是从某个未知的来源派生出来的，没有其他1-4个文件可以比较的“原始”；所有文件都必须以某种方式与其他文件进行比较。

编辑2: I，或者更确切地说是我的同事，意识到内容可以排序，因为输出顺序是无关的。这种解决方案意味着对应用程序的这一部分使用额外的域知识，但也意味着差异复杂性是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)的C(n，2)倍，这是一个期望的O(ND)算法，其中N是两个序列的长度之和，A和B，D是A和B的最小编辑脚本的大小。

我不确定您需要在什么环境中使用这些代码，但是可以使用Python中的衍射库来查找各种序列之间的差异--而不仅仅是文本行--所以它可能对您有用。difflib文档没有具体说明它所使用的算法，但它对其时间复杂性的讨论使我认为它类似于Myers的算法。

Answer 2

伪代码(用于编辑2)：

10: stored cells = <empty list>
for each column:
  if cell < stored cells:
    stored cells = cell
  elif cell == lastCell:
    stored cells += cell

if stored cells == <empty>:
  return result
result += stored cells
goto 10

Answer 3

两个文件的情况可以用标准的diff算法解决。从3个文件中可以使用“多数票”算法：

如果超过一半的记录是相同的: 3项中有2项、4项中有3项、5项中有3项是参照考虑其他记录已改变的。

此外，如果更改的次数相对较少，则对该算法来说意味着相当大的加速比。

Pseudocode:
  initialize as many line indexes as there are files
  while there are still at least 3 indexes incrementable
    if all indexed records are the same 
      increment all line indexes
    else 
      if at least one is different - check majority vote
      if there is a majority
        mark minority changes, increment all line indexes
      else
        mark minority additions (maybe randomly deciding e.g. in a 2:2 vote)
        check addition or removing and set line indexes accordingly
        increment all indexes
      endif
    endif
  endwhile