最近想要做一个查重程序，目的是检测大学生提交的电子文档的重复率。
最初的想法是是参考之王的论文查重，但是发现他有自己的弊端，也就是说知网论文查重的算法能对标准的论文进行有效的查重。但是对于学生提交的电子档作业就不一定行了。
我们先来看一下知网论文查重原理：
1：知网论文查重由于是采用了最先进的模糊算法，如果整体结构和大纲被打乱，可能会引起同一处的文章检测第一次和第二次标红不一致或者第一次检测没有标红的部分第二次检测被标红。因此在修改重复内容的时候尽量变换句式，不要打乱论文原来的整体大纲和结构。
2：整篇论文上传后，系统会自动根据文章生成的目录检测该论文的章节信息，然后系统会将论文分章节检测，可以获得每一单章节的复制比同时目录显灰色不参与正文检测；否则会自动分段按照1万字符左右检测，同时目录有可能当成正文检测，重复就会标红。
post~~知网检测目录原理：
目录一般放置在论文正文的前面，因而是论文的导读图。要使目录真正起到导读图的作用，必须注意：
1. 有明显的“目录”标记，目录两个字独占一行；
2. 目录需用word自动生成，不要手工书写；
3. 每个目录需用有明显的页码结尾，页码可以是阿拉伯数字或者是罗马数字；
4. 图目录或者表目录格式和正文目录格式一样；
5. 准确。目录必须与全文的纲目相一致。也就是说，本文的标题、分标题与目录存在着一一对应的关系。
6. 清楚无误。目录应逐一标注该行目录在正文中的页码。标注页码必须清楚无误。
7. 目录既然是论文的导读图，因而必然要求具有完整性。也就是要求文章的各项内容，都应在目录中反映出来，不得遗漏。
8. 知网目录识别标准：
正确的按照知网识别标准自动生成的目录如上图所示，这样的目录用知网检测系统生成的文本复制比报告单如下图：
很明显各个章节文本复制比一目了然，看起来更专业权威了。然而如果有丝毫的差错，知网检测系统都不会按照章节来进行检测，他会自动分段检测，一段大概1万字左右。
3：中国知网对该套查重系统的灵敏度设置了一个阀值，该阀值为5%，以段落计，低于5%的抄袭或引用是检测不出来的，这种情况常见于大段落中的小句或者小概念。举个例子：假如检测段落1有10000字，那么引用单篇文献500字以下，是不会被检测出来的。实际上这里也告诉同学们一个修改的方法，就是对段落抄袭千万不要选一篇文章来引用，尽可能多的选择多篇文献，一篇截取几句，这样是不会被检测出来的。
4：一篇论文的抄袭怎么才会被检测出来？知网论文检测的条件是连续13个字相似或抄袭都会被红字标注，但是必须满足3里面的前提条件：即你所引用或抄袭的A文献文总字数和在你的各个检测段落中要达到5%以上才能被检测出来标红。
5：知网检测系统会自动识别参考文献，参考文献不参与正文检测。并且进行剔除，在知网检测报告中参考文献显示灰色字体，说明并没有参与检测。当然这是在参考文献格式完全正确规范的情况下才会自动排除不会标红。否则参考文献会当成正文来进行检测导致参考文献全部标红。结果增高！
post~~知网自动识别参考文献原理：
6：知网论文查重为整篇上传，PDF或者Word格式对检测结果可能会造成影响。因为上传PDF检测，PDF会比Word多一个文本转换的过程，这个过程有可能会将你原本正确的的目录和参考文献格式打乱，目录和参考文献等格式错乱，就会导致系统识别不正确而被标红。特别对于那些有英文目录和大部分英文参考文献的论文，其英文占字符数很高。英文被标红就会导致总结果大大增高。
7：关于引用尽量引用整段话，如果引用单独一句两句，知网系统是根本识别不到具体你引用的是哪篇文章里面的句子。所以引用尽量大段引用。并且引用的内容必须完全一致。
如果你认真读了以上内容应该就能感觉到，知网的论文查重算法就是针对标准论文来的，对于只想要做学生作业的查重是不合适的。
不过从另外一方面来讲，知网的论文查重算法网上也没有公开Demo，所及就选择了另一种算法：SimHash算法
如果有兴趣可以看看原论文：
https://www2007.cpsc.ucalgary.ca/papers/paper215.pdf
这是运行出来的效果：
I am very happy that day!产生的字符串是：1111001111110101001111111111010011000001001101011011010000000001
I am very happy the day!产生的字符串是：0111111111100101001111111100010011000011001110111011010010000001
海明距离是：11
下面来讲解一下Simhash:
1：文本准备。
2：分词（根据行业特定的需求可以为不同的词定义不同的权值）：
- 给定一段语句，进行分词，得到有效的特征向量，可以自定义1-5等5个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。例如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。
3：对关键字进行hash形成签名（向量），如 CSDN 的签名是100101。
4：对向量加权：
- 在hash值的基础上，给所有特征向量进行加权，即W = Hash * weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。例如给“CSDN”的hash值“100101”加权得到：W(CSDN) = 100101_4 = 4 -4 -4 4 -4 4，给“博客”的hash值“101011”加权得到：W(博客)=101011_5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。
5：将各特征向量加权后的结果累加，得到一个向量。例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。
6：对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。
应用：
每篇文档得到SimHash签名值后，接着计算两个签名的海明距离即可。根据经验值，对64位的 SimHash值，海明距离在3以内的可认为相似度比较高。
- 海明距离的求法：异或时，只有在两个比较的位不同时其结果是1 ，否则结果为0，两个二进制“异或”后得到1的个数即为海明距离的大小。
举个例子，上面我们计算到的“CSDN博客”的simhash签名值为“1 0 1 0 1 1”，假定我们计算出另外一个短语的签名值为“1 0 1 0 0 0”，那么根据异或规则，我们可以计算出这两个签名的海明距离为2，从而判定这两个短语的相似度是比较高的。
换言之，现在问题转换为：对于64位的SimHash值，我们只要找到海明距离在3以内的所有签名，即可找出所有相似的短语。
但关键是，如何将其扩展到海量数据呢？譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢？
- 一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
- 大约需要四万多次的查询。
- 另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
- 大约需要占据4万多倍的原始空间。
这两种方案，要么时间复杂度高，要么空间复杂度复杂，能否有一种方案可以达到时空复杂度的绝佳平衡呢？答案是肯定的：
- 我们可以把 64 位的二进制simhash签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理），如果两个签名的海明距离在 3 以内，它们必有一块完全相同。如下图所示：
- 然后把分成的4 块中的每一个块分别作为前16位来进行查找，建倒排索引。
如此，如果样本库中存有2^34（差不多10亿）的simhash签名，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本。
- 假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ，四个块返回的总结果数为 4* 262144 （大概 100 万）。这样，原本需要比较10亿次，经过索引后，大概只需要处理100万次。
周末会把Demo传到GitHub上。
参考链接：
https://www.kancloud.cn/kancloud/the-art-of-programming/41614，by www.kancloud.cn
http://www.cnkis.net/html/1095371058.html ，http://www.cnkis.net/html/6389745413.html，http://www.cnkis.net/html/7096252235.html，by WWW.CNKIS.NET
https://www2007.cpsc.ucalgary.ca/papers/paper215.pdf by Gurmeet Singh Manku，Arvind Jain， Anish Das Sarma.
