基于Low-IDF-SIG的句子重复检测

俞昊旻，张 玥，张 奇，黄萱菁

(复旦大学 计算机科学与技术学院，上海 201203)

1 引言

随着互联网时代的发展，信息呈现出爆炸式增长的趋势。由于数字文档本身易于被复制的特点，导致网络中出现了大量的重复网页和文档[1]。这些重复信息给基于Web的应用造成了严重的负担。因此，对于重复检测问题的研究，在近年来逐渐成为了信息检索领域的一个研究热点。

然而现有的研究工作主要着眼于如何进行文档级别的重复检测，如对文档级别文本特征选取的研究[2-7]，或是对文档级别快速拷贝检测系统的研究[8-11]。文档级别重复检测已经在一般网页的重复检测中取得了不错的成果。但目前仍存在一些未能很好处理的问题。两个较为典型的例子分别为文档中抄袭部分和引用部分的重复检测。由于抄袭通常不会是文档级别的抄袭，而是段落级别和句子级别的抄袭，即将他人文章中的部分段落或句子抄入自己的文章中，因此无法使用文档级别的重复检测方法有效地检测。而对于文档中的引用也存在相同的问题。在文章或是新闻中出现引用时，引用的通常会是几句话或是一个短小的段落，因此两个文档之间的相似度不会高，无法简单使用文档级别的重复检测方法。

除了以上的问题之外，在网页的重复检测中还存在一些不能使用文档级别重复检测方法解决的问题，如分页新闻以及论坛中帖子(Thread)等的重复检测[12]。这些问题的一个共同特点是，两个文档之中只是部分互为拷贝，这些部分拷贝需要基于更细粒度的句子级别重复检测的方法才能有效检测。我们在文献[12]中提出了一个两个步骤的解决方案： 首先进行句子级别的重复检测，即先检测文档中互为拷贝的句子对；然后，通过对互为拷贝的句子进行序列匹配，从而检测并定位出文档间互为拷贝的部分。如文档A中第i个句子到第j个句子的部分与文档B中第m个句子到第n个句子的部分互为拷贝，这样就将句子级别的重复检测提高到了段落的级别。

本文是对文献[12]的进一步深化，本文主要贡献主要有以下两个方面：

(1) 提出了一种改进型的句子级别的文本特征提取方法-Low-IDF-Sig算法。该算法可以高效地从句子中提取出表示整个句子核心内容的Low-IDF-Sig特征。

(2) 在句子级别的GoldenSet实验集上对我们的Low-IDF-Sig方法，以及现在已有的文档级别上较有代表性的方法(包括Shingling算法、SpotSig算法以及I-Match算法)进行了综合性的评测。评测结果表明了我们提出的方法在句子级别重复检测中，具有较高的精度，并对时间空间的占用较少，适用于句子级别重复检测。

2 相关工作

重复检测在过去的数年中成为了信息检索领域一个热门问题。至今为止，关于重复检测的研究工作大体上可以被分为两大类别。第一类研究工作主要关注如何使用特征来表示文档。另外，由于文档集合中通常包含上亿个文档，因此对它们之间进行比较的效率也成为一个研究热点。本文的工作集中于对句子级别文本的特征提取的精度和效率的研究上，因此在本节中对已有的文本表示方法进行简单的回顾。

2.1 DSC和DSC-SS算法

Border在1997年提出一种Shingling算法，即DSC (Digital Syntactic Clustering)算法[2]。该算法将文本按照若干个词一组组合起来，称为一个Shingle，而整个文本则由一个Shingle的集合组成。随后按照一种过滤策略，对集合中的Shingle进行筛选，由选中的Shingle参加比较，并使用Jaccard算法来衡量两个集合间的相似度。DSC中采取每25个Shingle中取一个的筛选方法，这种筛选方法虽然快速，但却极大地降低了算法的精度。

由于在文档集合较大时，DSC算法的比较次数过多，效率不高。因此在同年Border提出了DSC-SS算法，该算法将几个Shingle合并为一个SuperShingle，以减少比较次数，提高算法效率。该算法虽然总体上的精确性只是略有较低，但对于较为短小的文档却造成了比较精度的大幅下降[3]。

2.2 I-Match算法

I-Match算法[4]基于对文档集合的外部统计结果。I-Match算法将输入文档中的非常常见(即具有很低反向文档频数)与非常少见的Token(即具有很高反向文档频数)过滤掉，并将剩下的Token插入到升序排列的排序树中，对每一个Token，相加得到一个哈希值，直到文档结束为止。具有相同的哈希值的文档互为拷贝[4]。

I-Match算法的一个缺点是稳定性较差。如果文档中的一个词发生变化，则最后的哈希值就会发生显著的变化。一个解决方法是使用随机化的方法，如A Kocz等人在2008年提出的随机化的I-Match算法[5]。

2.3 LSH算法

Indyk和Motwani提出的LSH算法的基本思想为： 如果两个文本相似，可以用哈希函数将它们投影到相近的空间中[6]。具体来说，算法首先将文档转换为特征的集合，每一个特征有一个权重；然后利用LSH函数把特征向量转换为指纹；最后查找指纹的海明距离。该算法在文档级别的重复检测中也被广泛地使用。

2.4 SpotSig算法

2008年，M·Theobald等人提出了SpotSig算法[7]。SpotSig算法是Shingle算法的一种改良算法，该算法使用禁用词(Stopword)作为开始抽取Shingle的标志，并将先行词之后的数个词组合起来形成一个Shingle，作为一个特征。在比较时，SpotSig使用Jaccard相似度，并提出了一种基于文档特征向量长度的剪枝方法，大大提高了SpotSig在比较阶段的效率。尽管SpotSig特征在文档级别的重复检测中取得了很好的效果，但由于SpotSig特征选取有限的禁用词作为先行词进行特征抽取，因此在文本普遍长度较短的句子级别进行特征抽取时，无法抽取出足够多的优质特征以表示整个句子的核心内容，因此在精度上效果不好。

3 Low-IDF-Sig

句子级别上的文本重复检测的首要问题是如何抽取出足够的优质特征以很好地表示一个句子。好的特征抽取方法既可以大幅地提高句子重复检测的精度，又可以提高在句子两两间计算相似度时的效率。

我们在SpotSig基础上提出了一种新的改进算法Low-IDF-Sig，该算法选取一定数量的具有最低反向文档频数(Inverse Document Frequency，IDF)的常见词汇作为先行词，以抽取改进的Shingle特征，用以表示整个句子。

3.1 概念与标记方法

一个Low-IDF-Sig特征si可以表示为一条紧跟在一个先行词ai后的具有固定长度ci的词链，该词链的取词间隔为一个固定值dj。事实上我们使用标记ai(di,ci)表示一个先行词为ai，词链长度为ci，取词间隔为di的Low-IDF-Sig特征si。举例来说，as(1, 2)表示在句子中每次出现as时进行提取，其中提取的间隔为1，词链长度为2。注意如果在前一先行词的词链范围内出现了其他的先行词的情况下，有可能出现两个特征部分重叠的情况。

考虑如下的句子： “As we are taking your candidature ahead we would like to highlight that INTEL as an organization believes and practices high standards of ethical behavior from every potential candidate.”

假设我们从反向文档频数表中获得了前五个具有最低的反向文档频数的单词{as, to, that, of, from}作为先行词，并以ci=2作为词链的长度，di=1作为取词间隔，则我们可以将上面的句子变为如下的由Low-IDF-Sig特征组成的集合： S={as:we:are, to:highlight:that, that:intel:as, as:an:organization, of:ethical:behavior, from:every:potential}。可以看出上述集合已经很好地覆盖到了整个句子的核心内容。

Low-IDF-Sig特征作为一种改进型的SpotSig算法，与SpotSig算法主要存在以下几个差别：

(1) Low-IDF-Sig特征在选取先行词时，总是从作为外部资源的一个反向文档频数表中选取具有最低反向文档频数的前n个常见词作为Low-IDF-Sig特征的先行词；为了保证每个句子至少有一个特征，我们简单地选取句子中的第一个词作为一个特殊的先行词；

(2) Low-IDF-Sig特征在构成Shingle时，词链中不仅包括在先行词后提取的词，同时也包括先行词本身；

(3) SpotSig算法在选取构成词链的词语时，简单地跳过了所有的禁用词，即禁用词不会出现在任何一条词链中。SpotSig的理由是禁用词本身的语义信息较少，对于文档级别的文本来说可以忽略。但我们在实验中发现，对于文本长度较短的句子而言，禁用词仍对整个句子可以产生较大的影响，因此不应该简单地跳过所有的禁用词。在Low-IDF-Sig算法中，我们在选取构成词链的词语时，只跳过少部分的禁用词，这部分的禁用词包括部分的冠词与介词。原因是我们在实验中发现两个互为拷贝的句子，可能会使用不同的冠词或介词，但仍然表示相同的意义。

经过如上改进的Low-IDF-Sig特征可以克服SpotSig先行词不足的缺陷，保证即使在文本长度较短的句子中也能够抽取出足够多的特征，从而较好地覆盖到整个句子的核心内容，以提高句子级别重复检测的精度。

4 相似度计算方法

给定一个句子集，重复检测需要进行句子间两两的相似度计算。我们使用常见的Jaccard相似度作为相似度计算方法。假设两个句子经过上一节中的转换，变为了两个由Low-IDF-Sig特征组成的集合：A和B。注意到同一个Low-IDF-Sig特征可能在一个句子中出现多次，因此A和B实际上是一个包(Bag)，它们间的相似度定义为：

其中freqA(sj)表示特征sj在包A中出现的频率。freqB(sj)的含义类似。

5 实验

Low-IDF-Sig算法使用Java进行实现。实验机器配置为，处理器： Intel(R) Core(TM)2 CPU 6320 @ 1.86GHz 1.87GHz， 内存： 3.50GB。为了测试不同特征的性能，我们从ClueWeb09-T09B*http://boston.lti.cs.cmu.edu/Data/clueweb09/中手工选择了2 000篇文档，总共57 135个句子，并对其两两间是否互为拷贝进行了标注，以作为GoldenSet。

5.1 特征精度比较

我们使用标准的Precision、Recall和F1 Score作为精度的评测标准，对Shingle，I-Match，SpotSig特征在句子级别重复检测中的表现进行评测，以验证以上三种在文档级别表现较好的特征是否也能在句子级别取得较好的精度。

图1的左图显示了3-Shingle、4-Shingle、5-Shingle在调整相似度阈值τ时的F1 Score的变化。可以看出三者的表现在句子级别上较为相近，同时都在相似度阈值τ=0.6时获得了最高的F1 Score。其中3-Shingle在τ=0.6时，F1 Score达到最高值0.960。这表明Shingle特征在句子级别的精度也较高，但还需考察其在空间时间上的占用以决定其是否适用于句子级别的重复检测。

图1 参照特征的F1 Score变化趋势

图1的中图显示了I-Match特征在变化IDF范围时，F1 Score的变化。从图中可以看出，IDF范围取[0.3, 1.0]时，F1 Score达到最大值0.877。另外，可以发现I-Match算法在句子级别的表现要好于其在文档级别的表现[4]。这是因为在我们GoldenSet中可以发现，句子级别互为拷贝的两个句子，有80%以上是完全相同的句子，这与文档级别的情况有很大的差别。

图1的右图显示了SpotSig特征在变化相似度阈值τ时的F1 Score的变化，其中词链长度取3，取词间隔为1。M·Theobald等人发现在文档级别先行词只需选取24个禁用词时就可以取得足够好的F1 Score。但在我们的实验结果中可以发现，24个先行词无法从句子中抽取中足够多的特征，因此F1 Score较低。而选取全部共365个禁用词作为先行词时，总体的F1 Score较高，并在相似度阈值τ=0.7时得到最高值0.764。

接下来我们将通过实验对本文提出的Low-IDF-SIG特征在句子级别重复检测中的精度进行评测，以验证Low-IDF-SIG特征是否适用于句子级别。

图2的左图显示了Low-IDF-Sig特征在变化先行词数量时的F1 Score的变化， 其中相似度阈值τ此时固定为0.6，词链长度取3，取词间隔为1。可以看出Low-IDF-Sig特征在只选取了少量的先行词时就可以取得比较好的F1 Score值。随着先行词数量的增多，F1 Score略有上升后稳定在0.95左右。图2中右图显示了Low-IDF-Sig特征在变化相似度阈值τ时时的F1 Score的变化， 其中词链长度取3，取词间隔为1。可以看出先行词取10、500以及1 000时，F1 Score随相似度阈值τ变化的变化趋势基本相同。对比Shingle算法的结果图，可以发现Low-IDF-Sig与其表现出了相同的变化趋势。F1 Score的最大值出现在先行词取500个，τ=0.6时，为0.954。

图2 调整先行词数量(左)与调整τ(右)时Low-IDF-Sig的F1 Score变化

5.2 特征综合表现比较

接下来我们通过比较各特征的综合表现，以挑选出适合运用于句子级别重复检测的特征算法。

表1 各特征在GoldenSet上的综合表现

表1中显示了各个特征在GoldenSet上的综合表现。从表中可以看出3-Shingle在F1 Score一项上取得了所有特征中最高的0.960，但对比Low-IDF-Sig(50)的F1 Score来说，优势并不显著。且在空间占用上，Low-IDF-Sig(50)具有明显的优势，仅为3-Shingle的三分之一。从时间占用上可以看出无论是索引阶段还是相似度计算阶段，Low-IDF-Sig(50)都明显少于3-Shingle。特别是相似度计算阶段的用时仅为3-Shingle的1/11。3-Shingle用时过长的原因在于存在某些特征过于常见，即索引中该特征对应的句子过多，根据本文第4节中的介绍，假设该特征对应的句子数为n的话，则这n个句子进行两两比较，需要n2级别次计算。因此当句子数增长时，这部分的时间可能出现n2级别的增长。因此3-Shingle不适合大规模的部分重复检测任务。而I-Match尽管在时间与空间的占用上比Low-IDF-Sig(50)要少，但F1 Score却明显低于Low-IDF-Sig(50)，因此仅仅适合于对算法效率要求相当高，而对精度要求不高的任务中。另外Low-IDF-Sig(50)在空间、时间占用以及F1 Score上均要优于SpotSig。同时SpotSig在GoldenSet上抽取出的特征总数要多于Low-IDF-Sig(50)，也就是说SpotSig平均用于表示每个句子的特征要多于Low-IDF-Sig(50)，但其F1 Score却低于Low-IDF-Sig(50)。说明SpotSig抽取出的特征未能有效地表现句子的核心内容，因此Low-IDF-Sig比SpotSig更适合于句子级别的特征抽取。

综上所述，Low-IDF-Sig算法的F1 Score仅比3-Shingle略低1%，但算法的空间占用仅为3-Shingle的29%，同时索引阶段用时仅为3-Shingle的37%，而相似度计算阶段的用时更是仅为3-Shingle的8.6%。而对比I-Match以及SpotSig算法，Low-IDF-Sig算法的精度高出许多。因此该算法极适合于句子级别的特征提取。

6 结论

本文提出了一种高效的句子级别的文本特征提取算法——Low-IDF-Sig算法，该算法适合于句子级别的文本特征提取。在我们未来的工作中，我们希望能把Low-IDF-Sig算法用于大规模的部分重复检测任务中。

[1] D. Fetterly, M. Manasse, and M. Najork. On the Evolution of Clusters of Near-Duplicate Web Pages[C]//1st Latin American Web Congress, 2003: 37-37.

[2] A.Z.Broder, S.C.Glassman, M.S.Manasse, and G.Zweig. Syntactic clustering of the Web[J]. Computer Networks, 1997， 29(8-13): 1157-1166.

[3] A.Z.Broder. Identifying and filtering near-duplicate documents[C]//Proceedings of COM2000, London, UK, 2000： 1-10.

[4] A.Chowdhury, O.Frieder, D.Grossman, and M.C.McCabe. Collection statistics for fast duplicate document detection[J]. ACM Trans. Inf. Syst., 2002. 20(2): 171-191.

[6] P.Indyk and R.Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//STOC’98, New York, NY, USA, ACM. 1998: 604-613.

[7] M.Theobald, J.Siddharth, and A.Paepcke. Spotsigs: robust and efficient near duplicated etection in large web collections[C]//SIGIR’08, New York, NY, USA, ACM.2008: 563-570.

[8] N. Shivakumar and H. Garcia-Molina. Building a scalable and accurate copy detection mechanism[C]//ACM New York, NY, USA, 1996: 160-168.

[9] N. Shivakumar and H. Garcia-Molina. Finding near-replicas of documents and servers on the web[C]//Proceedings of WebDB 1998, London, UK, Springer-Verlag. 1999: 204-212.

[10] A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing[C]//VLDB ’99, pages 518-529, San Francisco, CA, USA, 1999: 204-212.

[11] K. Muthmann, W. M. Barczynski, F. Brauer, and A. Loser. Near-duplicate detection for web-forums[C]//IDEAS ’09, New York, NY, USA, ACM. 2009: 142-151.

[12] Qi Zhang, Yue Zhang, Haomin Yu, Xuanjing Huang. Efficient Partial-Duplicate Detection Based on Sequence Matching[C]//Proc. of the 33rd Annual ACM SIGIR, 2010: 675-682.