基于Simhash算法的作業查重系統設計

李 玲, 王法勝, 李紹民

(大連民族大學 信息與通信工程學院，遼寧 大連 116605)

目前高校普遍存在課程作業抄襲的現象，由于部分學生缺乏誠信意識，貪圖抄襲帶來的便捷，使得教師布置的課程任務無法實現應有的考核效果，因此應該提出有效的方法來遏制這種現象[1]。作業查重是課程形成性考核中的減少抄襲現象的重要手段，能夠有效提高課程形成性考核的效果。目前，我國在學位論文查重方面制定了大量規范，通過中國知網平臺、萬方平臺等提供的查重功能，來檢測學位論文的重復率，但這類商業化平臺在查重時收取費用較高，難以用于數量和頻次較多的課程作業查重。目前，在課程形成性考核方面，很少有高校投入資金開發針對課程作業的查重系統，而一些商業化的系統，如北京航空航天大學開發的希冀平臺，帶有查重功能也僅限于程序設計類課程的代碼查重功能。2018年，清華大學推出的作業查重服務已在清華大學全校推廣使用[2]，有效減少了作業抄襲現象。

針對課程形成性考核中的作業查重問題，本文設計了一種基于Simhash算法的作業查重系統。本系統融入了自然語言處理領域中的Simhash算法，并且聯合Bootstrap、jQuery、SSM框架等多種技術進行設計開發。本文設計的系統，在加強課程質量管理、鼓勵學生堅持原創意識、提高學生的誠信意識、杜絕作業抄襲和拷貝等學術不端行為具有重要意義。

1 關鍵技術綜述

1.1 Simhash算法簡介

Simhash算法最早是由Google提出來用來網頁去重的算法，其主要思想是將高維的具有表征文本效果的指紋向量進行降維處理，從而在后續進行文本內容重復率比對時能夠大幅度提高其計算的效率[3]。Simhash算法的出現是建立在傳統的hash算法之上的，hash算法將原有的文本映射成一系列分散的簽名值，但是在后期與其他文本進行相似程度的比對時，如果兩篇文檔的簽名值不相等，只能說明它們不是完全相同的，并不能反映出來實際上存在的差異程度，因此后期提出了能夠反映出文本相似度的Simhash算法[4]。Simhash屬于一種局部敏感哈希算法(Locality-Sensitive Hashing，LSH)。其主要思路是將原始的文本內容先通過一些哈希映射轉換后劃分成能夠代表該內容的集合，這些集合被分配到哈希表的各個位置，在進行相似性比對時，將待查文本進行哈希映射的操作，得到其在哈希表中的位置，然后根據位置關系將數據進行逐一的線性比對，進而發現與待查數據相似性更高的數據，從而減少海量數據比對時的計算量[5,6]。此外，Simhash算法不僅應用在文本相似度計算方面，還在生物測序數據去重、多媒體數據檢索、惡意代碼檢測等領域有著廣泛的應用[7]。

1.2 文本相似度分析的相關研究

文本相似度分析是自然語言處理領域中的一個重要分支，是一項基礎性研究，文獻[8]對目前存在的各種文本相似度分析算法進行了較為全面的綜述性研究。作為最常見的可視的信息載體，文本是一種最為普遍的信息表現形式，因此文本相似度算法應用的范圍也十分的廣泛。

Orellana G等人[9]所提出的通過文本相似度計算對教學大綱中的內容進行語義比較的方法，能夠成功計算高等教學大綱間的相似性，方便解決學生因流動帶來的學分驗證問題。Soleymanzadeh K等人[10]提出一種釋義識別系統，該系統利用機器翻譯和通用文本相似性度量的組合作為特征，完成確定一個文本是否是另一文本的重述的分類任務。湯建明等人[11]以文本相似度分析算法為依托，開發了海量網絡文本去重系統，能夠給瀏覽網頁的用戶帶來更好的體驗。陳江華[12]將文本相似度分析算法應用于對科技項目申報書中文字的重復性檢測中，有效地減少了部分科研項目重復申報的問題，同時大大節省了申報書審核的成本，提高了審核的效率。Lemantara J等人[13]提出的在線考試的模型，能夠以百分比的形式顯示學生答案與正確答案間的相似度，幫助教師更快、更客觀地評價作文，同時可以顯示學生答案之間的相似度，從而防止抄襲行為的發生。李剛[14]結合網絡信息檢索系統與查重系統，對數據庫中的文本進行挖掘，同時借助遺傳算法的思想，實現了網絡環境下的中文查重系統。

2 算法設計

2.1 分詞插件設計

分詞作為自然語言處理領域中的第一道工序，其效果的好壞直接影響了后續的相關工作和結果，因此要選取符合系統需求的分詞器。對于本作業查重系統來說，不同專業都存在大量的專業詞匯，選取的分詞器不僅自身要包含一個很大的詞匯庫，還要有能夠擴展詞庫的接口。

本系統采用了最新的IKAnalyzer 2012版本，該版本相較于其他版本來說，具有標志化的分詞歧義排除算法，這種標志化的算法使得IKAnalyzer分詞器不再被認為是單純的中文詞典分詞器。IKAnalyzer2012分詞器同時支持細粒度和智能分詞兩種分詞處理模式，每秒能夠處理大約160萬字，處理效率極高，分詞器的處理系統同時支持英文字母、數字、中文等多種詞匯。目前該分詞器在主詞典上自帶有27萬字左右的基礎漢語單詞量，后期還可以進行多種途徑的自定義詞匯擴展[15]。該分詞器在分詞處理能力、分詞效果、后續詞典優化等方面都能夠滿足本系統功能開發的需求，其流程如圖1。

圖1 IK分詞器流程圖

2.2 算法匹配

分詞后的結果并不能被計算機所理解，因此要將結果轉化成計算機能夠理解的，可以表征待查重文本的特征向量，本系統選用的是Simhash算法，具體流程圖如圖2。

圖2 Simhash算法流程圖

首先定義一個規定長度的特征數組用來存儲后期hash計算產生的hash值，本系統規定的長度為64位。接下來讀取數據庫中學生提交待查重文本的分詞結果，然后對分詞結果進行處理，其中包括過濾標點符號、過濾超頻詞匯等，得出一組能夠表征文本的詞匯數組。接著對詞匯數組中的每個詞匯進行hash值計算，隨機生成64位長度的01數列。最后賦予每個詞匯相應的權重，對詞匯的hash值進行加權處理，然后對所有加權后詞匯的hash值進行合并和降維處理，得到本篇文檔的Simhash簽名。通過計算兩篇文檔對應的Simhash簽名的漢明距離可以得到其相似程度。漢明距離指的是兩個長度相同的字符串對應位置字符不同的數量，是一種簡單有效的計算并度量兩個向量之間的距離的方法，其計算公式如下所示[16]：

(1)

式中：⊕表示的是xi與yi進行異或操作，即對應位置兩數相同置為0，兩數不同置為1，漢明距離就是兩個等長的二進制碼字之間，位置相同但數值不同的碼字的數量，也就是異或操作后得到的1的數量。本系統中，規定漢明距離在0～2之間為嚴重抄襲行為，3～4之間為中等抄襲行為，5～6之間為輕微抄襲行為。

3 系統的設計與實現

3.1 系統的架構

選擇一個合適的架構對系統的高效開發至關重要。因此架構設計是系統開發和實際應用過程中的一個關鍵步驟，針對不同的系統功能和應用需求，選擇合理的系統架構。

本系統總體的設計架構是基于SSM框架進行搭建，前端頁面的設計采用了Bootstrap框架，使用最新的jQuery技術、HTML、JavaScript和CSS完成開發。同時采用了B/S模式、Maven工具等進行了系統的聯合開發。除此之外，系統中還嵌入了自然語言處理領域中的Simhash算法，以完成抄襲檢測模塊的功能開發。系統中數據存儲采用的是關系型數據庫MySQL，可以同時處理大量用戶需求，處理超過五千萬的相關記錄，命令響應的速度快，相較于其他的關系型應用數據庫，MySQL是一個完全開源且更加簡單快捷易用的關系型數據庫，本系統的整體架構如圖3。

圖3 系統整體架構圖

3.2 系統模塊設計

本系統主要包括用戶管理、課程管理和作業查重三個模塊，其模塊功能圖如圖4。用戶管理模塊中被細分為了登錄注銷和基本管理兩個子模塊，其中登錄注銷子模塊是面向系統所有的用戶，各個用戶首先在登錄界面中輸入注冊賬號和設置的密碼并選擇其對應的登錄角色，系統將根據用戶輸入的賬號和信息調用身份驗證程序進行登錄驗證，驗證的主要內容包括該用戶是否存儲在數據庫中，以及檢測輸入的密碼是否正確，最后是該用戶的角色是否對應正確，若以上驗證內容有一項存在錯誤則登錄失敗，并根據用戶系統登錄失敗的原因進行對應的錯誤提示，反之則直接進入到相關角色的系統主界面。在用戶基本管理子模塊中，管理員具有該模塊最大的權限，不僅具有和其他用戶一樣可對個人的基本信息進行查看修改的功能，還可對系統中所有的用戶進行查看、刪除、修改以及新建系統用戶并且賦予其相應的角色類型的操作。

課程管理模塊共包含四個子模塊，分別是新建課程、查看課程信息、刪除課程和修改課程基本信息。其中查看課程信息中可對課程基本信息、課程任務記錄和課程作業記錄進行查看。管理員擁有該功能模塊的全部操作權限，可在線新建課程，并且對現有的課程進行刪除、修改和查看相關課程信息。教師用戶可查看自己所教授課程信息，如有修改基本信息的需求可在線進行修改。學生用戶只擁有查看自己所修課程信息的權限。

作業查重模塊只面向教師和學生兩個用戶。教師可在系統中發布課程任務并且查看已發布的課程任務記錄，同時對學生提交的課程作業可進行在線查重批閱。學生用戶可查看教師發布的課程任務，并且在規定時間內根據教師發布的課程任務進行作業在線編輯和提交，在教師批閱完之后可以查看自己的作業分數。

圖4 系統模塊功能圖

3.3 數據庫的設計

在進行系統的數據庫設計時，要在保證系統數據準確的情況下，盡可能的做到實時的傳輸和存儲。系統界面顯示的相關數據要從系統的數據庫中取出，用戶可以通過界面操作直接修改、刪除數據庫中的對應數據，并且還可在線向數據庫里寫入數據。針對本系統的需求，設計了admin_tab、stu_tab、tc_tab、user_tab、mission_tab、class_task_tab等15個數據表，分為基礎數據表和業務表兩類。基礎數據表中包括了系統用戶信息表、課程信息表等，而課程任務記錄表、課程作業記錄表屬于業務表，系統的E-R圖如圖5。

圖5 系統E-R圖

3.4 系統的實現

在本系統的開發過程中，前端開發使用了Bootstrap和jQuery等技術，并且采用了B/S架構。前后端整合技術選取的是SSM開發框架，其中Spring MVC是基于MVC模式進行設計的用來完成Web前端開發的框架，它給架構的使用者提供了可自主制定的處理器映射器以及視圖解析器，相比于其他的Web MVC框架，使用起來更具有靈活性，Spring框架作為業務邏輯層提供原始的URL地址映射以及特定的自主制定的策略，MyBatis框架的連接方法不同于傳統的JDBC數據庫，它可以通過現有的插件生成DAO層代碼[17-19]。Tomcat作為后端Web服務器用來響應HTML頁面的訪問請求，為了保證能夠有序管理系統中的模塊和jar包，加入了Maven管理工具[20]。

4 結 語

針對學生和教師使用的教務及作業提交等系統中存在的問題，結合師生日常教學發展中的實際需求，設計并實現了符合實際情況的作業查重系統。設計系統時充分考慮了應用功能性、安全性等多方面的需求，同時，系統中留有接口，方便日后的擴展和維護。該系統的使用能夠大大降低教師批閱作業的時間和工作強度，同時能夠督促學生認真完成作業，有效減少作業抄襲的現象，為營造良好的學習氛圍提供了有力保障。