从100万篇文档中找出相似度较高的文档对

当我们想从100万篇文档中找出相项较高的文档对，就需要两两相互比较，一共是5千亿次，如果每次比较花费1微秒，那一共需要6天才能计算完，这肯定是不行的。 问题应用： 1、论文查重，读过大学的就都听过这个词，让无数人崩溃的查重，就是本题的一种应用，只是

当我们想从100万篇文档中找出相似项较高的文档对，就需要两两相互比较，一共是5千亿次，如果每次比较花费1微秒，那一共需要6天才能计算完，这肯定是不行的。

问题应用：

1、论文查重，读过大学的就都听过这个词，让无数人崩溃的查重，就是本题的一种应用，只是将一篇和上千万篇比较，但原理是一样的。

2、同源文档。我们再网站百度一些东西时，点开几个页面，可能发现很多页面及其相似，内容甚至重复，比如CSDN上的博客就有很多是从别的地方复制过来的，各个网站上的新闻等也有时候会相同或相似。如果一个网站汇总每天的新闻，那肯定是要能识别内容相似的两篇文章，选一个即可。

相似度定义：

Jaccard相似度：集合S和T的交集与集合并集大小的比率。加入S文档有三个字母A，B，C，T文档有5个字母B,C,D,E，F，那么S和T的相似度就是2除以6，三分之一。

问题处理

1、单个文档处理

步骤1——Shingling

文档一般都很长，总不能一个字符一个字符的比较，最有效的解决方法就是把整个文档拆分成短字符集合（长度为k），这样处理后如果集合中相同元素越多，那么相似度也就越高，同时还能忽略句子顺序（很多人抄论文时就经常改句子顺序）。

例：文档为abcdabd，选择k=2，那字符集合就是{ab，bc，cd，da，bd}。

当然k=2肯定是不行的，这样集合最大才是26^2，估计任何两个长文档都会认为相似。

具体k应该为多少呢？如果文档是邮件，那么k=5就够了，如果像论文这样大文档，一般k=9.

此外，文档中有很多次被称作停用词，像the，and，to等，一般是忽略这些词，因为对文章主题无作用。

步骤2——哈希

如果k=9，那么集合最大为26^9，每个元素需要9个字节来表示，而实际的集合大小是文档长度*9，现在我想把这多么元素哈希到2^32个桶中，这样每个元素就可以用4个字节来表示，这种做法的效果要比直接另k=4要好。原因是k=4时，实际集合中的元素最多为26^4，而且通常是20^4，因为像字母z，j的频率出现的次数是很低的。而9个字节的集合大小最大能达到26^9

感谢哈希算法一次。

步骤3——最小哈希

即使用4个字节的shingle，那么每篇文档难道要保存4倍的文档大小的信息？本步骤的目标就是将大集合替换成小很多的“签名”，通过计算签名集合的相似度来估计原始集合的相似的，当用50Kb的文档shingle到200Kb，而最后的签名集合只有1Kb时，最终差异值可能在几个百分点之内。

假设有M个文档集合，一共有N元素（所有集合中元素的并集，N很大），那么集合可以用一个N行M列来表示，当这个集合含这个元素时，对应位置为1，否则为0.

我们随机选择n（通常为几百）为签名大小，可以构建集合S的最小哈希签名向量[h1(r)，h2(r)...hn(r)]。

步骤如下：

初始矩阵SIG（大小n*M）都为正无穷，对每行r如下处理：

（1）随机选择n个哈希函数，计算出h1(r)...hn(r).

（2）如果原N*M矩阵对应位置为0，什么都不做，如果为1，那么将SIG中新的值变为hi(r)和SIG中原值的最小值。

也就是通过N步迭代，把原来的N*M大小矩阵，变成n*M大小的矩阵（对于一个文档来说，就是N变成了n）。

这种方法能估计准确有一定的理论依据，概括为：两个集合的两个最小哈希值相等的概率等于这连个几个的相似度。

再次感谢哈希算法。

2、整体文档处理

现在文档本身不是很大，但是需要比较的文档对的数目太大。 实际中我们关注的是相似度大于某个值的文档对，这样很多相似度较低的文档对是不需要比较的。 处理方法：局部敏感哈希（LSH） 我们对目标项进行多次哈希处理，使得相似项会比不相似项更可能到同一个桶中，然后只要比较同一个桶中的文档对。哈希到同一个桶的非相似文档对成为伪正例，而真正相似的分到两个桶的为伪反例，我们希望这两个越少越好。 一种有效的方法是将上面的n*M矩阵再分为b块，每块是r行*M列，（n=br）。将每个r长的序列哈希到一个大数目范围的桶。这样矩阵缩小为b*M，对于两列来说，只要有一行在一个桶中，就是相似候选对，这种方法的准确也是很高的，关于LSH技术详细理论分析可以查看其他文献。 这种LSH技术由于在过滤阶段非相似的数据对象大部分被过滤掉，因而极大地缩短了查询计算时间，提高了效率。 再次感谢哈希。 总结 最后总结这种问题常用思路: 1、先选择k，构建shingle集合，可以再通过哈希映射成更短的桶编号。 2、计算出最小哈希签名。 3、应用LSH技术构建候选对。 每一步都用了哈希算法，复杂度一再缩小。