6

我正在使用 Rabin–Karp 算法来检查任何两个源代码文件的抄袭所以首先我简单地在 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");
        }

    }

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

4

1 回答 1

5

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

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

您应该能够使用该 Wikipedia 条目中描述的技术来实现滚动哈希。如果您在实施时遇到困难，请留下一个关于它是如何完成的更具体的问题，展示您尝试过的内容。

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

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

但是，如果您有 100 个文档，并且您想知道是否有任何一个是另一个的大量副本，那么您的更大问题是 O(n^2)，因为您必须检查每个文档与所有其他文档。文档比较的次数等于(n*(n-1))/2。如果您希望优化您的流程，您需要一个不同的算法。理想情况下，可以为您提供文档的“指纹”。这样，您可以一次计算每个文档的指纹，然后比较指纹的相似性。

文档指纹识别是一个众所周知的问题。然而，构建一个对比较有用的指纹并不那么简单。你会想研究一种叫做 shingling 的技术。我还看到了一些关于使用小型 Bloom 过滤器（256 字节左右）来表示文档以及使用它进行快速比较的能力的研究。

综上所述，我怀疑如果您正在谈论一百或两个源代码文件，每个文件可能有 1,000 或 2,000 行长，那么使用良好 Rabin-Carp 实现的天真 O(n^2) 比较技术将完成您的工作想。这将需要一些时间（您将进行 5,000 次单独的文档比较），但我认为 RK 实施的速度不会成为您的限制因素。

于 2011-12-08T22:07:51.090 回答