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");
        }

    }

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

Answer 1

在维基百科的文章有算法的一个相当不错的讨论,甚至提到了如何实现滚动哈希函数(请参阅"散列用于移动字符串搜索的使用").它还讨论了如何使用哈希表或布隆过滤器来提高运行时速度.

您还必须了解最坏的情况是一个相当人为的例子.维基百科文章中给出的例子是"在一千万个"a"字符串中搜索一个10,000字符串的字符串,后跟一个"b".

您应该能够使用Wikipedia条目中描述的技术实现滚动哈希.如果你在实现这个问题时遇到了麻烦,请留下一个更具体的问题,说明它是如何完成的,展示你尝试过的内容.

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

另一件需要注意的是,虽然O(m*n)可能是一个问题,但你必须看一下规模.你正在检查的文件有多大？你说你正在处理源代码文件.如果您正在查看典型的课程项目,那么您可能会说2000行代码.这些文件不会出现最糟糕的情况.即使他们这样做,n*m也不会是一个非常大的数字.

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

文档指纹识别是众所周知的问题.但是,构建一个对比较有用的指纹并不那么简单.你想要研究一种称为shingling的技术.我还看到了一些关于使用小Bloom过滤器(256字节左右)来表示文档的研究,以及使用它进行快速比较的能力.

所有这一切,我怀疑,如果你正在谈论一百个或两个源代码文件,每个可能是1000或2,000行,使用良好的Rabin-Carp实现的天真的O(n ^ 2)比较技术将做你所做的想.这将花费一些时间(您将进行5,000次单独的文档比较),但我不认为RK实施的速度将是您的限制因素.