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

Question

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

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

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

1. diff 尝试将更改分组在一起，找出文件中的哪些 block 发生了更改。我只是在寻找已更改行的列表，这应该是一个比查找最长公共(public)子序列或类似问题简单得多的问题。

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

这里是问题的限制条件:

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

2. 大多数情况下，列表之间没有区别。如果有差异，通常只有少数新文件/删除文件。

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

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

为了它的值(value)，我 previously posted这个问题关于 Ask Metafilter几年前。请允许我预先回应几个可能的答案。

答案:这个问题叫做Longest Common Subsequence .

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

答案:按字母顺序对它们进行排序，然后进行比较。

响应:那将是 O(m log m+n log n)，比 O(m+n) 更糟.

Answer 1

这不完全是 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。