检测某个文件的最大后缀，该后缀是另一个文件的前缀。

Question

我有两个文件 - 让我们称它们为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位地址空间了。

- Nubok

---

你的算法有多慢，你需要它有多快？我可以想出一个算法，但我不知道它是否比你的“慢”算法更慢。 - drysdam

Answer 1

考虑将您的字节视为0..255作为模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，并且您可以通过对suitably large p进行mod p运算来使其变小。（如果我记得正确，有一种消息认证方案，其核心思想就是这个）。

- mcdowella

Answer 2

根据您可用的内存量，您可能需要考虑为第一个文件构建后缀树。一旦您拥有了这个，您可以通过沿着与第二个文件前缀匹配的边从根向下遍历后缀树来查询最大重叠的第二个文件的后缀。由于后缀树可以在线性时间内构建，因此该算法的运行时间是O（|A| + |B|），使用您的术语，因为构建后缀树需要O（|A| + |B|）时间，并且遍历后缀树以查找块B需要O（|B|）时间。

- templatetypedef

---

这看起来是个不错的想法。线性于较小文件大小的长度已经足够快了。 - Nubok

如果您能给出一些提示，如何处理后缀树“不适合”内存的情况（因为X86的32位地址空间限制），我将非常满意。 - Nubok

如果其中一个文件可以拥有适合内存的后缀树，而另一个文件则不行，您可以反转这两个文件，为第二个文件构建一个后缀树，然后找到第一个文件的最长后缀，它是第二个文件的前缀。这样做可行吗？ - templatetypedef

我清楚地认为你可以将自己限制在较小文件的大小范围内。正如我在评论中所说：大多数文件都足够小（10到几百MB），但它也应该能够处理几GB大小的文件。我认为为了处理这些文件，我会编写一个小型内存管理器，将后缀树的未使用部分交换到磁盘上 - 这不是最快的方法，但它能够完成工作。 - Nubok

Answer 3

如果这不是一个学术任务，那么实现最简单的解决方案并观察其在数据上的表现可能是有意义的。

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

对于大文件，您的程序可能会花费所有时间等待 I/O。

- jfs