Mctrain's Blog

What I learned in IT, as well as thought about life

Fingerprint算法查抄袭

| Comments

这两周在改学生的Lab,据说有很多人直接抄了github上的代码,就把Naruil以前写的查抄袭软件拿来用了下,感觉超有效果,绝对是TA的利器。不过虽然查抄袭这件事本身很方便,写个配置文件输个命令就结束了,不过之后要处理的事就麻烦多了,要回复一堆学生的邮件,巨花时间,所以建议助教还是少干查抄袭这件事,实在是件吃力不讨好的活。

闲话扯到这,其实在我前年的一篇博客就提到过Naruil的这个查抄袭算法,不过当时主要是介绍关于TCP redundancy的,它用到的也是fingerprint算法,而在那篇博文中也提到Naruil用lua写的查抄袭软件其实是基于一篇Sigmod’03的paper:Winnowing,今天就根据这篇论文来介绍下fingerprint算法以及Naruil是如何把它应用在查抄袭这件事儿上的。

首先,根据Winnowing的作者的经验,查抄袭的算法必须满足以下三个条件:

  • 必须不被像”空格“、字母大小写、标点符号这类字符或token影响(以及在检查代码时不被变量名、函数名影响);
  • 必须忽略一些短词对整个算法的影响,比如两个文档中都有很多”the“,但是其实这并没有什么意义;
  • 必须是”position independence“,即不能因为在某个文档中调换了下”子字符串“顺序,增加了或减少了某些”子字符串“而受影响。

而fingerprint算法解决了这三个问题!

首先我们先来描述一个最常见的fingerprint算法:k-gram。将一个文档的字符串分成长度为k(k为可选参数)的子字符串集(k-grams),然后将这些子字符串各自算个hash值,然后再在所有这些hash中选取出来一个子集,这个子集就是这个文档的fingerprint。

举个例子:

对于字符串:

A do run run run, a do run run

我们先把一些不相关的字符(如空格)去掉,变成:

adorunrunrunadorunrun

然后分成n-k+1个长度为k(假设这里k取5)的子字符串:

adoru dorun orunr runru unrun nrunr runru unrun nruna 
runad unado nador adoru dorun orunr runru unrun

再通过一种hash算法把这些子字符串分别算一个hash值:

77 72 42 17 98 50 17 98 8
88 67 39 77 72 42 17 98

之后问题就变成”如何在所有的hash值中选取一个子集“,即如何sample。最极端的方法就是选取所有的hash值,但是这样就会把原来的n个字符变成(n-k+1)*n个字符数进行计算,这样会产生巨大的计算量。

另外一个之前比较成熟的算法叫0 mod p,即选出这些hash值中mod p为0的值。比如对于上面的例子,可以选取p=4,则选取出来的hash为:

72 8 88 72

这种算法的好处在于:对于一个确定的值p,它的实现非常简单,而且基本上可以sample出大约1/p的hash值。但是它有一个缺点,即无法保证两个文档某个段落中的重复被查出来。这个是什么意思呢?让我们假设两个被选出来的hash值对应在文档中的内容之间的距离叫一个”gap“,那么这个”gap“的最大值是unbounded的!也就是说,通过0 mod p这种方法,我们无法保证在”gap“为t之内的一段文字所产生的t-k+1个hash被选取出来。

不知道讲清楚了没有,如果还有问题,那么再具体一些:假设我们有一个文档D,字符数为105,采用k-gram算法且k取值6,则它会产生105-6+1=100个hash值,文档D有5个段落p1, p2, p3, p4, p5,假设使用0 mod p算法,p取值10,那么很有可能这(105-6+1)/10=10个hash值只分布在段落p1, p2, p4中,而p3和p5中没有一个hash值被选取出来。虽然这种概率不大,但是我们不能保证p1~p5这5个段落都有值被选取出来进行比较。

其实还有一种sample的方法,就是每次选取所有hash值中最小的n个。这个方法其实效果也挺好的,不过它的缺点在于如果我们是比较那种containment的情况,即类似于一个文档包含另一个文档的情况,这个就会有问题。即使我们根据产生的hash值数目的比例来选择最小的n个值,比如文档A产生了100个hash值,文档B产生了50个hash值,那么我们在文档A中选取最小的10个,文档B中选取最小的5个,它还是无法保证在文档A中选取的10个hash值中存在和文档B相对应的子文档的hash值(因为可能在文档A中较小的hash值都分布在其他段落中)。

关于k-gram fingerprint算法,还有一点需要提到的,就是如何计算hash值。有一个很有名的算法叫做Kar and Rabin's algorithm,它采用了一种叫做”rolling“的方法,使得第i+1个k-gram能够很快地从第i个k-gram中计算出来。具体流程是这样的:

我们假设一个k-gram c1…ck是k个b位数,它的hash值的计算方法就是:

c1*b^(k-1) + c2*b^(k-2) + ... + ck

那么它的下一个k-gram c2…c(k+1)的hash值的计算方式则是:

H(c2...c(k+1)) = (H(c1...ck) - c1 * b^(k-1)) * b + c(k+1)

或者:

H'(c2...c(k+1)) = ((H'(c1...ck) - c1 * b^k) + c(k+1)) * b

上面讲的就是通常的k-grams fingerprint算法,当然还有一些不是基于k-grams的算法,这里就不说了。fingerprint算法可以满足最早提到的查抄袭系统的三个要求:

  • 它会将一些不相关字符(如空格等)先去掉,避免其对结果造成影响;
  • 对于小于k长度的子字符串它都不会计算hash,从而不会对结果造成影响;
  • 它并不需要和位置相关,不同位置的相同k长度的子字符串如果得到的hash值都被sample出来了,那么也会被检查出来。

接下来就要讲下这篇文章的算法——winnowing。

winnowing也是一种k-grams算法,区别在于它sample hash的方式,它解决的就是0 mod p中遇到的问题:unbounded gap。它的方法其实非常简单:

还是利用上面给的例子,得到的hash值是:

77 72 42 17 98 50 17 98 8 88 67 39 77 72 42 17 98

假设我们希望任意t个字符之内(不包含t)的重复都能被查出来,那么我们就设置一个窗口(window)w=t-k+1。举个例子,比如在上面5-grams的例子中我们希望t=8,那么我们就设置w=8-5+1=4,于是,得到了以下14个hash值的窗口:

(77, 74, 42, 17) (74, 42, 17, 98) (42, 17, 98, 50)
(17, 98, 50, 17) (98, 50, 17, 98) (50, 17, 98,  8)
(17, 98,  8, 88) (98,  8, 88, 67) ( 8, 88, 67, 39)
(88, 67, 39, 77) (67, 39, 77, 74) (39, 77, 74, 42)
(77, 74, 42, 17) (74, 42, 17, 98)

然后我们选出每个窗口中的最小值,这里需要注意的是,相连几个窗口的最小值可能指的是文档中同一个hash,这个时候我们只需要在这个hash第一次出现的那个窗口选择它就可以了,其它的窗口就不再需要选择最小值了。比如在这个例子中,前三个窗口的最小值都是17,而且指向的是同一个hash,所以我们只需要选择第一个就可以了,另外两个窗口都不需要选择,直到第四个窗口又出现了另外一个17。通过这个算法我们就可以sample出以下5个hash值:

17 17 8 39 17

于是这个就是这整个文档的fingerprint。之所以在这里要选择每个window的最小值,就在于这样可以得到很多相同的值,使得最后得到的fingerprint的hash数更少。比如上面得到的5个hash值有3个是重复的,如果应用的需求是和位置无关的话(比如后面会说到的查抄袭程序),则可以在最后的检查过程中把3个”17“变成1个”17“,整个fingerprint就变成:

17 8 39

很容易可以看出这种sample的算法选出的fingerprint可以满足它的需求:

  • 如果任意t长度的字符之内(不包含t)存在重复,它都能得到它其中某个k长度的子字符串的fingerprint,并检查出来;
  • 任意小于k长度的噪声子字符串都不会对结果产生影响。

接下来就来说下Naruil是如何利用winnowing算法进行查抄袭的:

  • 由于是检查C/C++代码的抄袭情况,所以对于任何需要检查的文件,先要用一个语义分析器把所有的关键字、变量名、函数名等变成一个个token(这里的token其实就是不同的数字),然后把空格、注释、标点符号,以及support code等去掉;
  • 通过上一步,把任意文件都变成了一个长度为n的token串,然后选择了一个k值(Naruil选的是7,据说是实验了好几次得到的结果),把这个token串分成n-k+1个长度为k的子token串;
  • 将这些子token串分别算一个hash值;
  • 选择一个w(window)值(Naruil选择的是5),将上一步算出来的hash值按顺序填入每一个window中;
  • 然后利用前面说的winnowing算法选出每个window中的最小hash值;
  • 将这些选出来的hash值去掉重复的,得出来的hash值就是这个文件的fingerprint
  • 最后就把每一个学生相同文件的fingerprint进行比较,得到任意两个文件相同hash值的比例,就是这两个学生该文件的重复率了。

通过这个算法最后得出来的效果还蛮好的,如果去看重复率在70%以上的学生的代码会发现大部分可以很明显地看出来抄袭的痕迹,就是把变量名改一改,把函数顺序换一换什么的。

Comments