Content Reuse Detection 文章内容复用检测
原文在此：Efficient Overlap and Content Reuse Detection in Blogs and Online News Articles
该文主要讲述了在博客和新闻的文章中如何进行内容复用的检测。作者提出了一种基于签名索引(Signature-Indexing)的算法qSign(Signature-Indexing for Incremental Reuse Detection)。
所谓signature files，是指在一个文件中，所包含的每一个word都通过hash映射到一个固定宽度的bit串，并且有相同数量的bit位为1，这个bit串就是这个word的signature。然后将所有这些word的signature通过位或操作全部按位或起来作为file的signature。
这样一来，检测一个查询的word是否和file匹配的话，就看这个word的signature和file的signature按位与之后会不会发生变化，如果不变，则匹配。显然，这样的识别会造成错误的匹配，即false positive，该文的目标之一就是在控制住误识率的情况下提高预测的召回率(recall)。
在这里有必要先解释一下准确率和召回率。在一般的多类分类问题中，通常只有准确率一说，即分类正确的比例，而在一些特殊情况下，用户会比较关注某一类的分类情况，比如某一类A，这时候，显然不能使用总的准确率来衡量，因为很有可能A类的样本本来就少，比如只占1%，并且A类全预测错了，但其余部分预测正确，这样总的准确率高达99%。在这种情况下，为了衡量A的预测情况，引入了专门针对A类的准确率，即预测为A类的样本中有多少是正确的(确实是A类的)，但这个衡量标准显然是不够的，于是又引入了召回率，即A类的样本中有多少被识别出来了。
说的更具体一些就是：假设A类样本有n条，分类器预测为A类的样本有m条，而这m条中有k条其实是别的类别的，那么准确率就是(m-k)/m，而召回率就是(m-k)/n。
作者接下来介绍了如何通过控制signature不同bit的数目来控制误识率。
假设给定一个句子S1，包含n个words，它的signature宽度为m个bits，每个words对应signature中1的数目是l，那么这个句子的signature中某一位为1的概率为：1-(1-1/m)^(nl)
这个式子是这样近似来的，因为n个words的signature中各有l个1，所以该句子的signature可以近似看为初始时全为0，然后进行nl次这样的操作：每次从m个bit中随机抽取一个，将其置位为1。
再假设有另一个句子S2，它包含S1的n个words和k个另外的words，显然S2的signature包含了S1的signature中所有的1，并且可能还有更多的1，这些多出来的1就是由另外k个words产生的，那么某一位从S1中的0变为S2中的1的概率就是：
P_b(m,l,n,k) = (1-1/m)^(nl) * (1-(1-1/m)^(kl)))
进一步的，S1和S2的signature中正好有t位不相同的概率为：
P_e(m,l,n,k,t) = C(m,t) * P_b(m,l,n,k)^t * (1-P_b(m,l,n,k))^(m-t)
而S1和S2的signature中最多有d位不相同的概率为：
P_m(m,l,n,k,d) = Sigma[P_e(m,l,n,k,t)] while 0 <= t <= d
这样一来，通过d的选取就可以控制误识率了，设误识率希望控制在R，那么只要使得P_m(m,l,n,k+1,d) <= R，即任何包含超过k个单词的句子，其signature中的不同位数仍然在d以内的概率最多为R。
显然，每一个m位的signature可以对应到一个m维的空间，这样两个不同位数为d的signature在这个空间中的欧几里得距离就是sqrt(d)。
该算法的主要用到了两个数据存储，一个是signature的索引，一个是句子的单词哈希表索引，前者索引句子的signature，后者索引句子包含的word及对应的词频。
算法的主要步骤如下，主要分为两个部分，如下图所示。其中，1、2属于candidate-selection step，3-5属于post-processing step：
reuse-detection
- 1.给定了博客和新闻文章的输入流之后，从中提取出句子，插入到句子队列中。
- 2.对句子队列中的每一个查询句子做如下操作：
- 2.1. 计算出该句子的signature及单词哈希表(即单词与相应的词频)。
- 2.2. 将句子的signature映射到m维空间中的一个点。
- 2.3. 以该点为中心，在signature索引库中找出与该点举例小于sqrt(d)的句子，插入到候选队列中。
- 2.4. 将该句子插入到signature索引库中。
- 3.对候选队列中的每一个句子，在哈希表索引库中找出对应的哈希表，填入候选哈希表中。
- 4.对查询句子的哈希表(在2.1布种建立的)和候选哈希表进行hash join操作，通过word-overlap measure计算相似性分数，如果分数超过预定阈值，则输出。
- 5.将查询句子的哈希表插入到哈希表索引库中。
