面向文本拷贝检测的分布式索引

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

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

1 引言

在互联网中存在大量内容重复的相似网页。根据Broder等人1997年统计的结果,大约有41%的网页是重复的[1],在Fetterly等人2003年统计的结果中这个比例大约是29.2%[2]。很多Web应用,例如文本聚类[1],网页去重[3],抄袭检测[4],社区发现[5],协同过滤[6]等任务,都依赖于高效的文本拷贝检测。

为了减少比较次数,提升性能,倒排索引是拷贝检测任务中常用的数据结构。但随着文档集规模的增大,基于单台电脑的索引结构已经不能有效处理大规模文档集上的拷贝检测任务。为此需要采用分布式索引,通过并行计算提高处理能力。同时,因为数据集的规模将一直增大,一个好的分布式索引,不仅要能提升拷贝检测算法的效率,而且还必须具有良好的可扩展性。

Map-Reduce是一种并行编程范式,基于此范式可以实现具有良好可扩展性的算法[7]。本文中,我们采用Map-Reduce范式,对基于索引的文本拷贝检测进行如下几个方面的研究：

◦第一,分析比较了两种分布式索引结构：Term-Split索引和Doc-Split索引,并给出了Map-Reduce范式下的建立这两种索引的算法。

◦第二,基于上述两种索引结构,分别给出了Map-Reduce范式下的拷贝检测算法。并且通过实验,比较了两种算法性能上的差异。

◦第三,探讨了Map-Reduce范式下,中间结果数量对整个算法性能的影响,并进一步讨论如何更好的利用Map-Reduce范式实现算法的并行化。

本文的其余部分将按如下方式进行组织：第2节中,将说明基于索引的拷贝检测方法的基本思想。第3节中,将简要介绍Map-Reduce范式的相关内容。第4节将具体阐述如何在Map-Reduce范式下实现基于索引的拷贝检测方法。第5节和第6节分别介绍实验和结论。

2 基于索引的拷贝检测方法

给定一个文档集,在其之上进行文档间两两比较的拷贝检测,需要对n(n-1)/2个文档对进行相似度计算。这是一个O(n2)的算法。因此拷贝检测算法中,一般会采用倒排索引来减少所需比较的次数。因此索引结构的实现对拷贝检测算法的性能有至关重要的影响。不同的索引结构还会直接决定拷贝检测算法的实现。

另一方面可以看出,传统的单机索引结构已经难以适应越来越大的数据规模,需要引入分布式索引,以适应并行处理的需求。为此本文中将比较两种分布式索引结构,在此基础上,提出了两种基于分布式Index的拷贝检测算法。

为了方便讨论,本文中将整个算法分成三步：

◦第一步,Tokenize：遍历文档集中所有文档,对每个文档抽取特征。

◦第二步,建立分布式索引：在Tokenize基础上,建立分布式索引。

◦第三步,基于索引的拷贝检测：基于分布式索引,进行文档两两之间的相似度计算,得到内容重复的文档对。

2.1 文本特征与相似度计算

进行有效的文本拷贝检测,首先必须考虑两个问题,第一,从文本中抽取何种的特征来表征一个文档;第二,采用何种相似度的度量来表征两篇文档间的相似程度。本文中采用 Theobald等人提出的SpotSig算法对文档进行特征抽取,将文档表示成SpotSig(Si)的集合[8]。此外本文中将采用J accard相似度来表征文档的相似度。给定两个集合 A和B,集合 A、B的J accard相似度定义为[9]：

2.2 分布式索引

完整的索引一般包括两个部分：由词(Term)组成的词典和包含某个词的所有文档(Doc)的ID列表(Posting List)[10]。要实现分布式索引,就需要按照某种方式将一个完整的索引分割开来。有两种基本的分割方法,一种是按照词分割(Term-Split),另一种是按照文档分割(Doc-Split)。

图1 一般索引结构

如图1所示,一个索引可以看成一个二维表格,表格的行表示不同的词,表格的列表示不同的文档。Term-Split相当于将表格“按行横向分割”,首先将词典中的词划分为若干子集,每个节点只保存一个词子集以及相应的Posting List。Doc-Split则相当于将表格“按列纵向分割”,将整个文档集划分为若干个子集,对每个子集分别建立独立的索引,存储在不同节点上。

2.3 基于索引的拷贝检测方法

Lin提出了Map-Reduce范式下进行两两文档间相似度计算的算法Postings Cartesian Product(PCP)[11]。本文中将基于此思想提出基于Term-Split索引的拷贝检测方法。此外,本文将提出另外一种基于Doc-Split索引的拷贝检测方法。

2.3.1 Term-Split方法

对于Term-Split索引,每个索引分块中包含词典中的一部分词以及这些词所对应的Posting List。因此 Term-Split方法,首先从每个词的 Posting List出发,计算两篇文档在这个词上的“部分相似度”(partial contributions)[11],再对这些“部分相似度”进行综合,得出两篇文档间完整的相似度。在Lin的方法中采用的是向量点积作为相似度。而本文中采用J accard相似度。

如公式(1)所示,已知|A|、|B|,是两个文档的长度,所以只需要计算 A,B的交集大小,|A∩B|。亦即 A,B两篇文档共有的词数量即可。结合Term-Split索引,若两篇文档出现在同一个Posting List中,表明这两篇文档在该词上的“部分交集大小”为1。遍历所有词后,对所有文档对的“部分交集大小”进行综合,得到两篇文档的完整相似度,再与相似度阈值进行比较,决定是否为“拷贝”。

如图2(a)所示,对于每一个词所对应的Posting List,将Posting List中的Id两两组合,作为一个可能相似的候选文档对(candidate_pair)。考虑到两篇文档之间,每出现一个相同词,就会产生一个这样的文档对。因此只需要对于每一个候选文档对维护一个计数器(accumulator),统计该文档对出现的次数,得到的结果就是这两篇文档共有的词数量。最后根据计数器的值,计算所有候选文档对的相似度。

2.3.2 Doc-Split方法

对于Doc-Split索引,每个索引分块中包含一部分文档的完整索引。因此基于Doc-Split索引的方法,是把每一篇文档作为一次查询,在所有的索引分块中查找与其相似的文档。因为索引分块和文档内容都分别分散在不同的节点上,具体实现时可以有两种解决方式。一种方式是每次把作为查询的文档分发到各个节点上,在该节点上的索引中进行查重,另一种方式是每次把一个索引分块分发到各个节点上,把该节点上的所有文档作为查询进行查重。考虑到索引比文档本身更容易压缩,且压缩后体积较小,本文中采用后一种实现方式。

如图2(b)所示,每次首先将一个索引分块复制到所有节点上。然后在每个节点上,将该节点中的所有文档作为查询,在索引分块中查找拷贝。对每个作为查询的文档(doc_q)维护一组计数器,记录所有索引分块中文档(doc_i)与 doc_q的交集大小。每当doc_q与doc_i有一个相同词时,就将 doc_i对应的计数器加1。最后根据计数器的值,计算doc_q与所有doc_i的相似度。

图2 基于索引的拷贝检测方法

3 Map-Reduce范式

Map-Reduce范式是J.Dean等人在2004年提出的分布式编程范式[7]。它通过面向函数的抽象使得分布式程序的开发变得简单。在Map-Reduce编程范式下,数据被抽象为＜key,value＞的形式。而针对数据的操作被抽象为Map和Reduce两个操作。用户只需要提供自定义的两个函数实现Map和Reduce。剩余的工作,诸如数据分发,任务调度,容错,任务同步等工作可以交由框架处理。

如图3所示,一个Map-Reduce的任务包括两个阶段。第一个阶段为Map操作,首先将输入分割为小块,每一个小块都包含若干个＜key,value＞对。在这些数据分块上执行map操作,得到中间结果。中间结果同样以＜key,value＞的形式表示。接着,中间结果按照key进行sort和group,使key相同的结果合并在一起。第二阶段为Reduce操作,对相同key的中间结果进行合并得到最终结果,以＜key,value＞的形式输出。

图3 M ap-Reduce范式

4 实现细节

本节中将详细介绍本文所述方法在Map-Reduce范式下的实现细节。本节共分为三部分,分别讨论基于索引的拷贝检测方法的三步。

4.1 Tokenize

第一步,Tokenize所有文档。对于每个文档的操作可以完全并行,实现起来相对简单,仅需Map操作即可。如图4所示,每个Map任务接受一批文档作为输入,其中文档Id为key,文档内容为Value,对每个文档,抽取SpotSigs特征,将文档Id作为key,特征集合作为Value输出。

4.2 建立分布式索引

第二步,对文档建立索引。本文中分别给出两种分布式索引在Map-Reduce范式下的实现。

如图5(a)所示,Term-Split索引需要Map、Reduce两步操作。在Map过程中以文档 Id(Di)为Key,文档的SpotSigs特征(Si)集合为Value输入,输出的中间结果以Si为Key,Di为Value。在Reduce过程中,将相同Si的中间结果收集在一起,将对应的Di合并成列表。

如图5(b)所示,Doc-Split索引相对简单,只需一步Map即可。每个Map任务在整个文档集的一个子集上迭代,只对子集中的文档建立索引,不考虑其他子集中的文档。

4.3 基于索引的拷贝检测

第三步是基于索引的拷贝检测。针对 Term-Split索引和 Doc-Split索引将分别给出Map-Reduce范式下的实现。

图4 Tokenize文档

图5 建立分布式索引

Term-Split方法如图6所示,在Map操作中,接收以 Term(Si)为 Key,Posting List(D1,D2,…)为Value的输入,将Posting List中的文档Id(D1,D2,…)两两组合作为中间结果输出,其中文档Id对(Di_Dj)作为Key,Value为该pair出现的次数。在Reduce操作中,将相同的Di_Dj收集在一起,将出现的次数相加得到文档Di和文档Dj之间相同的Term数量,再根据公式(1)计算得到Di与Dj之间的相似度,如果相似度超过阈值,则将结果以Dj_Dj作为Key,相似度作为Value输出。

Doc-Split方法如图7所示,初始化Map任务时,将这次迭代所需的索引分块读入内存。Map操作以文档Id(Di)为key,以文档的SpotSigs特征(Si)集合为 Value,将输入的文档作为“Query”(Dq)在Index中查找拷贝。具体的做法是,根据文档中的 Term在索引分块中找到同样包含这个Term的其他文档(D1,D2,…)。然后统计这些文档与(Dq)共有的Term数,之后使用公式(1)计算相似度。最后,将相似度超过某个阈值的文档对(Dq_Di)作为Key,相似度作为Value输出。

图6 Term-Split方法

图7 Doc-Split方法

5 实验

实验使用了开源的 Map-Reduce框架 Hadoop①http：//hadoop.apache.org/。实验将使用由10个节点构成的集群。每个节点配置2个单核主频为2.8GHz的4核CPU和32GB的内存。本文将使用WT10G作为实验数据。WT10G包含约160万个文本文件,总大小约为10GB。本节中,将首先考察两种文本拷贝检测算法的精度,以确定算法的参数。然后在最优精度的参数下,对两种算法的性能进行比较。

5.1 精度

在文本拷贝检测算法中,相似度阈值(τ)对结果的精度有比较大的影响。此外,在通过索引进行相似度计算时,往往会设置IDF值限制条件,忽略掉IDF值过高或过低的Term,这也会对精度产生影响。本实验的主要目的是,在不同的IDF限制条件下,找出使得精度最好的τ。为此,本实验将在人工标注的Golden Set上进行。该文档集是从WT10G中随机抽取出来,经过人工标注得到的,包含1000篇文档。此外,试验中所采用的IDF值是在整个WT10G文档集上统计的结果。考虑到本文所述两种算法的实现在精度方面具有完全一致的特性。因此,在下面论述中对这两种算法不作区分。

如图8所示,当IDF值为0.0～1.0以及 0.1～0.95时,τ取 0.4可以使F1 Score达到最大,均为0.953。τ过小会导致Precision值的下降,τ过大会导致Recall值急剧下降。当IDF值为0.2～0.85时,因为更多的词在计算时被忽略,因此需要将τ设得略低一些,当τ取0.3时,F1 Score达到最大,为0.954。该实验结果与 Theobald等人报告的τ取0.44时,F1 Score为0.94的结果基本相符[8]。

图 8 算法精度 V.S.相似度阈值(τ)

5.2 效率

通过前面的实验已经得到在不同IDF值设定下使得精度最优的τ：IDF为[0.0,1.0]时,τ取0.4;IDF为[0.1,0.95]时,τ取 0.4;IDF为[0.3,0.85]时,τ取0.3。在本实验中,将在上述三种不同参数配置下,对Term-Split和Doc-Split拷贝检测方法进行比较。本实验使用WT10G的八分之一作为测试集合,约包含20万篇文档。

由表1可见,Doc-Split方法的效率要明显好于Term-Split的方法。这主要是因为在Term-Split索引中,每个节点只包含一部分词信息,只能计算文档对之间的“部分交集大小”,在最终汇总前不能确定两个文档是否相似。为此必须维护大量的计数器,产生大量的中间结果。

表1 Term-Split V.S.Doc-Split

5.3 可扩展性

在本实验中,将验证两种拷贝检测算法的可扩展性。首先,将考察数据集规模与运行时间的关系。以检验两种算法在数据集规模不断增加的情况下的适应性。然后,将考察集群中CPU数量与运行时速度的关系。以检验两种算法的加速性能。实验中IDF取[0.3,0.85],τ取0.3。

如图9(a)所示,当文档数量达到 80万时,Term-Split方法在本次实验的硬件条件下已经无法进行(因为128GB的硬盘被中间数据耗光,算法在运行了4个多小时后终止)。因为中间数据的数量太大,当数据集规模很大时,Term-Split方法只能通过Lin提出的近似方法[11]计算非精确解。而相比之下 Doc-Split方法则表现出良好的性能。使用Doc-Split方法对整个WT10G数据集进行实验的时间为5627.457秒。同时如图9(b)所示,在加速性方面Doc-Split方法也优于Term-Split方法。在CPU数量增加4倍的情况下,达到了2.56倍的速度提升。这是因为Map-Reduce范式下的程序,具有天然的可扩展性,可以通过增加节点数量提高处理能力。

图9 可扩展性实验

6 结论

本文对Term-Split和Doc-Split两种不同的分布式索引结构进行了比较,并分别给出了Map-Reduce范式下建立这两种索引的算法,以及基于这两种索引的拷贝检测算法。最后通过实验比较了上述两种算法的性能。

实验表明Doc-Split方法在进行拷贝检测任务时更有效,而Term-Split方法因为产生了大量中间结果使得效率大大降低。因此中间结果数量的多少,直接影响了采用两步并行(Map,Reduce)的Map-Reduce程序的运行效率。当中间结果数量过多时,对中间结果进行排序,分组以及分发的操作代价已经远远超出了两步并行的好处。因此不适合采用两步并行,应该改为一步并行。比如本文所述的Doc-Split方法,没有采用Reduce操作,而是每次将一部分索引分块复制到所有节点上。因为仅凭单个节点上的信息已经可以得到结果,就无需进行Reduce操作,也回避了中间结果的问题。

综合来看,Map-Reduce范式可以有效地解决算法并行化的问题。但因为不同算法的差异性,在实现并行化时,需要结合算法本身的特性进行考虑,才能最大限度的发挥Map-Reduce范式的好处。

[1]A.Z.Broder,S.C.Glassman,M.S.Manasse et al.Syntactic clustering of the web[J].Computer Networks,1997,29(8-13)：1157-1166.

[2]D.Fetterly,M.Manasse,and M.Najork.On the E-volution of Clusters of Near-DuplicateWeb Pages[C]//Proceedings of the 1st Latin American Web Congress.Washington,DC,USA：IEEE Computer Society,2003：37.

[3]J.Cho,N.Shivakumar,and H.Garcia-Molina.Finding replicated web collections[C]//ACM SIGMOD Record.New York,NY,USA：ACM,2000：355-366.

[4]T.C.Hoad and J.Zobel.Methods for identifying versioned and plagiarized documents[J].JASIST,2003,54(3)：203-215.

[5]E.Spertus,M.Sahami,and O.Buyukkokten.Evaluating similarity measures：a large-scale study in the orkut social network[C]//Proceedings of the 11th ACM SIGKDD.New York,NY,USA：ACM,2005：678-684.

[6]R.J.Bayardo,Y.Ma,and R.Srikant.Scaling up all pairs similarity search[C]//Proceedings of the 16th WWW.New York,NY,USA：ACM,2007：131-140.

[7]J.Dean and J.Ghemawat.Map-Reduce：Simplified Data Processing on Large Clusters[J].Communications of the ACM,2004,51(1)：107-113.

[8]M.Theobald,J.Siddharth,and A.Paepcke.Spotsigs：robust and efficient near duplicate detection in large web collections[C]//Proceeding of 31th SIGIR,New York,NY,USA ：ACM,2008：563-570.

[9]Pang-Ning Tan,Michael Steinbach,Vipin Kumar.Introduction to Data Mining[M].Addison-Wesley,2005.

[10]C D Manning,P Raghavan,H Schutze,An Introduction to Information Retriveval[M].Cambridge University Press,2008.

[11]J.Lin.Brute force and indexed approaches to pairwise document similarity comparisons with mapreduce[C]//Proceedings of 32th SIGIR,New York,NY,USA ：ACM,2009：155-162.