大數據環境下作業抄襲檢測研究

馮凌凌　劉海霞

摘 要： 作業是檢驗教學效果的一種重要手段，但是不可避免存在作業抄襲的現象。隨著網絡的進一步發展，學生作業的抄襲從簡單的同學間抄襲延伸到從網絡抄襲，如何從幾十億網頁中找到抄襲的源頭成了亟待解決的問題。文章結合MapReduce及Nutch提出在大數據環境下作業抄襲檢測的設計方案。

關鍵詞： MapReduce Nutch 抄襲檢測

1.背景

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

前期已經有不少專家針對抄襲檢測推出了不少系統及方案，但是前期的系統及方案主要解決在現有數據庫中查找抄襲情況[1][2][3]。目前網絡資源瞬息萬變，有很多從網絡抄襲的情況無法檢測出來。針對現狀，筆者結合MapReduce及Nutch提出了新的抄襲檢測方案。

2.相關概念

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

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

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

3.作業抄襲的模塊的分析與設計

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

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

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

3.1客觀題部分抄襲檢測

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

圖 客觀題抄襲檢測流程圖

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

步驟1：輸入學生作業的客觀題部分。

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

步驟2：對文檔進行預處理。

目前系統要求學生客觀題部分的標準輸入是題號答案（如1A，代表第1題的答案是A），但是學生輸入的時候可能會存在如下與標準不符的答案，對于這部分的輸入，系統先進行預處理：

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

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

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

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

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

處理辦法：刪除空格。

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

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

步驟4：答案有錯的學生作業。

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

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

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

for（ i =1；i

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

if （學生i的答案==學生j的答案） {

把學生i，j的信息放到文件中

刪除學生j的文檔

n=n-1

}

else

j++；

}

i++；

}

3.2主觀題部分的抄襲檢測

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

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

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

步驟1：Nutch crawler操作。

此處利用Nutch crawler從網絡上搜索我們指定網站或全網的相關網頁信息，并放入數據庫A中。

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

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

步驟3：學生作業上傳。

把所有學生作業中主觀題部分按學生作業1，2……n上傳到各個分布式系統中，以便與網絡上的信息進行相似度檢測。

步驟4：相似度檢測。

通用的文檔復制（抄襲）檢測系統如下圖所示[7]

輸入模塊：輸入待檢測文檔與數據庫中存儲已注冊的文檔。在本系統中待檢測的文檔就是學生上傳的作業，數據庫中存儲的已注冊文檔即為從網絡中獲取的文檔信息。

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

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

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

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

步驟5：合并。

輸出有抄襲嫌疑多個作業清單，部分同學的作業可能與網絡多個文檔相似度都高于老師設定的閥值，取相似度最高的紀錄，刪除該同學的其他記錄，以保證獲取最有可能抄襲的網絡信息。

3.2.2方案二：

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

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

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

步驟3：jobtracker在hadoop中監控分布式系統中每個節點運行情況，在本方案中是用來監控哪個作業與網絡資源的相似度已經超過了老師設定的閥值，并通知其他分布式設備節點無需再對此作業進行相似度匹配。

步驟4：jobtracker有兩個功能：（1）發現有作業與網絡資源的相似度已經超過了老師設定的閥值，上報給jobtracker；（2）接收jobtracker的廣播，即接收來自jobtracker關于哪份作業已經有抄襲嫌疑的通知，對此作業進行標記，該分布式節點后續不再進行相似度檢測。

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

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

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

3.2.3兩種方案比較

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

4.結語

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

參考文獻：

[1]秦新國，丁國勇.作業抄襲檢測系統的設計與實現[J].南京審計學院學報，2008-08-20.

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

[3]付兵，謝本貴.網絡環境與機房環境下電子作業反抄襲策略[J].實驗室研究與探索，2013.4.

[4]Linda DiGeronimo，Filomena Ferrucci，Alfonso Murolo，Federica 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]盧小康 .中文文本復制檢測技術研究[D].杭州杭州電子科技大學 ，2009.

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

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

教改基金項目（kyjg1416）。