大數(shù)據(jù)環(huán)境下作業(yè)抄襲檢測(cè)研究

馮凌凌　劉海霞

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

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

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é)效果，但是若靠老師的手工檢測(cè)，工作量太大，則現(xiàn)實(shí)中難以實(shí)現(xiàn)。

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

2.相關(guān)概念

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

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

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

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

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

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

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

3.1客觀題部分抄襲檢測(cè)

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

圖 客觀題抄襲檢測(cè)流程圖

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

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

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

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

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

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

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

（2）對(duì)于沒有答案的題目直接省略，如直接輸出1A3C，缺少題號(hào)2與第2題的答案

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

（3）題號(hào)或答案前后有空格

處理辦法：刪除空格。

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

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

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

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

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

在這個(gè)步驟中采用兩兩匹配的算法：

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主觀題部分的抄襲檢測(cè)

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

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

圖 主觀題相似性檢測(cè)方案一

步驟1：Nutch crawler操作。

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

步驟2：教師查詢請(qǐng)求操作。

此處用到了Nutch Searcher功能，教師根據(jù)作業(yè)中將會(huì)涉及的關(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，同時(shí)教師輸入認(rèn)定有抄襲嫌疑的閥值。

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

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

步驟4：相似度檢測(cè)。

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

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

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

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

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

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

步驟5：合并。

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

3.2.2方案二：

圖 主觀題相似性檢測(cè)方案二

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

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

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

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

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

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

步驟7：合并，簡(jiǎn)單把前面輸出的各個(gè)抄襲嫌疑，清單歸并，輸出給教師。

3.2.3兩種方案比較

表 主觀題抄襲檢測(cè)的方案比較

4.結(jié)語

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

參考文獻(xiàn)：

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

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

[3]付兵，謝本貴.網(wǎng)絡(luò)環(huán)境與機(jī)房環(huán)境下電子作業(yè)反抄襲策略[J].實(shí)驗(yàn)室研究與探索，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ù)制檢測(cè)技術(shù)研究[D].杭州杭州電子科技大學(xué) ，2009.

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

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

教改基金項(xiàng)目（kyjg1416）。