王素紅，寧慧，王明星，徐麗

哈爾濱工程大學 計算機科學與技術(shù)學院，黑龍江 哈爾濱 150001

?

基于Hadoop的抄襲檢測的源檢索方法研究

王素紅，寧慧，王明星，徐麗

哈爾濱工程大學 計算機科學與技術(shù)學院，黑龍江 哈爾濱 150001

摘要：隨著科學技術(shù)的發(fā)展和互聯(lián)網(wǎng)的普及，網(wǎng)絡給人們帶來便利的同時，也給抄襲剽竊提供了機會，現(xiàn)在抄襲檢測已經(jīng)成為一個重要的研究課題。本文分析了傳統(tǒng)抄襲檢測系統(tǒng)源檢索模塊的優(yōu)缺點，結(jié)合分布式系統(tǒng)的特點，提出基于索引分片的源檢索體系結(jié)構(gòu)，在大規(guī)模數(shù)據(jù)集上進行抄襲檢測研究，以便快速的檢測出可疑文檔的備選文集。通過實驗證明，基于索引分片的源檢索結(jié)構(gòu)能夠應對大規(guī)模數(shù)據(jù)集的處理要求，有效的提高了源檢索階段的時間性能，同時也保證了抄襲檢測系統(tǒng)的可靠性。

關鍵詞：抄襲；抄襲檢測；大規(guī)模數(shù)據(jù)集；源檢索；Hadoop 分布式源檢索模塊的主要功能是對大規(guī)模備選文檔數(shù)據(jù)集批量的構(gòu)建索引和接收查詢進行分布式檢索，最后返回候選文檔集。從功能上能看出，分布式源檢索模塊包括2個子模塊：索引更新模塊和檢索模塊，如圖1所示。 檢索模塊接收查詢，將查詢請求發(fā)送到索引庫中進行分布式查詢，檢索接口返回的是候選文檔集[11]。

寧慧(1964-)，女，副教授，碩士生導師.

隨著互聯(lián)網(wǎng)的發(fā)展，大量有價值的學術(shù)論文以及資料被發(fā)布在網(wǎng)絡上的同時，也為文本抄襲提供了便利。文本抄襲是指抄襲者將他人的作品沒有修改或者做出少量修改后使用而不做引用說明的行為。抄襲檢測是指人們利用計算機各方面的研究技術(shù)，檢測數(shù)字產(chǎn)品是否復制其他數(shù)字產(chǎn)品的過程。當前的抄襲檢測系統(tǒng)存在很多問題。大規(guī)模備選文檔數(shù)據(jù)集上的抄襲檢測系統(tǒng)研究尚不成熟。隨著抄襲檢測的備選文檔數(shù)據(jù)集的迅速增長，基于單機的抄襲檢測系統(tǒng)已經(jīng)無法滿足大規(guī)模數(shù)據(jù)集的存儲需求和計算力需求，如何使抄襲檢測系統(tǒng)能夠適應大規(guī)模數(shù)據(jù)集，從大規(guī)模數(shù)據(jù)集中獲取與可疑文本相似的抄襲片段，有待進一步研究。

針對以上問題，文中提出了基于Hadoop[1]的抄襲檢測方法，使得抄襲檢測系統(tǒng)在數(shù)據(jù)存儲和計算資源上能夠應對大規(guī)模的備選文檔數(shù)據(jù)集。

1相關技術(shù)介紹

1.1Hadoop簡介

Hadoop是Apache軟件基金會旗下的一個開源分布式計算平臺。以HDFS[2]和MapReduce[3]為核心的Hadoop為用戶提供了系統(tǒng)底層細節(jié)透明的分布式基礎架構(gòu)。HDFS的高容錯性、高伸縮性等優(yōu)點允許用戶將Hadoop部署在低廉的硬件上，形成分布式系統(tǒng)；MapReduce分布式編程模型允許用戶在不了解分布式系統(tǒng)底層細節(jié)的情況下開發(fā)并行應用程序。所以用戶可以利用Hadoop輕松地組織計算機資源，從而搭建自己的分布式計算平臺，并且可以充分利用集群的計算和存儲能力，完成海量數(shù)據(jù)的處理。

Apache Hadoop的流行與大數(shù)據(jù)處理的興起關系密切。眾所周知，現(xiàn)代社會的信息量增長速度極快，這些信息里又積累著大量的數(shù)據(jù)，其中包括個人數(shù)據(jù)和工業(yè)數(shù)據(jù)。預計到2020年，每年產(chǎn)生的數(shù)字信息將會有超過1/3的內(nèi)容駐留在云平臺中或借助云平臺處理。人們需要對這些數(shù)據(jù)進行分析和處理，以獲取更多有價值的信息。為了高效地存儲、管理和分析這些數(shù)據(jù)，可以選用Hadoop系統(tǒng)，它在處理這類問題時，采用了分布式存儲方式，提高了讀寫速度，并擴大了存儲容量。采用MapReduce來整合分布式文件系統(tǒng)上的數(shù)據(jù)，可保證分析和處理數(shù)據(jù)的高效。與此同時，Hadoop還采用存儲冗余數(shù)據(jù)的方式保證了數(shù)據(jù)的安全性。

1.2 實驗評測方法

該實驗所使用的評價函數(shù)是信息檢索領域常用評價函數(shù)，分別為精確率(precision)，召回率(recall)和F1值[4]。在抄襲檢測的源檢索階段主要使用這3個評測指標來進行評測。精確率是用來衡量檢索出來的數(shù)據(jù)的準確性，計算方法是正確的結(jié)果數(shù)與檢索返回的總數(shù)目的比值。召回率是用來衡量可以成功檢索到相關文本的可能性，計算方法是檢索到的正確的數(shù)據(jù)個數(shù)與標準答案所提供的總的相關個數(shù)的比值。F1值可以平衡地反映召回率與準確率。F1值的公式如式(1)所示：

(1)

式中：R是召回率：

(2)

其中：P 是精確率：

(3)

其中：TP是指系統(tǒng)檢索到的相關文檔；FP是指系統(tǒng)未檢索到的相關文檔數(shù)；FN是系統(tǒng)檢索到的不相關的文檔數(shù)；F1值是調(diào)和函數(shù)，用于平衡召回率和精確率的值，是系統(tǒng)的最終評價指標。

2源檢索模塊研究

2.1基于索引分片的源檢索研究

文中提出基于索引分片的源檢索模塊結(jié)構(gòu)。分布式檢索的基礎是分布式索引[5]，即邏輯索引被劃分成很多子索引，且這些子索引部署在不同的服務器上[6]，利用Hadoop可以實現(xiàn)分布式檢索模塊[7]。

該檢索模塊充分地利用了基于Hadoop的分布式集群所提供的存儲能力、計算能力，并且保證了源檢索模塊的高可靠性。

基于索引分片[8]的源檢索模塊結(jié)構(gòu)也把備選文檔數(shù)據(jù)集的邏輯索引劃分成多個子索引，每個子索引會有多個副本索引，所有的副本索引會被部署在Hadoop分布式集群的源檢索服務器上。在文中采用Apache Zookeeper集群協(xié)調(diào)和管理分布式集群。

圖1　基于索引分片的源檢索模塊

2.2索引更新模塊

索引更新模塊接收備選文檔數(shù)據(jù)集，批量構(gòu)建索引并部署到分布式集群中，將索引存儲在源檢索服務器上。集群中每個源檢索服務器可以包含多個處理單元，每個處理單元能獨立的提供索引更新或檢索功能[9]。索引更新模塊負責增量索引、文檔的刪除等。

源檢索模塊索引更新流程如下：

1)客戶端把需要索引更新的數(shù)據(jù)提交到服務器集群，集群中與邏輯索引相關的任一副本索引節(jié)點都有可能接收到更新請求。

2)如果該副本索引節(jié)點不是對應的子索引的主節(jié)點，它就會把更新請求轉(zhuǎn)發(fā)給和自己是同一子索引上的主節(jié)點。

3)主節(jié)點把備選文檔數(shù)據(jù)的更新請求轉(zhuǎn)發(fā)給同一子索引的所有其他副本索引節(jié)點，所有節(jié)點都要執(zhí)行更新請求。

4)如果備選文檔數(shù)據(jù)的更新請求基于轉(zhuǎn)發(fā)規(guī)則并不屬于當前子索引，主節(jié)點會把它轉(zhuǎn)交給相應的子索引的主節(jié)點。

5)對應的主節(jié)點會把備選文檔數(shù)據(jù)的更新請求轉(zhuǎn)發(fā)給該子索引的所有其他副本索引節(jié)點，所有的副本索引節(jié)點都需要執(zhí)行更新請求。

分布式源檢索模塊中的子索引主節(jié)點接收到備選文檔集數(shù)據(jù)的更新請求后，必須確定當前更新請求屬于邏輯索引的哪個子索引。在基于索引分片的源檢索模塊中，負責分布式更新邏輯處理中的是一個Hash算法[10]，由此來決定更新記錄具體分配到哪個子索引。算法代碼如下所示。

private int hash(AddUpdateCommandcmd) {

String hashableId = cmd.getHashableId();

return Hash.murmurhash3_x86_32(hashableId, 0, hashableId.length(), 0);

}

private int hash(DeleteUpdateCommandcmd) {

return Hash.murmurhash3_x86_32(cmd.getId(), 0, cmd.getId().length(), 0);

}

其中cmd.getHashableId()方法返回的是備選文檔集數(shù)據(jù)的主鍵的值，通過其hash值定位更新到哪個子索引。

2.3檢索模塊

源檢索模塊會把邏輯索引劃分成多個子索引，客戶端向源檢索服務器集群中包含這個邏輯索引的任意源檢索服務器發(fā)出檢索請求此請求會被處理成多個子查詢分發(fā)到邏輯索引的各個子索引節(jié)點上。多個子索引源檢索服務器的檢索結(jié)果返回給最初的服務器匯總后，將檢索結(jié)果返回給客戶端。

源檢索模塊的分布式檢索流程如下：

1)客戶端向分布式源檢索服務器集群發(fā)送檢索請求，含有該邏輯索引的任意源檢索服務器都有可能接收到該請求，源檢索服務器的內(nèi)部處理邏輯會把查詢請求轉(zhuǎn)發(fā)到一個其他的副本索引節(jié)點。

2)這個副本索引節(jié)點啟動源檢索分布式查詢，根據(jù)子索引的個數(shù)，將查詢轉(zhuǎn)化為多個子查詢并把每個子查詢定位到對應子索引的任意一個副本索引節(jié)點上。

3)接受檢索請求的副本索引節(jié)點返回各自的查詢結(jié)果。

4)最初的源檢索服務器節(jié)點合并這些子查詢，并把最終結(jié)果返回給客戶端。

在分布式源檢索模塊檢索時，多個查詢在分布式索引中并行地進行檢索，減少了串行檢索的時間。

3實驗設計與實驗結(jié)果分析

3.1實驗設計

PAN@CLEF2012國際評測訓練數(shù)據(jù)集涵蓋了較為常見的多類抄襲案件：no obfuscation、artificial low、artificial high、simulated paraphrase和translation 5大類。本實驗采用Pan2012的訓練數(shù)據(jù)集，參考文檔是4 210篇，可疑文檔是1 804篇。實驗的第一部分，針對每一種可疑文檔抄襲類型，隨機地選擇20篇可疑文檔，總共20×5篇可疑文檔，與4 210篇參考文檔一起，作為本章的實驗數(shù)據(jù)的一部分，驗證基于索引分片的源檢索模塊的性能。

實驗分為備選文檔集索引的創(chuàng)建、可疑文檔文本預處理、檢索相關文檔和性能評測4個步驟：

1)備選文檔集索引的創(chuàng)建

對于訓練數(shù)據(jù)集中的參考文檔集，按自然片段建立索引。當文檔集很大時，可以利用MapReduce計算框架批量構(gòu)建索引方法創(chuàng)建索引。

2)可疑文檔文本預處理

對可疑文檔進行預處理,包括停用詞的移除、大小寫字母轉(zhuǎn)化和詞干提取。

3)檢索相關文檔

在源檢索模塊的檢索階段，文中在不同結(jié)構(gòu)的源檢索模塊上進行測試。首先將索引部署在基于單機索引的源檢索模塊上，調(diào)整檢索的各項閾值，如提交查詢個數(shù)的閾值，使源檢索模塊的性能達到最優(yōu)。其次，擴展源檢索模塊的數(shù)據(jù)節(jié)點為4、5、6，將索引部署到基于索引分片的源檢索模塊上，調(diào)節(jié)數(shù)據(jù)參數(shù)使分布式源檢索模塊的性能達到基于單機的源檢索模塊的水平。返回各種情況下性能指標、時間開銷等。

4)性能評測

根據(jù)1.2節(jié)中提出的評測方法，對獲得的相關文檔進行評測。

本實驗基于Pan@CLEF2012的評測標準和指標，測試在Hadoop分布式平臺上，基于索引分片的源檢索模塊在訓練數(shù)據(jù)集上的性能表現(xiàn)。實驗還測試了基于索引分片的源檢索模塊結(jié)構(gòu)與基于單機的源檢索模塊結(jié)構(gòu)，在處理大規(guī)模備選文檔數(shù)據(jù)集上的時間效率對比。

3.2實驗結(jié)果與分析

實驗的第1部分，不同的源檢索模塊體系結(jié)構(gòu)得到實驗結(jié)果如表1所示，參加對比的源檢索模塊結(jié)構(gòu)分別是基于單機索引的源檢索模塊結(jié)構(gòu)和基于索引分片的源檢索模塊結(jié)構(gòu)，分布式環(huán)境下的數(shù)據(jù)節(jié)點分別擴展為4、5、6臺源檢測服務器。表1中展示了6種數(shù)據(jù)集下的源檢索結(jié)果，分別是數(shù)據(jù)集1(no obfuscation)、數(shù)據(jù)集2(artificial low)、數(shù)據(jù)集3(artificial high)、數(shù)據(jù)集4(simulated paraphrase)和數(shù)據(jù)集5(translation)，以及將所有數(shù)據(jù)合并后的總的數(shù)據(jù)集數(shù)據(jù)6(All Data)。表1中的F1值是指最終的系統(tǒng)對比指標，R指的是召回率，P指的是精確率。

表1　 不同源檢索模塊結(jié)構(gòu)檢索的實驗結(jié)果

由于表1所示的檢索結(jié)果中R和P的值太小，將其放大100倍。在實驗中，基于單機的源檢索模塊結(jié)構(gòu)的各個閾值經(jīng)過調(diào)節(jié)后，F(xiàn)1值在各個數(shù)據(jù)集可以達到最優(yōu)。由表1的實驗結(jié)果可知，基于索引分片的源檢索模塊的各項閾值經(jīng)過調(diào)節(jié)后，在不同規(guī)模集群的F1值性能也可以達到基于單機索引的源檢索模塊的水平。

由表1中的檢索結(jié)果可以看出，對于相同的數(shù)據(jù)集，基于索引分片的源檢索模塊結(jié)構(gòu)的F1值可以達到基于單機索引的源檢索模塊結(jié)構(gòu)的最優(yōu)性能；同一種源檢索結(jié)構(gòu)在不同的數(shù)據(jù)集，性能效果也是不一樣的。因此，在Pan@CLEF2012的訓練數(shù)據(jù)集上，基于索引分片的源檢索模塊可以達到基于單機索引的源檢索的最優(yōu)性能。該實驗主要考察了4種不同的源檢索結(jié)構(gòu)的模塊的性能指標，由實驗結(jié)果可知，基于索引分片的源檢索模塊可以達到基于單機索引的源檢索結(jié)構(gòu)模塊的最優(yōu)性能。實驗證明在基于Hadoop分布式平臺上，基于索引分片的源檢索體系結(jié)構(gòu)在性能上可以應用于抄襲檢測系統(tǒng)上。

在實驗的第2部分中，實驗數(shù)據(jù)使用ClueWeb09[12]的英文文檔作為備選文檔集。實驗中隨機選擇若干篇英文文檔組成5個不同規(guī)模的數(shù)據(jù)集，和實驗第一部分的All Data一起組成本實驗的6個數(shù)據(jù)集，測試在大規(guī)模備選文檔集上4個源檢索模塊的時間效率。實驗數(shù)據(jù)集信息如表2所示。

表2　 較大規(guī)模的備選文檔集數(shù)據(jù)

表2中數(shù)據(jù)1為第一部分實驗的All Data數(shù)據(jù)集。本實驗用第一部分在數(shù)據(jù)6上獲得的源檢索模塊參數(shù)模型來測試時間效率。首先需要將這些數(shù)據(jù)在基于單機的源檢索模塊和基于索引分片的源檢索模塊(分別擴展為4～6臺源檢索服務器)上創(chuàng)建備選文檔集數(shù)據(jù)的索引；其次在訓練數(shù)據(jù)集可疑文檔中隨機選取100篇作為查詢。測試結(jié)果如表3。

表3　 源檢索模塊時間測試結(jié)果

實驗證明了在Hadoop分布式平臺上，基于索引分片的源檢索模塊可以應對抄襲檢測系統(tǒng)中大規(guī)模數(shù)據(jù)集的問題。

4結(jié)束語

針對當前的抄襲檢測系統(tǒng)無法處理大規(guī)模備選文檔數(shù)據(jù)集的問題，本文提出了基于索引分片的源檢索結(jié)構(gòu)。實驗結(jié)果表明，基于索引分片的源檢索模塊在精確性、召回率、F1值等性能指標上可以達到基于單機的源檢索模塊的性能水平，在性能上滿足抄襲檢索系統(tǒng)的要求。隨著備選文檔數(shù)據(jù)集規(guī)模的增大，基于索引分片的源檢索模塊的時間開銷增長速度相對比較平穩(wěn)，這說明了基于索引分片的源檢索模塊通過擴展集群規(guī)模在處理大規(guī)模數(shù)據(jù)集時完全有效。

參考文獻:

[1]Hadoop.Apache Hadoop[EB/OL]. [2011-12-27]. http://hadoop.apache.org.

[2]BORTHAKUR D. The hadoop distributed file system: Architecture and design[Z]. Hadoop Project Website, 2007: 1-10.

[3]DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. In Proceedings of Operating Systems Design and Implementation (OSDI), San Francisco,USA,2004, 51(1):107-113.

[4]POTTHAST M, GOLLUB T, HAGEN M, et al. Overview of the 4th International Competition on Plagiarism Detection[C]//CLEF 2012 Conference and Labs of the Evaluation Forum. Rome, Italy, 2012: 1-9.

[5]XU Jinxi, CALLAN J. Effective retrieval with distributed collections[C]//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA, 1998: 112-120.

[6]ICHIKAWA Y, UEHARA M. Distributed search engine for an IaaS based cloud[C]// 2011 International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA). Washington D C, USA, 2011: 34-39.

[7]封俊. 基于Hadoop的分布式搜索引擎研究與實現(xiàn)[D]. 太原: 太原理工大學, 2010: 35-53.

[8]蘇宇. 基于Hadoop的分布式全文檢索及相關技術(shù)研究[D]. 合肥: 中國科學技術(shù)大學, 2014: 22-38.

[9]PARO A. ElasticSearch cookbook[M]. Bermingham: Packt Publishing Ltd, 2013: 5-25.

[10]吳煒, 蘇永紅, 李瑞軒, 等. 基于DHT的分布式索引技術(shù)研究與實現(xiàn)[J]. 計算機科學, 2010, 37(2): 65-70.

[11]吳雪琴, 舒曉苓. 基于云計算的大數(shù)據(jù)信息檢索技術(shù)研究[J]. 電腦知識與技術(shù), 2014, 10(10): 2388-2390.

[12] Lemur. ClueWeb[EB/OL]. [2009-2-24]. http://lemurproject.org.

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1191.U.20151206.1018.016.html

Research on the source retrieval method of

plagiarism detection based on Hadoop

WANG Suhong, NING Hui, WANG Mingxing, XU Li

Department of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China

Abstract：With the development of science and technology and the popularity of Internet, the network has brought us convenience, as well as the opportunity for plagiarism. Plagiarism detection has become an important research subject. By analyzing the advantages and disadvantages of source retrieval of the traditional plagiarism detection system, in combination with characteristics of the distributed system, this paper proposes a source retrieval system structure based on the index slice, so as to retrieve candidate documents from massive data sets. Experimental results show that, the source retrieval structure based on the index slice can deal with massive data set. It can effectively improve time performance of source retrieval, and also guarantee the reliability of the plagiarism detection system.

Keywords：plagiarism; plagiarism detection; massive data sets; source retrieval; Hadoop

通信作者：寧慧，E-mail：ninghui@hrbeu.edu.cn.

作者簡介：王素紅(1986-)，女，碩士研究生；

基金項目：國家自然科學基金資助項目(61201084).

收稿日期：2015-03-27.網(wǎng)絡出版日期：2015-12-06.

中圖分類號：TP311

文獻標志碼：A

文章編號：1009-671X(2015)06-067-05

doi:10.11991/yykj.201503030