4

我有两个文件 - 我们称它们为 file0 和 file1。

我想得到的是针对以下问题的快速算法（我很清楚如何编写一个相当慢的算法来解决它）：

检测file0的最大后缀，它是file1的前缀，这意味着一个最大长度的内存块B（或更准确地说：这样一个内存块的字节数），使得

  • file0 由一些内存块 A 组成，然后是 B
  • file1 由内存块 B 组成，后跟一些内存块 C

请注意，块 A、B 和 C 的长度也可以为零字节。

编辑（回答drysdam的评论）：我想到的明显相当慢的算法（伪代码）：让文件的长度以m为界，n与wlog m<=n。

for each length from m to 0
    compare the m last bytes of file0 with the first m bytes of file1
    if they are equal
        return length

这显然是一个 O(m*min(m, n)) 算法。如果文件大小相同，则为 O(n^2)。

我目前必须处理的文件大小为 10 到几百兆字节。但在极端情况下，它们的大小也可能只有几千兆字节——只是大到不再适合 x86 的 32 位地址空间。

4

3 回答 3

3

考虑将您的字节视为数字 0..255 作为整数 mod p，其中 p 是素数，可以选择远大于 255。以下是计算 b0*x^2 + b1*x + b2 的两种方法：

(b0*x + b1)*x + b2

b0*x^2 + (b1*x + b2)。

因此，我可以通过从左到右计算这个数量 - 乘以 x 并添加 b2，或者通过从右到左计算 - 添加 b0*x^2。

选择一个随机 x 并在 AB 中从右到左计算，在 BC 中从左到右计算。如果计算的值匹配，则记下位置。稍后对从最长开始的所有匹配项进行缓慢检查，以查看 B 在两种情况下是否真的相同。

随机匹配的机会是多少？如果您有错误匹配，则 (a0 - c0)*x^2 + (a1 - c1)*x + (a2 - c2) = 0。 d 次多项式最多有 d 个根，所以如果 x 是随机的错误匹配的机会最多为 d / p，您可以通过将 mod p 用于适当大的 p 来使这个值变小。（如果我没记错的话，有一个消息认证方案，其核心就是这个想法）。

于 2011-03-31T19:35:31.160 回答
1

根据您有多少可用内存，您可能需要考虑为第一个文件构建一个后缀树。一旦你有了这个，你可以查询与第二个文件的后缀最大重叠的第二个文件的前缀，方法是沿着与第二个文件前缀的字母匹配的边缘从根部向下遍历后缀树。由于后缀树可以在线性时间内构建，因此使用您的术语，此算法的运行时间为 O(|A| + |B|)，因为构建后缀树需要 O(|A| + |B|) 时间O(|B|) 时间遍历后缀树以找到块 B。

于 2011-03-31T11:29:43.420 回答
1

如果这不是学术任务，那么实施最简单的解决方案并查看它在您的数据上的表现可能是有意义的。

例如，理论上更有效的基于 Knuth-Morris-Pratt 算法的解决方案可能比基于 IndexOf 的解决方案执行得更差（请参阅重叠检测）。

对于大文件，您的程序可能一直在等待 I/O。

于 2011-03-31T20:11:19.360 回答