基于Simhash算法的作業(yè)查重系統(tǒng)設(shè)計(jì)

李 玲, 王法勝, 李紹民

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

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

針對(duì)課程形成性考核中的作業(yè)查重問題，本文設(shè)計(jì)了一種基于Simhash算法的作業(yè)查重系統(tǒng)。本系統(tǒng)融入了自然語言處理領(lǐng)域中的Simhash算法，并且聯(lián)合Bootstrap、jQuery、SSM框架等多種技術(shù)進(jìn)行設(shè)計(jì)開發(fā)。本文設(shè)計(jì)的系統(tǒng)，在加強(qiáng)課程質(zhì)量管理、鼓勵(lì)學(xué)生堅(jiān)持原創(chuàng)意識(shí)、提高學(xué)生的誠信意識(shí)、杜絕作業(yè)抄襲和拷貝等學(xué)術(shù)不端行為具有重要意義。

1 關(guān)鍵技術(shù)綜述

1.1 Simhash算法簡(jiǎn)介

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

1.2 文本相似度分析的相關(guān)研究

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

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

2 算法設(shè)計(jì)

2.1 分詞插件設(shè)計(jì)

分詞作為自然語言處理領(lǐng)域中的第一道工序，其效果的好壞直接影響了后續(xù)的相關(guān)工作和結(jié)果，因此要選取符合系統(tǒng)需求的分詞器。對(duì)于本作業(yè)查重系統(tǒng)來說，不同專業(yè)都存在大量的專業(yè)詞匯，選取的分詞器不僅自身要包含一個(gè)很大的詞匯庫，還要有能夠擴(kuò)展詞庫的接口。

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

圖1 IK分詞器流程圖

2.2 算法匹配

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

圖2 Simhash算法流程圖

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

(1)

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

3 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

3.1 系統(tǒng)的架構(gòu)

選擇一個(gè)合適的架構(gòu)對(duì)系統(tǒng)的高效開發(fā)至關(guān)重要。因此架構(gòu)設(shè)計(jì)是系統(tǒng)開發(fā)和實(shí)際應(yīng)用過程中的一個(gè)關(guān)鍵步驟，針對(duì)不同的系統(tǒng)功能和應(yīng)用需求，選擇合理的系統(tǒng)架構(gòu)。

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

圖3 系統(tǒng)整體架構(gòu)圖

3.2 系統(tǒng)模塊設(shè)計(jì)

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

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

作業(yè)查重模塊只面向教師和學(xué)生兩個(gè)用戶。教師可在系統(tǒng)中發(fā)布課程任務(wù)并且查看已發(fā)布的課程任務(wù)記錄，同時(shí)對(duì)學(xué)生提交的課程作業(yè)可進(jìn)行在線查重批閱。學(xué)生用戶可查看教師發(fā)布的課程任務(wù)，并且在規(guī)定時(shí)間內(nèi)根據(jù)教師發(fā)布的課程任務(wù)進(jìn)行作業(yè)在線編輯和提交，在教師批閱完之后可以查看自己的作業(yè)分?jǐn)?shù)。

圖4 系統(tǒng)模塊功能圖

3.3 數(shù)據(jù)庫的設(shè)計(jì)

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

圖5 系統(tǒng)E-R圖

3.4 系統(tǒng)的實(shí)現(xiàn)

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

4 結(jié) 語

針對(duì)學(xué)生和教師使用的教務(wù)及作業(yè)提交等系統(tǒng)中存在的問題，結(jié)合師生日常教學(xué)發(fā)展中的實(shí)際需求，設(shè)計(jì)并實(shí)現(xiàn)了符合實(shí)際情況的作業(yè)查重系統(tǒng)。設(shè)計(jì)系統(tǒng)時(shí)充分考慮了應(yīng)用功能性、安全性等多方面的需求，同時(shí)，系統(tǒng)中留有接口，方便日后的擴(kuò)展和維護(hù)。該系統(tǒng)的使用能夠大大降低教師批閱作業(yè)的時(shí)間和工作強(qiáng)度，同時(shí)能夠督促學(xué)生認(rèn)真完成作業(yè)，有效減少作業(yè)抄襲的現(xiàn)象，為營造良好的學(xué)習(xí)氛圍提供了有力保障。