基于TF-IDF的程序代碼抄襲檢測系統

李晗

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

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

中圖分類號：TP183 文獻標識碼：A 文章編號：1007-9416（2020）09-0136-03

0 引言

高校程序類課程教學越來越多地要求學生在線提交編程作業或實驗源代碼。一些課程或實驗也開始使用成績自動評分系統[1]。這些代碼提交系統的廣泛應用使得防范代碼抄襲成為此類課程的一個重要需求。抄襲檢測也是慕課系統或在線教學系統的重要組成部分[2]。

1 算法設計

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

整個算法流程說明如下：

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

（2）使用停用詞集合進行濾除操作，保留各種名稱標識符，形成關鍵詞向量;

（3）綜合所有文本的處理結果（關鍵詞向量），形成語料庫（corpus）;

（4）分別計算各關鍵詞的TF和IDF，最后形成TF-IDF向量;

（5）計算余弦相似性;

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

2 實驗與算法測試

2.1 實驗環境

實驗數據來源于C語言程序設計課程的網絡作業平臺。該網絡平臺包括了一些C語言習題及自動判題機制，供學生在課余練習編程之用。數據集包括如下字段：用戶提交號、用戶ID、題目ID、課程序號、編程語言編號、判題結果、使用時間、使用內存、提交時間及提交源代碼。除最后一項提交源代碼外，其他字段每次提交所產生的數據均在一行中。提交源代碼字段根據源代碼篇幅占據數量不等的行。

2.2 算法測試

首先進行數據清洗。數據清洗主要有以下作用：

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

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

（3）將切分好的數據導入數據庫，并分離出目標課程對應的相關數據。

為了確保數據清洗的可靠性，進行數據探索。在數據探索中發現以下問題：

（1）通過各種SQL語句檢視數據及程序調試中發現少數行數據格式不規范問題，影響本行數據的分段及后續數據行的處理。處理方法為修改數據清洗程序重新進行清洗;

（2）發現提交數過少或ID號格式異常的用戶，將其篩除。

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

圖中橫坐標為相似度區間，相似度從0至1平均分成100個區間;縱坐標為相似度值落到此區間內的文本對數量，為更明顯地展示的高相似值區間的統計情況，縱坐標的顯示范圍被限制在0～2000之間。直方圖的右側的自然趨勢應該隨著相似度值變大平緩下降為0，然而從圖中可以明顯地看到“翹尾”現象。這表明存在抄襲的可能性很大。

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

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

上圖的橫坐標為表1中相似度閾值，縱坐標為精度和召回率的百分比。從圖中可知，在總共128個計算結果中，如果取0.9999作為相似度閾值，可取得最佳的分類效果。從表中的數據可以看出，采用TF-IDF特征向量，可以相當準確地聚合文本特征，從而使余弦相似度測量呈現出非常好的效果。

3 結語

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

參考文獻

[1] 張景輝，王培進.課程設計自動評分系統設計與實現[J].電氣電子教學學報，2019，41（4）：149-152.

[2] 薛景，陳仁祥，張敏，等.程序設計類課程在線評測教輔系統的設計與實現[J].計算機教育，2018（11）：104-108.

[3] 田振洲，劉烴，鄭慶華，等.軟件抄襲檢測研究綜述[J].信息安全學報，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.