algorithm - diff可以在自己的游戏中被击败吗？

Question

我正在寻找合适的算法来比较两个文件。diff我认为我可以比由于一些额外的限制做得更好。

我拥有的是两个文本文件，每个文件都包含一个文件列表。它们是在两个不同时间拍摄的系统上所有文件的快照。我想弄清楚在两个快照之间添加或删除了哪些文件。

我可以diff用来比较这些文件，但我不想这样做，因为：

1. diff尝试将更改组合在一起，查找文件中的哪些块已更改。我只是在寻找一个已经改变的行列表，这应该比找到最长的公共子序列或类似的东西要简单得多。

2. 广义差异算法在运行时或空间上是O(mn) 。我正在寻找更像时间上的O(m+n)和空间上的O(1)的东西。

以下是该问题的限制条件：

1. 两个文件中的文件列表顺序相同。它们不一定按字母顺序排列，但它们的相对顺序相同。

2. 大多数情况下，列表之间不会有任何差异。如果存在差异，通常只会有少数新/删除的文件。

3. 我不需要将结果组合在一起，比如说“整个目录已被删除”或“第 100-200 行是新的”。我可以单独列出不同的每一行。

我认为这相当于拥有两个排序列表并试图找出两个列表之间的差异的问题。问题是列表项不一定按字母顺序排序，因此您不知道一项是否比另一项“更大”。您只知道两个列表中存在的文件的顺序相同。

对于它的价值，我几年前曾在Ask Metafilter上发布过这个问题。请允许我预先回答几个可能的答案。

答：这个问题称为最长公共子序列。

回应：我试图避免最长的公共子序列，因为简单的算法在O(mn)时间/空间中运行，而更好的算法更复杂且更“启发式”。我的直觉告诉我，由于添加了约束，所以存在线性时间算法。

答：按字母顺序排列，然后比较。

响应：那将是O(m log m+n log n)，这比O(m+n)差。

Answer 1

读取一个文件，将每个文件名放入带有add 和contains 实现的类似HashSet的数据结构中。O(1)O(1)

然后读取 seconds 文件，根据 HashSet 检查每个文件名。

如果文件一有长度m，而第二个文件有长度，则总算法n是O(m+n)按要求的。

注意：该算法假设数据集在物理内存中的适应速度很快。

如果数据集无法轻松放入内存，则可以使用带有磁盘分页的B-Tree的某些变体来实现查找。然后，复杂性将是O(mlog m)初始设置并O(n log m)为每个其他文件进行比较。

Answer 2

这不完全是O(1)内存，按更改次数顺序的内存需求，但它是O(m+n)运行时的。

它本质上是一种缓冲流算法，在任何给定行都知道所有先前行的差异。

// Pseudo-code:
initialize HashMap<Line, SourceFile> changes = new empty HashMap
while (lines left in A and B) {
    read in lineA from file A
    read in lineB from file B

    if (lineA.equals(lineB)) continue

    if (changes.contains(lineA) && changes.get(lineA).SourceFile != A) {
         changes.remove(lineA)
    } else {
         changes.add(lineA, A)
    }

    if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
         changes.remove(lineB)
    } else {
         changes.add(lineB, B)
    }
}

for each (line in longerFile) {
    if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
         changes.remove(line)
    } else {
         changes.add(line, longerFile)
    }
}

Lines in the HashMap from SourceFile == A have been removed
Lines in the HashMap from SourceFile == B have been added

这在很大程度上依赖于文件以相同的相对顺序列出的事实。否则，内存需求将远大于更改的数量。但是，由于这种排序，该算法使用的内存不应超过 2 * numChanges。

Answer 3

从理论的角度来看，比较两个字符串之间的编辑距离（因为这里有一个有趣的语言中的字符串，其中“字符”是一个文件名）不能进行 O(m+n)。但在这里我们进行了简化。

在您的情况下实现算法（应该包含错误）：

# i[0], i[1] are undoable iterables; at the end they both return Null

while (a = i[0].next()) && (b = i[1].next()) :    # read one item from each stream
    if a != b:                 # skip if they are identical
        c = [[a],[b]]          # otherwise, prepare two fast arrays to store difference
        for (w = 1; ; w = 1-w) # and read from one stream at a time
             nxi = Null        
             if (nx = i[1-w].next()) in c[w]:  # if we read a new character that matches
                  nxi = c[w].index(nx)          
             if nx is Null: nxi = -1           # or if we read end of stream
             if nxi is not Null:               # then output that we found some diff
                 for cc in c[1-w]: yield cc              # the ones stored 
                 for cc in c[w][0:nxi-1]: yield cc       # and the ones stored before nx
                 for cc in c[w][nxi+1:]: i[w].undo(cc)   # about the remainder - put it back
                 break                         # and return back to normal cycle
 # one of them finished
 if a: yield a
 if b: yield b
 for ci in i: 
     while (cc = ci.next()): yield cc

有些数据结构我称之为快速数组——它们可能是HashSet事物，但它们会记住排序。它们中的加法和查找应该是O(log N)，但内存使用O(N)。

O(m+n)除了发现差异之外，这不会使用任何内存或循环。对于每个“差异块”——可以描述为去掉 M 个连续项目并添加 N 个项目的操作——这需要O(M+N)内存和指令。块完成后释放内存，因此如果您确实只有很小的更改，这并不是什么大问题。当然，最坏情况下的性能与泛型方法一样糟糕。O(MN) O(Mlog N+Nlog M)

Answer 4

在实践中，排序时间的对数因子差异可能是微不足道的——sort可以在几秒钟内对数十万行进行排序。所以你实际上不需要编写任何代码：

sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes

我并不是说这一定是最快的解决方案——我认为Ben S 接受的答案是，至少高于 N 的某个值。但它绝对是最简单的，它可以扩展到任意数量的文件，并且（除非你是负责谷歌备份操作的人）对于您拥有的文件数量来说，它的速度将绰绰有余。

Answer 5

如果您接受字典（哈希映射）是 O(n) 空间和 O(1) 插入/查找，那么这个解决方案在时间和空间上都应该是 O(m+n)。

from collections import defaultdict
def diff(left, right):
    left_map, right_map = defaultdict(list), defaultdict(list)
    for index, object in enumerate(left): left_map[object] += [index]
    for index, object in enumerate(right): right_map[object] += [index]
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left_map[right[j]]:
            i2 = left_map[right[j]].pop(0)
            if i2 < i: continue
            del right_map[right[j]][0]
            for i in range(i, i2): print '<', left[i]
            print '=', left[i2], right[j]
            i, j = i2 + 1, j + 1
        elif right_map[left[i]]:
            j2 = right_map[left[i]].pop(0)
            if j2 < j: continue
            del left_map[left[i]][0]
            for j in range(j, j2): print '>', right[j]
            print '=', left[i], right[j2]
            i, j = i + 1, j2 + 1
        else:
            print '<', left[i]
            i = i + 1
    for j in range(j, len(right)): print '>', right[j]

>>> 差异（[1, 2, 1, 1, 3, 5, 2, 9],
... [ 2, 1, 3, 6, 5, 2, 8, 9])
< 1
= 2 2
= 1 1
< 1
= 3 3
> 6
= 5 5
= 2 2
> 8
= 9 9

好吧，如果它们是链表，那么轻微的作弊list.append只是list.__delitem__O(1)，这不是真的……但无论如何，这就是想法。

Answer 6

对 ehemient 答案的改进，这只在有变化时使用额外的内存。

def diff(left, right):
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] == right[j]:
            print '=', left[i], right[j]
            i, j = i+1, j+1
            continue

        old_i, old_j = i, j
        left_set, right_set = set(), set()

        while i < len(left) or j < len(right):
            if i < len(left) and left[i] in right_set:
                for i2 in range(old_i, i): print '<', left[i2]
                j = old_j
                break

            elif j < len(right) and right[j] in left_set:
                for j2 in range(old_j, j): print '>', right[j2]
                i = old_i
                break

            else:
                left_set .add(left [i])
                right_set.add(right[j])
                i, j = i+1, j+1

    while i < len(left):
        print '<', left[i]
        i = i+1

    while j < len(right):
        print '>', right[j]
        j = j+1

评论？改进？

Answer 7

我一直在追求一个程序来区分大文件而不会耗尽内存，但没有找到适合我的目的。我对使用差异进行修补不感兴趣（然后我可能会rdiff从 librdiff 使用），但是为了直观地检查差异，也许将它们变成单词差异dwdiff --diff-input（读取统一差异格式）并可能收集单词-diffs 不知何故。

（我的典型用例：我有一些用于处理大型文本语料库的 NLP 工具。我运行它一次，得到一个 122760246 行长的文件，我对我的工具进行了更改，再次运行它，得到一个文件就像每百万行不同，可能两次插入和删除，或者只有一行不同，诸如此类。）

由于我找不到任何东西，我只是制作了一个小脚本https://github.com/unhammer/diff-large-files - 它可以工作（dwdiff 接受它作为输入），它足够快（比 xz 进程快经常在管道中运行），最重要的是它不会耗尽内存。

Answer 8

我会将文件列表读入两组，然后找到对任一列表都是唯一的文件名。

在 Python 中，类似于：

files1 = set(line.strip() for line in open('list1.txt'))
files2 = set(line.strip() for line in open('list2.txt'))
print('\n'.join(files1.symmetric_difference(files2)))