利用滚动哈希实现抄袭的Rabin-Karp算法

Question

我使用拉宾-卡普算法来检查任何两个源代码文件的抄袭，所以首先我简单地用c#实现了它的算法，这里是它的代码，但它在O(p)空间中的平均和最佳运行时间是O(n+m)，但它的最坏情况时间是O(nm)。

 public void plagiarism(string [] file1, string [] file2)
    {
        int percent = 0;

        for (int i = 0; i <(file1.Length - file2.Length +1); i++)
        {

            for (int j = 0; j < file1.Length; j++)
            {
                if (file1[i + j - 1] != file2[j])
                {


                }

                    percent++;
                Console.WriteLine(percent);
            }


            Console.WriteLine("not copied");
        }

    }

那么，如何通过使用滚动哈希函数来提高效率，因为这比这更好。

Answer 1

Wikipedia article对该算法进行了相当好的讨论，甚至提到了如何实现滚动散列函数(请参阅“使用散列进行移动子字符串搜索”)。它还解决了如何使用哈希表或布隆过滤器来提高运行时速度。

您还必须理解，最坏的情况是一个相当人为的例子。维基百科文章中给出的示例是“在1000万个”a“的字符串中搜索后跟"b”的字符串。“

您应该能够使用该Wikipedia条目中描述的技术来实现滚动哈希。如果你在实现这一点上有困难，可以留下一个关于它是如何做到的更具体的问题，展示你已经尝试过的东西。

在实际文档中，您不太可能遇到任何接近最坏情况的情况。即使遇到最坏的情况，滚动哈希也不会降低复杂性。实现滚动哈希可以在运行时实现线性改进，这将被n*m的复杂性所淹没。如果你发现最坏的情况经常发生，那么你可能需要一个不同的算法。

另一件需要注意的事情是，虽然O(m*n)可能是一个问题，但您必须考虑其规模。您正在检查的文档有多大？你说你正在处理源代码文件。如果您正在查看典型的类项目，那么您可能会谈论大约2,000行代码。这些文档不会展示最坏的情况。即使他们这样做了，n*m也不会是一个非常大的数字。

但是，如果您有100个文档，并且您想知道其中任何一个文档是否与另一个文档有实质性的重复，那么更大的问题是O(n^2)，因为您必须将每个文档都与所有其他文档进行核对。文档比较的数量等于(n*(n-1))/2。如果你想优化你的过程，你需要一个不同的算法。理想情况下，它会为您提供文档的“指纹”。这样，您就可以计算每个文档的指纹一次，然后比较指纹的相似性。

文档指纹识别是一个众所周知的问题。然而，构建一个用于比较的指纹就不那么简单了。你会想要研究一种名为shingling的技术。我还看到了一些关于使用小的Bloom filter (256字节左右)来表示文档的研究，以及使用它进行快速比较的能力。

综上所述，我怀疑如果您谈论的是一两百个源代码文件，每个文件可能有1000或2000行长，那么使用一个好的Rabin-Carp实现的朴素的O(n^2)比较技术将会做您想要的事情。这将需要一些时间(您将进行5000个单独的文档比较)，但我认为R-K实现的速度不会是您的限制因素。