秦國(guó)鋒 王睿晗 任成琨 郝泳濤 王力生

10.3969/j.issn.1671-489X.2022.03.032

摘 要 為解決學(xué)生遞交的計(jì)算機(jī)課程代碼管理和審核問(wèn)題，構(gòu)建本地哈希指紋算法和Spring Cloud框架的查重比對(duì)模型，開(kāi)發(fā)計(jì)算機(jī)專業(yè)課程教學(xué)評(píng)價(jià)系統(tǒng)，其中包含按照課程和小節(jié)分類的文件管理和代碼重復(fù)率計(jì)算。哈希指紋算法是通過(guò)哈希函數(shù)和滑動(dòng)窗口計(jì)算出文件一系列的哈希值，通過(guò)比較哈希值來(lái)計(jì)算出文件之間的重復(fù)率，從而為教師對(duì)學(xué)生代碼的評(píng)價(jià)提供參考。

關(guān)鍵詞 在線課程管理；查重比對(duì)算法；網(wǎng)絡(luò)教學(xué)平臺(tái)；k-gram算法

中圖分類號(hào)：G434 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1671-489X（2022）03-0032-04

0 引言

在當(dāng)今信息化建設(shè)中，各大高校都開(kāi)始采用信息化的管理和教學(xué)手段，這種方式具有便捷、快速、準(zhǔn)確等優(yōu)點(diǎn)，為教師和學(xué)生提供了很大的便利[1]。但是，以往的教學(xué)平臺(tái)往往只提供信息的傳輸、查看和下載等功能，比如教師在網(wǎng)站發(fā)布作業(yè)和視頻，而后學(xué)生查看視頻和作業(yè)，完成電子版的作業(yè)后將作業(yè)提交，最后教師評(píng)閱作業(yè)。這個(gè)過(guò)程僅僅是方便了信息傳輸，卻不能為教師評(píng)閱提供助力。由于代碼容易復(fù)制，使得在實(shí)際的教學(xué)工作中抄襲、“借鑒”等行為層出不窮，因此迫切需要快速準(zhǔn)確的代碼查重方法來(lái)幫助教師識(shí)別可能抄襲的代碼，培養(yǎng)學(xué)生正確的學(xué)習(xí)觀念，提升整體教學(xué)質(zhì)量。

本文基于知識(shí)管理的理念，采用三層B/S架構(gòu)，即數(shù)據(jù)訪問(wèn)層、業(yè)務(wù)邏輯層和表示層，提出并實(shí)現(xiàn)一種基于計(jì)算機(jī)專業(yè)課程計(jì)算機(jī)體系結(jié)構(gòu)的網(wǎng)絡(luò)教學(xué)平臺(tái)[2-3]，除提供常規(guī)的課程添加、課程小節(jié)添加、作業(yè)發(fā)布、學(xué)生作業(yè)上傳、教師下載查看等基本功能外，還提供Verilog代碼的在線編譯和查重功能，能夠?yàn)榻處熢u(píng)閱代碼提供有效的幫助。

1 在線課程管理與本地代碼查重的需求

分析

需求分析對(duì)于教學(xué)平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)來(lái)說(shuō)至關(guān)重要，通過(guò)需求分析要明確系統(tǒng)功能的各項(xiàng)需求，再根據(jù)這些需求來(lái)對(duì)下一步的系統(tǒng)設(shè)計(jì)和開(kāi)發(fā)進(jìn)行指導(dǎo)。

1.1 課程管理系統(tǒng)的需求分析

整個(gè)系統(tǒng)需要分成三個(gè)權(quán)限角色：管理員、教師和學(xué)生。課程需要是可擴(kuò)展的，管理員可以在需要時(shí)添加新的課程、添加教師。教師可以對(duì)課程添加小節(jié)和作業(yè)信息，上傳作業(yè)要求，查看選課學(xué)生信息，查看特定課程特定小節(jié)的查重結(jié)果。學(xué)生可以自主選課，查看作業(yè)信息，上傳作業(yè)壓縮包，服務(wù)器需要存儲(chǔ)學(xué)生文件、教師文件。對(duì)于不同的登錄用戶，系統(tǒng)會(huì)根據(jù)權(quán)限的不同進(jìn)入對(duì)應(yīng)的頁(yè)面，這樣不僅方便學(xué)生、教師和管理員操作，提高工作效率，也會(huì)使各自的數(shù)據(jù)信息更加安全。

1.2 本地代碼查重的需求分析

代碼查重是本系統(tǒng)最核心的功能?；谥R(shí)管理的理念，系統(tǒng)應(yīng)當(dāng)存儲(chǔ)學(xué)生的代碼文件，當(dāng)教師需要某門(mén)課程某個(gè)小結(jié)的代碼查重結(jié)果時(shí)，系統(tǒng)應(yīng)在后臺(tái)進(jìn)行計(jì)算，然后將結(jié)果返回給教師。代碼查重算法需要有以下四種關(guān)鍵性能。

1）代碼中的空格，代碼的大小寫(xiě)、標(biāo)點(diǎn)符號(hào)、注釋是需要忽略的，所以需要對(duì)代碼進(jìn)行預(yù)處理，將其中不需要檢測(cè)的內(nèi)容刪除或者替換掉。

2）較小的字段重復(fù)是需要被忽略掉的。比如關(guān)鍵字for在不同代碼文件中往往都會(huì)出現(xiàn)，而這往往不應(yīng)算作重復(fù)的地方。因此，重復(fù)的字段應(yīng)該足夠大，以至于這段代碼很可能是復(fù)制的，而不是簡(jiǎn)單的特定語(yǔ)言的重復(fù)單詞。

3）位置信息不應(yīng)該影響查重結(jié)果。例如：將代碼文件中兩個(gè)函數(shù)的位置進(jìn)行替換，不應(yīng)當(dāng)影響查重結(jié)果；在代碼中新添加一段代碼，不應(yīng)當(dāng)影響原來(lái)的重復(fù)代碼的重復(fù)檢測(cè)。

4）檢測(cè)時(shí)間盡可能短。大文件匹配本身就是一個(gè)非常消耗時(shí)間的算法，所以需要良好的系統(tǒng)設(shè)計(jì)和算法設(shè)計(jì)來(lái)加快處理速度。

對(duì)于第一點(diǎn)，首先需要將一個(gè)學(xué)生這次的作業(yè)代碼文件全部拼接為一個(gè)文件，在拼接過(guò)程中將空格、標(biāo)點(diǎn)符號(hào)、注釋刪除，同時(shí)將全部字母轉(zhuǎn)換為小寫(xiě)字母，并且將非關(guān)鍵字的變量或函數(shù)命名全部替換為“X”關(guān)鍵字[6]。第二點(diǎn)和第三點(diǎn)需要運(yùn)用提出的Verilog本地哈希算法來(lái)解決，第四點(diǎn)則會(huì)在之后的架構(gòu)設(shè)計(jì)中解決。

2 在線課程管理平臺(tái)的開(kāi)發(fā)與設(shè)計(jì)

2.1 總體設(shè)計(jì)

按照功能需求進(jìn)行分解，可以在結(jié)構(gòu)上將課程網(wǎng)站分為前臺(tái)模塊和后臺(tái)模塊。前臺(tái)模塊主要是學(xué)生和教師使用，學(xué)生在登錄成功后瀏覽相關(guān)課程，選課，查看課程小節(jié)信息和作業(yè)，上傳作業(yè)等；而教師登錄成功后則可以查看自己的課程，發(fā)布課程的小節(jié)，上傳作業(yè)，下載作業(yè)，以及進(jìn)行作業(yè)查重。后臺(tái)模塊為管理員使用，管理具體的課程、教師和學(xué)生信息。系統(tǒng)架構(gòu)見(jiàn)圖1。

2.2 系統(tǒng)框架設(shè)計(jì)

2.2.1 用戶登錄 登錄模塊主要實(shí)現(xiàn)用戶根據(jù)不同權(quán)限進(jìn)行系統(tǒng)登錄的驗(yàn)證，教師、學(xué)生和管理員可以根據(jù)不同權(quán)限進(jìn)入相應(yīng)頁(yè)面。在登錄頁(yè)面，可以選擇學(xué)生、教師和管理員三個(gè)權(quán)限，輸入用戶名和密碼后會(huì)在數(shù)據(jù)庫(kù)中進(jìn)行比對(duì)，如果密碼錯(cuò)誤會(huì)直接返回登錄界面，而連續(xù)登錄失敗三次會(huì)提示暫時(shí)無(wú)法登錄，然后在當(dāng)前頁(yè)面等待一分鐘，防止數(shù)據(jù)庫(kù)壓力過(guò)大。

1）學(xué)生用戶。學(xué)生登錄后可以查看課程列表，點(diǎn)擊選課即可加入該課程。點(diǎn)擊我的課程可以查看已選課程列表，進(jìn)入具體課程可以查看該課程的小節(jié)，下載教師發(fā)布的該課程小節(jié)的文檔信息，上傳這個(gè)小節(jié)的作業(yè)。

2）教師用戶。教師登錄后可以查看自己的課程，查看學(xué)生列表，發(fā)布課程下的小節(jié)，上傳作業(yè)文件，下載學(xué)生作業(yè)，進(jìn)行作業(yè)查重，下載查重文件并查看結(jié)果。

3）管理員。管理員在登錄后可以查看所有課程和教師，并且可以增刪課程，為課程指定教師，修改教師信息和學(xué)生信息等。

2.2.2 查重模塊的設(shè)計(jì) 在實(shí)際的工作學(xué)習(xí)中，電子內(nèi)容很容易復(fù)制，比如從網(wǎng)頁(yè)中復(fù)制內(nèi)容，學(xué)生借鑒其他人的作業(yè)等。因此，迫切需要對(duì)于不同文件中重復(fù)內(nèi)容進(jìn)行檢測(cè)。對(duì)比整個(gè)文件是否相同，相比于對(duì)比文件中的部分內(nèi)容更簡(jiǎn)單[4]。文件指紋算法可以用來(lái)準(zhǔn)確檢測(cè)復(fù)制，包括文件中的部分復(fù)制。算法是在k-gram算法的基礎(chǔ)上對(duì)Verilog語(yǔ)言的適配和改進(jìn)，以希望準(zhǔn)確檢測(cè)不同Verilog代碼文件中的重復(fù)部分[5]。

k-gram算法將一個(gè)處理好的文件內(nèi)容（處理是指刪除掉不相關(guān)的內(nèi)容，比如空格、標(biāo)點(diǎn)符號(hào)和注釋等）分割為長(zhǎng)度為k的子串。如abcdefghi，假設(shè)k為4（這個(gè)值是由用戶指定的，主要根據(jù)具體要比較的文本特點(diǎn)來(lái)確定），這個(gè)字符串在k-gram

算法中將被分為這樣的子串：abcd bcde cdef defg

efgh fghi。而后計(jì)算每一個(gè)子串的哈希值：45 22

20 36 21 52。由于所有的哈希值很多，如果全部存儲(chǔ)并且計(jì)算會(huì)給服務(wù)器帶來(lái)很大負(fù)擔(dān)，而且并不需要所有的哈希值，因此可以選擇所有模p為0的哈希值作為整個(gè)文件的指紋。在例子中p=4，指紋還包含位置信息，用來(lái)描述這個(gè)哈希值所代表的字符串在文件中的位置：20 36 52。

在獲取每個(gè)文件的指紋后，可以通過(guò)對(duì)比任意兩個(gè)文件之間指紋的相似度來(lái)計(jì)算出整個(gè)文件的近似相似度。但是這種方法存在問(wèn)題，如果兩個(gè)滿足0 mod p的哈希值相隔太遠(yuǎn)，那么即使兩個(gè)哈希值相同，也不會(huì)被檢測(cè)到。因此，在k-gram算法的基礎(chǔ)上針對(duì)Verilog語(yǔ)言進(jìn)行一定的改進(jìn)和適配，同時(shí)改善距離過(guò)大導(dǎo)致的無(wú)法檢測(cè)的問(wèn)題。

查重的目標(biāo)是將同一課程同一小節(jié)內(nèi)的所有作業(yè)都兩兩比對(duì)。要求所有學(xué)生上傳的作業(yè)都使用壓縮包的形式，上傳成功后進(jìn)行解壓，然后將所有.v文件拼接在一起，在拼接的過(guò)程中刪除所有空格、注釋和Verilog特有的不重要的關(guān)鍵字，比如endmodule等。拼接完成后，需要計(jì)算哈希值。設(shè)定每八個(gè)字符計(jì)算一個(gè)哈希值，每五個(gè)哈希值中選取最末尾的一個(gè)寫(xiě)入文件中。這些過(guò)程全部是在學(xué)生上傳作業(yè)后在系統(tǒng)后臺(tái)另開(kāi)啟新的線程實(shí)現(xiàn)的，目的是提前進(jìn)行預(yù)處理，節(jié)約時(shí)間。

預(yù)處理算法細(xì)節(jié)如下：

void cal （int w）{

int[] h=new int[n];

for（int i=0;i

VALUE;

int r=0;

int min=0;

while（true）{

r=（r+1）%w;

h[r]=hash（）;

if（min==r）{

for（int i=（r-1）%w;i！=r;i=（i-1+w）%w）{

if（h[i]

}

record（h[min]，global_pos（min，r，w））;

}else{

if（h[r]<=h[min]）{

min=r;

record（h[min]，global_pos（min，

r，w））

}

}

}

}

當(dāng)教師向用戶發(fā)送請(qǐng)求獲取某小節(jié)的查重結(jié)果時(shí)，后臺(tái)兩兩計(jì)算兩個(gè)學(xué)生作業(yè)的哈希值相似度，這里選用的是Jaccard相似性系數(shù)。而后將相似系數(shù)寫(xiě)入查重文件中，并寫(xiě)入數(shù)據(jù)庫(kù)，返回給教師。

Jaccard可以用來(lái)衡量?jī)蓚€(gè)集合之間的區(qū)分度?，F(xiàn)有兩個(gè)集合A、B。Jaccad系數(shù)：

J（A，B）=|A∩B|/|A∪B|

可以很容易看出Jaccard系數(shù)越大，A、B集合的相似度越高。具體的Jaccard系數(shù)計(jì)算代碼實(shí)現(xiàn)：

public double jaccard（Set A， Set B） {

int count = 0;

for （int i ： A） {

for （int j ： B） {

if （i == j） {

count++;

}

}

}

return count / （A.size（） + B.size（） - count）;

}

2.2.3 數(shù)據(jù)庫(kù)設(shè)計(jì) 數(shù)據(jù)庫(kù)在系統(tǒng)中用于存儲(chǔ)信息，數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)確定了各個(gè)實(shí)體之間的邏輯實(shí)現(xiàn)，而實(shí)體和屬性之間的關(guān)系需要用實(shí)體—聯(lián)系圖表現(xiàn)，見(jiàn)圖2。本系統(tǒng)具有以下四個(gè)實(shí)體。

1）管理員實(shí)體，包含管理員id、管理員姓名、管理員密碼。

2）教師實(shí)體，包含教師id、教師姓名、教師密碼。

3）學(xué)生實(shí)體，包含學(xué)生id、學(xué)生姓名、學(xué)生密碼。

4）文件實(shí)體，包含編號(hào)、文件在硬盤(pán)中的url、文件所屬的學(xué)生id、文件所屬的課程id、文件所屬的教師id、文件類型、成績(jī)、課程小節(jié)、創(chuàng)建時(shí)間、文件名。將教師課程文件、學(xué)生作業(yè)文件和查重文件統(tǒng)一放在這個(gè)表內(nèi)，通過(guò)文件類型標(biāo)識(shí)不同的文件類型，管理更為方便。

3 查重比對(duì)算法的測(cè)試驗(yàn)證與分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境（表1）在代碼查重中對(duì)結(jié)果準(zhǔn)確率的影響微乎其微，但會(huì)極大地影響計(jì)算速度。

3.2 實(shí)驗(yàn)方法

選取兩個(gè)代碼文本，分別是兩個(gè)完全不同的Verilog文件A和B，然后從A中隨機(jī)選取一些語(yǔ)句加入B文件中。設(shè)定A的代碼字符量為a，B的代碼字符量b，而從A中選取的加入B中的代碼字符量為c，則定義這兩個(gè)文件的相似度為：

S=（c/（a+b））*100%

而查重準(zhǔn)確率為：

Diff=（1-|c-c′|/c′）*100%。

然后創(chuàng)建多對(duì)文本，涵蓋完全重復(fù)到部分重復(fù)到完全不重復(fù)，用來(lái)驗(yàn)證查重代碼的有效性、敏感性和準(zhǔn)確性。

3.3 有效性檢驗(yàn)

先選取兩個(gè)完全不同的文本，然后選取兩個(gè)完全相同的文本，分別對(duì)其進(jìn)行查重比對(duì)，得出結(jié)果（表2）?？梢园l(fā)現(xiàn)算法對(duì)于不同文本是有效的，可以識(shí)別出相同文本和不同文本。

3.4 敏感性檢驗(yàn)

選取兩個(gè)完全不同的文本A和B，然后從A中選取一些代碼加入B，生成文本B1；從少到多選取一些代碼加入B，生成Bn。對(duì)A和Bn逐一進(jìn)行查重比對(duì)，并且用最長(zhǎng)公共子序列的字符串匹配的算法來(lái)作為對(duì)比，得到結(jié)果（表3）?？梢园l(fā)現(xiàn)哈希查重在敏感性上是優(yōu)于最長(zhǎng)公共子序列查重的。

4 結(jié)束語(yǔ)

本系統(tǒng)使用Java語(yǔ)言和Spring框架提出并實(shí)現(xiàn)一種基于知識(shí)管理的在線課程管理平臺(tái)，部署在Windows server上，使同濟(jì)大學(xué)計(jì)算機(jī)體系結(jié)構(gòu)的教研更趨向信息化。并且在其中提出并實(shí)現(xiàn)一種基于k-gram的在線查重算法，可以針對(duì)學(xué)生代碼進(jìn)行同課程內(nèi)的查重。該平臺(tái)現(xiàn)已在同濟(jì)大學(xué)計(jì)算機(jī)體系結(jié)構(gòu)課程教學(xué)中試運(yùn)行，為教師審閱學(xué)生代碼提供了極大便利，為提升教學(xué)質(zhì)量奠定堅(jiān)實(shí)的基礎(chǔ)。雖然目前缺少在線編譯、在線代碼查看等功能，甚至存在一些未知的問(wèn)題，需要在之后的迭代中繼續(xù)完善，但已經(jīng)達(dá)到初步試運(yùn)行的標(biāo)準(zhǔn)。未來(lái)需要根據(jù)用戶反饋，完善更多功能，優(yōu)化體驗(yàn)，助力課程教學(xué)。

參考文獻(xiàn)

[1] 張黎明，龔琪琳.基于MVC模式的Java Web應(yīng)用設(shè)

計(jì)[J].計(jì)算機(jī)與現(xiàn)代化，2007（2）：22-24.

[2] 秦國(guó)鋒，秦家豪，鄒劍煌，等.基于Artix-7 FPGA

的三級(jí)存儲(chǔ)體系設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)[J].實(shí)驗(yàn)室研究與

探索，2020，39（10）：45-49.

[3] 秦國(guó)鋒，胡岳，黃林鈺.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程實(shí)驗(yàn)

靜態(tài)流水線CPU的設(shè)計(jì)、實(shí)現(xiàn)與性能分析[J].教育

現(xiàn)代化，2018，5（20）：183-187，195.

[4] Broder AZ .On the Resemblance and Containment of

Documents[M]//Proceedings of the Compression

and Complexity of Sequences 1997.IEEE，1997.

[5] Baker B S， Manber U.Deducing similarities in

Java sources from bytecodes[J].USENIX Associa-

tion，1998.

[6] Schleimer S，Wilkerson D S， Aiken A. Winnowing：

Local Algorithms for Document Fingerprinting

[M]//Proceedings of the 2003 ACM SIGMOD inter

national conference on Management of data，2003：

76-85.

*項(xiàng)目來(lái)源：2017與2019教育部—美國(guó)DIGILENT公司產(chǎn)學(xué)合作協(xié)同育人項(xiàng)目（項(xiàng)目編號(hào)：201702015017，20190209

7011）；2017—2019年同濟(jì)大學(xué)實(shí)驗(yàn)實(shí)踐教學(xué)改革項(xiàng)目（項(xiàng)目編號(hào)：0800104251、0800104500/008）；同濟(jì)大學(xué)—華為

“智能基座”產(chǎn)教融合協(xié)同育人基地項(xiàng)目（項(xiàng)目編號(hào)：0800166023/001）。

作者：秦國(guó)鋒，同濟(jì)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)教研室主任，博士，研究方向?yàn)楦兄c嵌入式系統(tǒng)；王睿晗、任成琨、郝泳濤、王力生，同濟(jì)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系（200092）。