zhangge's stupid and messy life

对学校查重系统的一些思考与猜想

07 Apr 2012

每个学期我们都要做各种实验和课程设计，然后提交那boring and useless的实验报告，最不爽的就是还要通过那个可恶的查重系统，一旦不通过就要面临没分的危险。

于是，很无聊的我，在吃饭的时候，对这个查重系统思考了一下，然后查了一些资料，再对它的内部猜想一下。

对于检查抄袭，最直接的想法就是，拿两篇报告对比一下，当出现相同的内容的时候，就记录一下，最后结束的时候计算一下相同的百分比达到多少。

但是，计算机没有人的思维，怎么对比？

我们定义一下，有N个学生，每个学生作为一个用户user，N={u1, u2, ……, un}

某个user有一篇报告C，则一篇报告里面包括了许多内容，我们定义报告里面的每一个内容作为一个item，则C={i1, i2, ……, in}（注意，这里的报告划分内容会影响到系统的结果，我们可以定义一个item为一段话、一句话、一个短语、一张图片等等）这样，每个用户都有一个item集合。

有了上面的定义后，我们很容易想到如何比较两份报告的相似度。

U1和U2的相似度为

similarity(U1, U2)=

C1^C2

/

C1VC2

（Note，这个的^字符是交集的意思，V是并集的意思，整个公式就是说U1和U2的相似度等与U1和U2的交集除以并集）

好了，到了这里，大家都很容易想到，只要把每个用户的报告划分成item集合，然后进行比较就可以达到查重的目的了。没错，而且对于我们的报告一般都是office文档，所以，我建议使用面向对象的方法来解析文档，所以用java的话使用apache的一个开源框架POI就可以实现了。地址：http://poi.apache.org/

到了这里，的确可以比较出用户的相似度，但是，效率如何呢？假如有1000个学生，理论上来说，我们要两两比较，则比较的次数理论上来说就是1000x999/2，假如1s比较一对的话，一天86400s，那么就需要5到6天的时间来查重，假设一个报告1M，那么载入内存至少需要1G的容量，第一次载入内存开销比较大，比较耗时，后面效率就高一点，但是还是已经超出了人类的容忍程度，想想，要是扩大规模来应用这个系统，那就更不堪设想，再厉害的机器也伤不起啊，哥不是富二代，哥玩不起啊！！！

好吧，天无绝人之路，再猜想一下！ 假设U1的报告内容集合为C1={a, b, c, d}，U2的报告内容集合为C2={b, d, e, f},看到没有，这明显就是两个向量嘛，好，一维向量貌似处理起来不太容易，那就构建矩阵：

Elements(行元素)  C1(U1)  C2(U2)
a							1			0
b 							1			1
c							1			0
d							1			1
e							0			1
f							0			1

这个矩阵很容易看明白吧，第一列向量就是报告的内容，第二列向量就是U1的内容集合，第三列向量就是U2的内容集合，如果一个用户的报告含有该内容则用1表示，否则用0表示。灰常明显就可以计算出来U1和U2的相似程度，同一行里面如果都是1的话，则两个用户的内容相同，这里b和d内容相同，则similarity(U1,U2)=2/6.

现在，你依然会想，这没有实质的改变啊！没错，我们只是换了一种思考方式而已，并没有提高效率！

OK，我们创建一个函数H，对U1和U2分别求值，H(U1)=a, H(U2)=b. 函数内部是取出U1这个向量的第一个1对应的element。明白了吧？ 高手都知道，嗯，没错，H就是hash函数。

数学高手，概率高手，出现吧！

我们取一个随机变量r(H(U1)=H(U2))，然后对r求概率.

哈哈，就是这样,P[r(H(U1)=H(U2))] = similarity(U1,U2) = 2/6

不明白？是不是概率没过啊？唉，私下交流！

其实r是相似度similarity的一个无偏估计量！

有了这个结论，我们就可以用概率来求相似度了。现在知道高数的作用了吧，是不是有点后悔没有好好学啊？听哥说，重修刷分去！

那怎么算概率啊？ 我们以行为单位，对上面的矩阵进行一次随机的排列，例如结果如下：

Elements(行元素)  C1(U1)  C2(U2)
c							1			0
d							1			1
e							0			1
f							0			1
a							1			0
b							1			1

再对U1和U2进行hash，H(U1)=c, H(U2)=d。这样大概理解了吧？

理论上对行进行全排列，每一次排列就hash一次，最终你总能算出它们的概率！

不会吧？就算用我们发达的大腿来想想都知道不太实际啦。

每次排列完成后都要存储一下，然后再比较，依然是效率不高，扩展性不好。

那好，我们采用估算的方法来做，只要达到一定精度也就可以啦。

那就对所有的全排列只取几百种排列或者几千种排列就可以了，这样的话，你的规模就瞬间降低，效率迅速提高！先开心一会吧！

However，假如，我的行数是几百万行或者几十亿行呢？尼玛的，别说只取几百种排列了，就进行一次随机排列，那都是非常耗时的。

So？还好，存在hash这种东西！我们只要随机选择n个hash函数，然后对element(行号)进行求值，然后进行排序，这样不就是可以模拟出随机排列了吗？因为对于hash函数，变量(key)不一样，它的函数值(value)也就不一样，如果一样的话也可以解决冲突，而且，我们选择hash的范围是0~2^64-1，而element的规模是0~2^32-1。这已经是天文数字了，你再不满意的话我也没办法！

选择n个hash函数进行计算绝对比进行随机排列的效率高，如果你不了解hash的话，看一下wikipedia的资料吧, 传送门：http://en.wikipedia.org/wiki/Hash_function

好了，现在从概念上解决了一个困难！但是，接下来怎么办？生成多少个hash函数？最终还是要从n个学生那里两两比较求相似的概率啊？效率上还是没有大大提高啊！

这样，我们采用一个分组的概念，将n个用户（学生）分成m个组，如果两个用户的相似程度在一个下界之上的话，则他们被分到同一个组里面去。显然，这是一个多对多的关系，一个用户可能被分到几个分组里面去，一个组里面含有多个用户。

有了这个理念以后，只要找到某个用户他所在的所有组，然后和这些组里面的所有用户（除了自己）比较相似度就可以了。非常明显，你比较的次数已经下降了N多。

爽YY了，这样你已经省下了很多电费！但是，怎么分组啊？

Hash真牛B，还是要继续用到它！

这样，对于每个用户，我们选择p个hash-key来连接，然后映射到q个hash-bucket里面去。 这里的每个hash-bucket就是一个组。这里的关于hash的概念如果不了解的话，请到wiki看一下hash table吧！传送门：http://en.wikipedia.org/wiki/Hash_table

简单地说，就是选择pxq个hash，对每个用户的item集合求值，每次选择最小值，最后把pxq个value分成q个组。

到这里，又解决了一个困难，我们的查重系统的效率已经非常高了！

如果到这里，你感觉到很乱，看不懂的话，正常！因为我也是，里面非常多的问题我没有想明白，目前我也在思考当中，以上的一切都是我的一些猜想而已。

要搭建这么大的一个系统绝对不是一件容易的事，目前哥只有理论想法，哪路牛人想要做这样的事情可以跟我交流一下！

哥我是走技术流派路线的，不是走学术流派路线的，所以很多地方我的论述是有问题的，思考过程肯定有很多漏洞！读者如果发现bug，尽管提出，我们一起探讨！

各路牛人如果对此感兴趣的话，真心希望一起交流！ 希望学术派牛人提出一些改善此算法的看法！ 希望技术派牛人提出一些搭建次系统的看法！

PS： 原创日志，转载注明出处！ 这是我第一次发技术类的日志啊！希望多多支持！以后继续发此类日志！

---