比较五个不同的来源

我需要编写一个函数来比较2-5个“文件”（实际上2-5组数据库行，但类似的概念），我不知道如何去做。由此产生的差异应该呈现2-5个文件并排。输出应显示添加，删除，更改和未更改的行，每个文件都有一列。比较五个不同的来源

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

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

编辑2：我或者更确切地说是我的同事意识到可以对内容进行排序，因为输出顺序是不相关的。这个解决方案意味着在这部分应用程序中使用额外的领域知识，但是差异复杂度是O（N）和较不复杂的代码。这个解决方案很简单，当我关闭赏金时，我会忽略这个编辑的任何答案。不过，我会回答我自己的问题以供将来参考。

来源

2013-01-11 Jonas Byström

您是否对线路比较或字符级比较感兴趣？也就是说，如果在一组中一行是'a，b，c'，另一组是'a，b，d'，你是否还想让这两行被认为'除了c/d'一样？或者他们是不同的记录，因为他们有不同的数据？ – Kaganar

@Kaganar：他们不同，但并不重要。我确定了单独比较器中行的正交性。 –

因此，真正看到的是添加，删除和未更改的行。（没有'改变'的行，那么因为他们会被视为添加。）另外，给定“编辑2”你想要的是一种模糊。通过大多数定义，一组数据库行是无序的，解决您的问题的方法是重新排序和比较。另一种方法是使用散列进行比较，然后在集合中显示相似的行。但是，这听起来不像是你的原始问题的核心 - 你是否真的想要以行间依赖的方式比较行的行数？ – Kaganar

如果所有的Ñ文件（其中2 < = n < = 5为例）必须与其他人进行比较，那么在我看来，比较组合的数量将是C（n,2），由在Python中，例如）：

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

因此，你将有1，3,6或10的成对比较，用于分别Ñ = 2，3，4，5。

的时间复杂度将被C（Ñ，2）成对DIFF算法选择使用，这将是一个预期O（ND）的次数的复杂性，在Myers'算法的情况下，其中N是要比较的两个序列长度的总和，A和B，D是A和B的最小编辑脚本的大小。

我不确定环境你需要这个代码，但difflib在Python中，作为一个例子，可以用来找到各种序列之间的差异 - 不只是文本行 - 所以它可能是对你有用。 difflib文档没有说明它使用什么算法，但它对时间复杂度的讨论使我认为它与Myers相似。（编辑2）

来源

2013-01-15 04:17:36 Simon

我还发现[这个python]（https://github.com/paulgb/simplediff/blob/master/python/simplediff/__init__.py）的实现，我将试验并尝试拥抱你的建议理论。谢谢！ –

看看这篇文章。细节出比较2个数据源与所述陷阱

[http://www.codeproject.com/Articles/30102/Comparing-DataSets-using-LINQ][1]

来源

2013-01-14 15:52:01 user1974729

我需要比较两个以上的数据源。 –

伪代码：

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

来源

2013-01-15 15:00:43

的2个文件中的情况下，可以用标准的diff算法来解决。你从3个文件可以用“多数表决”的算法：

如果一半以上的记录是相同的：2出3,3出4,3出5比这些都是需要考虑的参考其他记录发生变化。

这也意味着如果改变的次数相对较少，算法会大大加快速度。

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

来源

2013-02-10 09:11:50

比较五个不同的来源

回答

相关问题