枝网查重的研究

ASoulCnki:https://asoulcnki.asia/

GitHub:https://github.com/ASoulCnki

枝网查重的 idea 非常棒,实现出的结果也很有意思,可以找出所有偷来的小作文。

借机研究一下论文查重用到的(最简单的)算法是什么样的。


ASoulCnki 项目中指出,参考:李旭.基于串匹配方法的文档复制检测系统研究[D].燕山大学.

于是对这篇文章进行一个研读,大概搞懂了内容,粗略的记一下。

n-gram

如果两篇文章完全相同,只需要逐字比较。如果进行了一些词语的替换,甚至是更复杂的更改,实际上可以想到一种有效的比较方式:将文章分割成若干段,每一段与已有资料进行比较。

论文中给出的切分方式被称为 n-gram,即将文档分割为若干个长度为 n 的串,相邻串中 n-1 个元素是相同的。例如现在有串 abcde,令 n=3,则可以得到 abc bcd cde 这样的串。在具体实现时可以去除不相关因素(如空格,标点)。

抽样

这样会产生一个新的问题:当文本量过大的时候,产生的 hash 值过多。考虑选取大量 hash 值中的一部分,满足当抄袭长度在一定长度之上时,一定可以检测到。

具体来说,将 hash 值按类似 n-gram 的方法划分,每一组称之为一个窗口,之后在每一个窗口中取满足某种特征的值,如取最小值。可以采取这样的方案:在窗口滑动一次(选取下一个窗口)后,如果最小值不变,则不重复选取。

正确性:

令 n-gram 中分割长度为 n,抽样中划分的长度为 m,如果抄袭了长度为 t=n+m-1 的一段,考虑 t 这一段的前 m 个位置,它们组成一个窗口。以这些位置开始的,长度为 n 的段计算出的 hash 值,一定有一个被选取了。那么当抄袭长度不小于 t,一定可以找到。

复杂度:

如果在窗口滑动一次后,产生了新的特征值,记上一次的窗口为 A[l, r],这次为 B[l+1, r+1],其中 r-l+1 = m,那么一定是以下两种情况之一:

A 窗口选取的值为 l,或 r+1 位置的值更小。

我们可以大致认为 hash 值大小是随机的,那么滑动一次后产生新值的概率为 \(\frac{2}{m+1}\)。这是非常优秀的结果。

实现

实际上采用数据结构维护就可以了,关键问题在于 n 与 m 的选取。可惜论文中的结果是英文,且暂时看不懂枝网查重的 Java实现,就先放着了。