基于TF-IDF的程序代碼抄襲檢測系統(tǒng)

李晗

摘要：本文設(shè)計(jì)了一種用于程序設(shè)計(jì)實(shí)驗(yàn)源代碼結(jié)果抄襲檢測系統(tǒng)。采用自然語言處理技術(shù)中的TF-IDF算法和測量向量相似度的余弦相似性算法，分析檢測源程序抄襲情況，通過實(shí)際應(yīng)用算例驗(yàn)證了系統(tǒng)的有效性。源程序抄襲檢測對各種需要提交代碼的實(shí)驗(yàn)教學(xué)系統(tǒng)有重要的實(shí)用價(jià)值。

關(guān)鍵詞：TF-IDF;余弦相似性;抄襲檢測;C源程序

中圖分類號：TP183 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2020）09-0136-03

0 引言

高校程序類課程教學(xué)越來越多地要求學(xué)生在線提交編程作業(yè)或?qū)嶒?yàn)源代碼。一些課程或?qū)嶒?yàn)也開始使用成績自動評分系統(tǒng)[1]。這些代碼提交系統(tǒng)的廣泛應(yīng)用使得防范代碼抄襲成為此類課程的一個(gè)重要需求。抄襲檢測也是慕課系統(tǒng)或在線教學(xué)系統(tǒng)的重要組成部分[2]。

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

從自然語言處理的觀點(diǎn)來看，抄襲檢測的本質(zhì)是測量兩個(gè)文本的相似度。在進(jìn)行相似性計(jì)算時(shí)，可采用余弦相似性算法。從文本到文本特征向量的轉(zhuǎn)化則采用TF-IDF算法[3-5]。整個(gè)算法的流程如圖1所示。

整個(gè)算法流程說明如下：

（1）將C語言的各種操作符、分隔符及三種括號聚合為停用詞（stopwords）集合;

（2）使用停用詞集合進(jìn)行濾除操作，保留各種名稱標(biāo)識符，形成關(guān)鍵詞向量;

（3）綜合所有文本的處理結(jié)果（關(guān)鍵詞向量），形成語料庫（corpus）;

（4）分別計(jì)算各關(guān)鍵詞的TF和IDF，最后形成TF-IDF向量;

（5）計(jì)算余弦相似性;

（6）最后，提取相似度的行最大值進(jìn)行閾值處理，判斷是否抄襲。

2 實(shí)驗(yàn)與算法測試

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

實(shí)驗(yàn)數(shù)據(jù)來源于C語言程序設(shè)計(jì)課程的網(wǎng)絡(luò)作業(yè)平臺。該網(wǎng)絡(luò)平臺包括了一些C語言習(xí)題及自動判題機(jī)制，供學(xué)生在課余練習(xí)編程之用。數(shù)據(jù)集包括如下字段：用戶提交號、用戶ID、題目ID、課程序號、編程語言編號、判題結(jié)果、使用時(shí)間、使用內(nèi)存、提交時(shí)間及提交源代碼。除最后一項(xiàng)提交源代碼外，其他字段每次提交所產(chǎn)生的數(shù)據(jù)均在一行中。提交源代碼字段根據(jù)源代碼篇幅占據(jù)數(shù)量不等的行。

2.2 算法測試

首先進(jìn)行數(shù)據(jù)清洗。數(shù)據(jù)清洗主要有以下作用：

（1）將讀入的每行數(shù)據(jù)進(jìn)行切分，此處的復(fù)雜性在于提交源代碼字段和其他字段出現(xiàn)混行現(xiàn)象，解決此問題采用了正則表達(dá)式;

（2）字符編碼格式不匹配問題，通過改變讀取方式和轉(zhuǎn)碼來解決;

（3）將切分好的數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫，并分離出目標(biāo)課程對應(yīng)的相關(guān)數(shù)據(jù)。

為了確保數(shù)據(jù)清洗的可靠性，進(jìn)行數(shù)據(jù)探索。在數(shù)據(jù)探索中發(fā)現(xiàn)以下問題：

（1）通過各種SQL語句檢視數(shù)據(jù)及程序調(diào)試中發(fā)現(xiàn)少數(shù)行數(shù)據(jù)格式不規(guī)范問題，影響本行數(shù)據(jù)的分段及后續(xù)數(shù)據(jù)行的處理。處理方法為修改數(shù)據(jù)清洗程序重新進(jìn)行清洗;

（2）發(fā)現(xiàn)提交數(shù)過少或ID號格式異常的用戶，將其篩除。

接下來是數(shù)據(jù)處理環(huán)節(jié)。通過上節(jié)所述的算法流程對數(shù)據(jù)進(jìn)行處理，其基本核心思想就是將源程序看成是一種文本，然后利用相應(yīng)算法進(jìn)行轉(zhuǎn)換和測量。將處理數(shù)據(jù)可視化可以看到文本對的余弦相似度分布情況。以下以題目ID為1958的編程題為例說明，該題的提交結(jié)果的文本對余弦相似度分布如圖2所示。

圖中橫坐標(biāo)為相似度區(qū)間，相似度從0至1平均分成100個(gè)區(qū)間;縱坐標(biāo)為相似度值落到此區(qū)間內(nèi)的文本對數(shù)量，為更明顯地展示的高相似值區(qū)間的統(tǒng)計(jì)情況，縱坐標(biāo)的顯示范圍被限制在0～2000之間。直方圖的右側(cè)的自然趨勢應(yīng)該隨著相似度值變大平緩下降為0，然而從圖中可以明顯地看到“翹尾”現(xiàn)象。這表明存在抄襲的可能性很大。

通過細(xì)致的結(jié)果分析可以進(jìn)一步說明問題。該編程問題提交源代碼文本數(shù)量為542，篩出嫌疑較大的高異常余弦相似值的文本對總數(shù)為128。高異常相似值的文本對是按照以下規(guī)則選取的：每個(gè)用戶相對于其他用戶的相似度取最大值者，然后對比閾值0.999進(jìn)行篩選，大于閾值者被篩選為高異常相似值。這些文本對的余弦相似度統(tǒng)計(jì)如表1第二列所示。為檢驗(yàn)算法組合對抄襲問題的檢測效果，使用人工方式查看源代碼文本，判斷是否抄襲，然后與算法結(jié)果進(jìn)行對比。人工判斷的結(jié)果見表1第三、四和五列。

在計(jì)算最后兩列精度和召回率時(shí)，將人工無法判定的文檔近似歸類為非抄襲文本。精度反映了檢測算法認(rèn)為的抄襲文本中真實(shí)抄襲文本所占的比率。召回率反映了真實(shí)抄襲文本中被檢測算法篩選出的比率。每欄的精度值和召回率表明在此欄的相似度閾值條件下計(jì)算出的精度值和召回率。具體見圖3。

上圖的橫坐標(biāo)為表1中相似度閾值，縱坐標(biāo)為精度和召回率的百分比。從圖中可知，在總共128個(gè)計(jì)算結(jié)果中，如果取0.9999作為相似度閾值，可取得最佳的分類效果。從表中的數(shù)據(jù)可以看出，采用TF-IDF特征向量，可以相當(dāng)準(zhǔn)確地聚合文本特征，從而使余弦相似度測量呈現(xiàn)出非常好的效果。

3 結(jié)語

本文提出了利用TF-IDF和余弦相似度的組合進(jìn)行C語言代碼的抄襲檢測，實(shí)驗(yàn)表明，算法組合取得較好的檢測效果。從本文的算法應(yīng)用可以看出，代碼抄襲檢測算法使用自然語言處理技術(shù)取得了很好的效果。由于近年來自然語言處理與神經(jīng)網(wǎng)絡(luò)技術(shù)相結(jié)合，發(fā)展迅速，因此可以從自然語言處理方面汲取更多新的思路。本文是將整個(gè)C語言源程序作為整體進(jìn)行處理的，未考慮C語言的語法特點(diǎn)所導(dǎo)致的一些宏觀結(jié)構(gòu)特征。在抄襲檢測中使用這些特征，可能使源代碼的結(jié)構(gòu)相似性判斷成為可能。今后可以在這方面進(jìn)行進(jìn)一步的研究。

參考文獻(xiàn)

[1] 張景輝，王培進(jìn).課程設(shè)計(jì)自動評分系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].電氣電子教學(xué)學(xué)報(bào)，2019，41（4）：149-152.

[2] 薛景，陳仁祥，張敏，等.程序設(shè)計(jì)類課程在線評測教輔系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)教育，2018（11）：104-108.

[3] 田振洲，劉烴，鄭慶華，等.軟件抄襲檢測研究綜述[J].信息安全學(xué)報(bào)，2016，1（3）：52-76.

[4] Burrows，Steven;Tahaghoghi，S.M.M.;Zobel，Justin.Efficient plagiarism detection for large code repositories[J].Software-Practice and Experience，2007，37（2）：151-175.

[5] Prechelt L，Malpohl G.Finding Plagiarisms among a Set of Programs with JPlag[J].J Universal Computer ence，2000，8（11）：1016-1038.