馮凌凌　劉海霞

摘 要： 作業(yè)是檢驗教學(xué)效果的一種重要手段，但是不可避免存在作業(yè)抄襲的現(xiàn)象。隨著網(wǎng)絡(luò)的進(jìn)一步發(fā)展，學(xué)生作業(yè)的抄襲從簡單的同學(xué)間抄襲延伸到從網(wǎng)絡(luò)抄襲，如何從幾十億網(wǎng)頁中找到抄襲的源頭成了亟待解決的問題。文章結(jié)合MapReduce及Nutch提出在大數(shù)據(jù)環(huán)境下作業(yè)抄襲檢測的設(shè)計方案。

關(guān)鍵詞： MapReduce Nutch 抄襲檢測

1.背景

隨著校園網(wǎng)和Internet的不斷普及，師生的生活、學(xué)習(xí)、工作方式發(fā)生了巨大變化，學(xué)生作業(yè)的上傳不再是單一傳統(tǒng)的手工書寫批改模式，開始采用網(wǎng)絡(luò)上傳方式，網(wǎng)絡(luò)廣泛使用極大地方便了師生的教與學(xué)，但是作業(yè)直接在網(wǎng)絡(luò)上傳讓部分學(xué)生鉆了空子，直接拷貝同學(xué)的作業(yè)或是直接從網(wǎng)上拷貝。這種連答案里面寫的內(nèi)容都不清楚的行為嚴(yán)重影響了教學(xué)效果，但是若靠老師的手工檢測，工作量太大，則現(xiàn)實中難以實現(xiàn)。

前期已經(jīng)有不少專家針對抄襲檢測推出了不少系統(tǒng)及方案，但是前期的系統(tǒng)及方案主要解決在現(xiàn)有數(shù)據(jù)庫中查找抄襲情況[1][2][3]。目前網(wǎng)絡(luò)資源瞬息萬變，有很多從網(wǎng)絡(luò)抄襲的情況無法檢測出來。針對現(xiàn)狀，筆者結(jié)合MapReduce及Nutch提出了新的抄襲檢測方案。

2.相關(guān)概念

Mapreduce[4]：MapReduce是一種編程模型，用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算。它極大地方便了編程人員在不會分布式并行編程的情況下，將自己的程序運(yùn)行在分布式系統(tǒng)上。

Nutch：是一個網(wǎng)絡(luò)搜索引擎，是在Java平臺上開發(fā)的開源網(wǎng)絡(luò)爬蟲工具。該引擎主要分為兩個部分：爬蟲crawler和查詢searcher。Crawler主要用于從網(wǎng)絡(luò)上抓取網(wǎng)頁并為這些網(wǎng)頁建立索引。Searcher主要利用這些索引檢索用戶的查找關(guān)鍵詞來產(chǎn)生查找結(jié)果。

N-Gram模型[5]：是大詞匯連續(xù)語音識別中常用的一種語言模型，對中文而言，我們稱之為漢語語言模型（CLM，Chinese Language Model）。該模型基于這樣一種假設(shè)，第n個詞的出現(xiàn)只與前面N-1個詞相關(guān)，而與其他任何詞都不相關(guān)，整句的概率就是各個詞出現(xiàn)概率的乘積。這些概率可以通過直接從語料中統(tǒng)計N個詞同時出現(xiàn)的次數(shù)得到。

3.作業(yè)抄襲的模塊的分析與設(shè)計

根據(jù)題目的種類（主觀題、客觀題），我們采用兩種不同的檢測機(jī)制，教師可以根據(jù)需要針對主觀題或是客觀題進(jìn)行抄襲檢測。

客觀題：本地檢測，抄襲判斷條件：錯誤題目的答案都一致。

主觀題：網(wǎng)絡(luò)檢測，抄襲判斷條件：滿足Z.B.Andrei定義的文檔相似性度量公式[6]。

3.1客觀題部分抄襲檢測

客觀題包括單選題、多選題、判斷題，對于此部分作業(yè)，若同學(xué)間錯誤的答案完全一致，我們就認(rèn)為此同學(xué)間存在抄襲嫌疑。判斷流程如下圖所示：

圖 客觀題抄襲檢測流程圖

各部分操作步驟如下（下面各步驟序號與上圖中的序號保持一致）：

步驟1：輸入學(xué)生作業(yè)的客觀題部分。

學(xué)生作業(yè)上傳可能包含主觀題與客觀題，在此部分只截取學(xué)生作業(yè)的客觀題部分。

步驟2：對文檔進(jìn)行預(yù)處理。

目前系統(tǒng)要求學(xué)生客觀題部分的標(biāo)準(zhǔn)輸入是題號答案（如1A，代表第1題的答案是A），但是學(xué)生輸入的時候可能會存在如下與標(biāo)準(zhǔn)不符的答案，對于這部分的輸入，系統(tǒng)先進(jìn)行預(yù)處理：

（1）學(xué)生直接輸出的答案，沒有題號，答案之間用空格相隔。

處理辦法：從左到右掃描，在空格處補(bǔ)上題號。

（2）對于沒有答案的題目直接省略，如直接輸出1A3C，缺少題號2與第2題的答案

處理辦法：在1A的答案后面補(bǔ)充2 （空格）。

（3）題號或答案前后有空格

處理辦法：刪除空格。

步驟3：與老師答案匹配。

按照整篇文本的粒度對文本進(jìn)行分塊，字符逐個匹配。

步驟4：答案有錯的學(xué)生作業(yè)。

與老師的答案出現(xiàn)不一致，說明學(xué)生作業(yè)中的部分答案是錯誤的，以學(xué)生的作業(yè)作為一個輸出單位，每個輸出文檔中包含學(xué)生所有的客觀題部分的答案，包括正確的與錯誤的。

步驟5：是否存在完全一致的作業(yè)比較。

在這個步驟中采用兩兩匹配的算法：

for（ i =1；i

for （j=i+1；j<=n；j++） {

if （學(xué)生i的答案==學(xué)生j的答案） {

把學(xué)生i，j的信息放到文件中

刪除學(xué)生j的文檔

n=n-1

}

else

j++；

}

i++；

}

3.2主觀題部分的抄襲檢測

目前因特網(wǎng)規(guī)模飛速膨脹，每天都會產(chǎn)生大量的新網(wǎng)頁，且有大量網(wǎng)頁失效，如何獲取有效信息至關(guān)重要，Nutch讓這個想法成了可能。在這輪檢測中我們先利用Nutch crawler幫助獲取有用的網(wǎng)絡(luò)信息，然后利用Nutch Searcher通過關(guān)鍵字查詢獲取教師所需的文本放入對應(yīng)的數(shù)據(jù)庫中。整個主觀題檢測的運(yùn)行流程有兩個方案，具體如下描述：

3.2.1方案一：在主觀題相似性檢測方案一中，各部分操作步驟如下（下面各步驟序號與上圖中的序號保持一致）：

圖 主觀題相似性檢測方案一

步驟1：Nutch crawler操作。

此處利用Nutch crawler從網(wǎng)絡(luò)上搜索我們指定網(wǎng)站或全網(wǎng)的相關(guān)網(wǎng)頁信息，并放入數(shù)據(jù)庫A中。

步驟2：教師查詢請求操作。

此處用到了Nutch Searcher功能，教師根據(jù)作業(yè)中將會涉及的關(guān)鍵字從數(shù)據(jù)庫A中獲取相關(guān)網(wǎng)頁鏈接，并截取網(wǎng)頁中的文本信息放入分布式數(shù)據(jù)庫中，即查詢結(jié)果數(shù)據(jù)庫Part1，查詢結(jié)果數(shù)據(jù)庫Part2……查詢結(jié)果數(shù)據(jù)庫Part n，同時教師輸入認(rèn)定有抄襲嫌疑的閥值。

步驟3：學(xué)生作業(yè)上傳。

把所有學(xué)生作業(yè)中主觀題部分按學(xué)生作業(yè)1，2……n上傳到各個分布式系統(tǒng)中，以便與網(wǎng)絡(luò)上的信息進(jìn)行相似度檢測。

步驟4：相似度檢測。

通用的文檔復(fù)制（抄襲）檢測系統(tǒng)如下圖所示[7]

輸入模塊：輸入待檢測文檔與數(shù)據(jù)庫中存儲已注冊的文檔。在本系統(tǒng)中待檢測的文檔就是學(xué)生上傳的作業(yè)，數(shù)據(jù)庫中存儲的已注冊文檔即為從網(wǎng)絡(luò)中獲取的文檔信息。

比較模塊：基于N-Gram模型[8][9]，結(jié)合Z.B.Andrei給出的文檔相似性度量公式計算文檔的相似度。

Z.B.Andrei定義的文檔相似性的度量公式，如下所示：

公式中：A為待檢測文檔，B為數(shù)據(jù)庫中已有文檔；S（A，w）和S（B，w）分別表示文檔A、B中大小為w的所有子序列的集合。

兩個文檔A，B的相似性是在0到1中的某個數(shù)字，兩篇文檔的相似性越高，說明這兩篇文檔雷同的成分越多。反之，則說明兩篇文檔的雷同成分越少。假設(shè)系統(tǒng)規(guī)定的閥值為。如果SimW（A，B）≥閥值，那么就認(rèn)為查詢文檔A抄襲了已注冊文檔B的內(nèi)容。

步驟5：合并。

輸出有抄襲嫌疑多個作業(yè)清單，部分同學(xué)的作業(yè)可能與網(wǎng)絡(luò)多個文檔相似度都高于老師設(shè)定的閥值，取相似度最高的紀(jì)錄，刪除該同學(xué)的其他記錄，以保證獲取最有可能抄襲的網(wǎng)絡(luò)信息。

3.2.2方案二：

圖 主觀題相似性檢測方案二

步驟1：同方案一中的步驟1。

步驟2：同方案一中的步驟2。

步驟3：jobtracker在hadoop中監(jiān)控分布式系統(tǒng)中每個節(jié)點運(yùn)行情況，在本方案中是用來監(jiān)控哪個作業(yè)與網(wǎng)絡(luò)資源的相似度已經(jīng)超過了老師設(shè)定的閥值，并通知其他分布式設(shè)備節(jié)點無需再對此作業(yè)進(jìn)行相似度匹配。

步驟4：jobtracker有兩個功能：（1）發(fā)現(xiàn)有作業(yè)與網(wǎng)絡(luò)資源的相似度已經(jīng)超過了老師設(shè)定的閥值，上報給jobtracker；（2）接收jobtracker的廣播，即接收來自jobtracker關(guān)于哪份作業(yè)已經(jīng)有抄襲嫌疑的通知，對此作業(yè)進(jìn)行標(biāo)記，該分布式節(jié)點后續(xù)不再進(jìn)行相似度檢測。

步驟5：學(xué)生作業(yè)主觀部分上傳：學(xué)生的作業(yè)按序錯開上傳到各個分布式設(shè)備中，如學(xué)生作業(yè)1，2……n上傳到分布式設(shè)備1中，學(xué)生作業(yè)10，11……n，1，2……9上傳到分布式設(shè)備2中，以此類推。用錯開方式上傳的目的是當(dāng)該學(xué)生與網(wǎng)絡(luò)中文檔相似度檢測時達(dá)到老師設(shè)定的閥值，jobtracker可以在該作業(yè)還沒有被其他設(shè)備檢測前及時通知到這些分布式設(shè)備，以便提高檢測效率；

步驟6：同方案一中的步驟4。

步驟7：合并，簡單把前面輸出的各個抄襲嫌疑，清單歸并，輸出給教師。

3.2.3兩種方案比較

表 主觀題抄襲檢測的方案比較

4.結(jié)語

抄襲檢測研究雖然已經(jīng)有多年歷史，但是結(jié)合大數(shù)據(jù)的抄襲研究還是一個較新的研究領(lǐng)域。本文探討了基于mapreduce與Nutch的抄襲檢測方案，給出了相應(yīng)的實現(xiàn)方案，采用了此方案可以讓數(shù)據(jù)庫中存儲的已注冊文檔為網(wǎng)絡(luò)中的最新文檔，以適應(yīng)網(wǎng)絡(luò)資源的快速發(fā)展。同時本方案中采用的mapreduce思想可以使用戶更方便，快捷地使用大規(guī)模數(shù)據(jù)集并行運(yùn)算，以減輕服務(wù)器的負(fù)擔(dān)。

參考文獻(xiàn)：

[1]秦新國，丁國勇.作業(yè)抄襲檢測系統(tǒng)的設(shè)計與實現(xiàn)[J].南京審計學(xué)院學(xué)報，2008-08-20.

[2]鄧愛萍，徐國梁.基于串匹配方法的源代碼復(fù)制檢測技術(shù)研究[J].科學(xué)技術(shù)與工程，2006.12.

[3]付兵，謝本貴.網(wǎng)絡(luò)環(huán)境與機(jī)房環(huán)境下電子作業(yè)反抄襲策略[J].實驗室研究與探索，2013.4.

[4]Linda DiGeronimo，F(xiàn)ilomena Ferrucci，Alfonso Murolo，F(xiàn)ederica Sarro."A Parallel Genetic Algorithm Based on Hadoop MapReduce for the Automatic Ge neration of JUnit Test Suites.”IEEE，2011.

[5]百度百科.

[6]Z.B.Andrei.On the Resemblance and Containment of Documents Compression and Complexity of SEQUENCES 1997，Salerno Intaly，1997：21-29.

[7]盧小康 .中文文本復(fù)制檢測技術(shù)研究[D].杭州杭州電子科技大學(xué) ，2009.

[8]吳斐 .基于N-gram的程序代碼抄襲檢測方法研究[D].重慶 西南大學(xué)，2012.

[9]王小華 ，盧小康 .基于N-Gram的文本去重方法研究[J].杭州電子科技大學(xué)學(xué)報 ，2010.

教改基金項目（kyjg1416）。