可以在自己的比赛中击败吗？

Question

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

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

我可以diff用来比较这些文件,但我不想,因为:

1. diff尝试将更改组合在一起,查找文件中的哪些块已更改.我只是在寻找一个已经改变的行列表,这应该是一个比找到最常见的子序列或某些类似事情更简单的问题.

2. 广义diff算法在运行时或空间中是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

读取一个文件,将每个文件名放入类似HashSet的数据结构中,并O(1)添加并O(1)包含实现.

然后读取seconds文件,根据HashSet检查每个文件名.

如果文件1具有长度m并且第二文件具有长度的总算法n是O(m+n)根据需要.

注意:该算法假设数据集在物理内存中非常适合快速.

如果数据集不能容易地适合存储器,则可以使用具有磁盘分页的B树的一些变体来实现查找.然后,复杂性将是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更多的内存.