使用滚动哈希实现Rabin-Karp算法进行抄袭检测

Question

我正在使用Rabin-Karp算法检查任意两个源代码文件的抄袭情况。首先，我用C#实现了它的算法，以下是它的代码。但是，它的平均和最佳情况的运行时间为O(n+m)，在空间上为O(p)，但是其最坏情况的时间复杂度为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");
        }

    }

那么如何通过使用滚动哈希函数使其更加高效呢？因为这比现有方法更好。

- Rdx

---

你尝试过什么？换句话说，你的问题是什么？你发帖说你想使用“滚动哈希函数”..好的..你如何尝试将其转换为那个函数？你遇到了什么问题？ - NotMe

让我们从一些基础知识开始：问题在于你不知道如何实现“滚动哈希函数”还是你不知道它是什么？ - NotMe

请查看以下两个链接：https://dev59.com/MHRB5IYBdhLWcg3wH0WW 和 https://dev59.com/CHE95IYBdhLWcg3wbtbO。 - NotMe

最近我学习了哈希表，可能是因为这个原因导致它发生了。 - Rdx

仅仅通过重命名变量和函数，你的算法无法检测到抄袭。 - parapura rajkumar

Answer 1

维基百科有一个相当不错的算法讨论，甚至提到了如何实现滚动哈希函数（参见“使用哈希进行子字符串搜索”）。它还介绍了如何使用哈希表或布隆过滤器来提高运行时速度。

您还需要了解最坏情况是一个相当牵强的例子。维基百科文章中给出的例子是在一串包含1000万个“a”的字符串中查找一个由10000个“a”后跟一个“b”的字符串。

您应该能够使用维基百科中描述的技术实现滚动哈希。如果您在实现过程中遇到困难，请留下更具体的问题，说明您已经尝试过什么。

在实际文档中，您不太可能遇到接近最坏情况的情况。即使您遇到了最坏情况，滚动哈希也无法减少复杂性。实现滚动哈希可以线性改善运行时间，但这种改善将被 n*m 复杂度所淹没。如果您发现最坏情况经常发生，那么您可能需要使用不同的算法。

另一个需要注意的是，虽然 O(m*n) 可能会成为问题，但您需要考虑规模。您正在处理源代码文件。如果您查看典型的类项目，则可能涉及大约2000行代码。这些文档不会展示最坏情况。即使它们这样做了，n*m 也不会是一个非常大的数字。

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

文档指纹是一个众所周知的问题。但是，构建可用于比较目的的指纹略微复杂。您需要研究一种称为shingling的技术。我还看到一些关于使用小型布隆过滤器（大约256字节）来表示文档并能够使用它进行快速比较的研究。

尽管如此，我认为如果您处理的是大约100或200个每个文件长度为1,000到2,000行的源代码文件，则使用良好的 Rabin-Carp 实现的朴素 O(n^2) 比较技术将能够满足您的需求。它需要一些时间（您将进行5,000个单独的文档比较），但我不认为 R-K 实现的速度会成为您的限制因素。

- Jim Mischel

---

嗯，我已经阅读了这篇文章。首先，我会从基础开始，比如 R.K 算法，然后我肯定会选择指纹技术来检查大量的文件..............非常感谢:) - Rdx