孫令成 肖鐵軍

（江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212000）

1 引言

隨著計(jì)算機(jī)科技的高速發(fā)展，以現(xiàn)代化的網(wǎng)絡(luò)教學(xué)手段解決傳統(tǒng)實(shí)驗(yàn)教學(xué)的不足，學(xué)生能夠進(jìn)行線上實(shí)驗(yàn)，以現(xiàn)代化的網(wǎng)絡(luò)教學(xué)手段解決傳統(tǒng)實(shí)驗(yàn)教學(xué)的不足，讓學(xué)生通過網(wǎng)絡(luò)遠(yuǎn)程訪問實(shí)驗(yàn)室設(shè)備完成實(shí)驗(yàn)的探索勢(shì)在必行［1］。這可以實(shí)現(xiàn)理論教學(xué)與實(shí)踐操作一體化、虛擬仿真和真實(shí)環(huán)境一體化、教學(xué)過程與教學(xué)管理一體化［2］。而抄襲現(xiàn)象作為一個(gè)一直困擾學(xué)術(shù)界多個(gè)領(lǐng)域的問題，不論是學(xué)生作業(yè)還是實(shí)驗(yàn)設(shè)計(jì)等，都或多或少存在抄襲現(xiàn)象［3］。

目前已經(jīng)有多種檢測(cè)代碼抄襲的算法，每種算法也有各自的優(yōu)缺點(diǎn)?；贙R 和Winnowing 的程序代碼相似度檢測(cè)算法［4～5］，李晗［6］基于TF-IDF 的程序代碼抄襲檢測(cè)算法，展佳俊等［7］基于多特征值的源代碼相似度檢測(cè)算法，馬申［8］以及Nickolay等［9］基于網(wǎng)絡(luò)流的代碼查重算法，Sanjay 等［10］基于語言不可知代碼抄襲分類的可靠代碼抄襲檢測(cè)方法，F(xiàn)eng Zhang 等［11］基于流程圖生成的源代碼相似性檢測(cè)，Junaid 等［12］基于索引的文件級(jí)粒度可伸縮代碼抄襲檢測(cè)特征提取技術(shù)。Lisan 等［13］基于ES-Plag抄襲檢測(cè)工具的代碼查重算法。

本文基于Verilog 語言，從其詞法分析識(shí)別單詞開始，結(jié)合TF-IDF算法獲取其文本特征值，再通過語法分析使用語法樹節(jié)點(diǎn)的哈弗曼值作為其結(jié)構(gòu)特征值，聯(lián)合使用文本特征值和結(jié)構(gòu)特征值構(gòu)成代碼向量，對(duì)代碼向量使用奇異值分解獲取其潛在語義空間，再潛在語義空間上余弦相似度獲取學(xué)生代碼之間的相似度值。實(shí)現(xiàn)了一種高效的程序代碼集到特征矩陣文本特征提取算法。

2 多維余弦相似度代碼特征提取的算法設(shè)計(jì)

本文提出多維余弦相似度代碼特征提取的算法。主要由三部分組成：1）特征值提取模塊；2）潛在語義空間獲取模塊；3）相似度計(jì)算模塊。

2.1 文本特征值、結(jié)構(gòu)特征值提取模塊

為保證每份學(xué)生作業(yè)文件格式的統(tǒng)一，因此需要對(duì)學(xué)生作業(yè)文件進(jìn)行預(yù)處理。必須刪除所有的注釋、制表符（ ）、換行（ ）以及多余無用的空格。根據(jù)Verilog 語言的相關(guān)詞法以及文本相似度的計(jì)算，為了同時(shí)體現(xiàn)程序語言的特征和文本語言的特征，先將所有可能識(shí)別到的單詞分為六類，如表1所示。

表1 單詞類別表

文本特征值的提取流程如圖1 所示，首先對(duì)每一份作業(yè)依次進(jìn)行詞法分析，讀取作業(yè)文件中的每一個(gè)單詞并且記錄和分類。在讀取完該實(shí)驗(yàn)項(xiàng)目下所有的學(xué)生文件后，再使用TF-IDF 算法計(jì)算分類中每一個(gè)單詞的對(duì)應(yīng)的TF-IDF 值，將該值存儲(chǔ)為文本特征值。

圖1 詞法分析器實(shí)現(xiàn)流程圖

TF值的計(jì)算公式如式（1）所示：

其中ni,j是該單詞在文件dj中出現(xiàn)的次數(shù)，分母則是文件dj中所有單詞出現(xiàn)的次數(shù)總和。

IDF值的計(jì)算公式如式（2）所示：

|D|是在做完語料庫中的文件總數(shù)。|{j:ti?dj}|表示包含詞語ti的文件數(shù)目（即ni,j≠0的文件數(shù)目）。

結(jié)構(gòu)特征值的提取過程分為如下幾步：1）生成學(xué)生作業(yè)的抽象語法樹；2）仿照哈夫曼編碼，在抽象語法樹的基礎(chǔ)上獲取每個(gè)單詞的哈弗曼值，并將該值轉(zhuǎn)換成10 進(jìn)制；3）根據(jù)詞法分析的單詞類別對(duì)單詞進(jìn)行分類，相同單詞進(jìn)行均值處理，并用該均值作為結(jié)構(gòu)特征值。

抽象語法樹（Abstract Syntax Tree，AST）［13～14］是源代碼的抽象語法結(jié)構(gòu)的樹狀表示，樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)，之所以說是抽象的，是因?yàn)槌橄笳Z法樹并不會(huì)表示出真實(shí)語法出現(xiàn)的每一個(gè)細(xì)節(jié)。哈希算法可以把任何一種數(shù)據(jù)通過散列算法變換成固定長(zhǎng)度的輸出。

如下的if-else結(jié)構(gòu)的verilog代碼：

圖2 if-then-else的語法樹結(jié)構(gòu)

在抽象語法樹的基礎(chǔ)上，仿照哈夫曼編碼，二叉樹中結(jié)點(diǎn)引向其左孩子的分支標(biāo)‘0’，引向其右孩子的分支標(biāo)‘1’；每個(gè)節(jié)點(diǎn)的編碼即為從根到每個(gè)葉子節(jié)點(diǎn)的路徑上得到的0，1 序列。如此得到的即為二進(jìn)制前綴編碼作為每個(gè)單詞的哈弗曼對(duì)單詞進(jìn)行分類，對(duì)于重復(fù)出現(xiàn)的相同單詞進(jìn)行均值處理，并用該均值作為結(jié)構(gòu)特征值。

2.2 潛在語義空間獲取模塊

為了獲取更高的計(jì)算效率，這里使用奇異值分解完成對(duì)矩陣的分解和壓縮［15～16］。奇異值分解的計(jì)算公式如式（3）所示，且奇異值分解擁有如下兩天重要的數(shù)學(xué)性質(zhì)：1）一個(gè)m?n 的矩陣至多有p=min（m，n）個(gè)不同的奇異值；2）矩陣的信息往往集中在較大的幾個(gè)奇異值中。

其中，U ?Rm*r，S ?Rr*r，V?Rn*r且r=rank（A）為矩陣A的秩。

在文本信息處理領(lǐng)域中，這三個(gè)矩陣有著非常重要的意義。矩陣U 是矩陣A 經(jīng)過變換后的標(biāo)準(zhǔn)正交基，每一行對(duì)應(yīng)特定詞項(xiàng)，列向量代表文檔集中不同的語義維度，（Ur）is給出的文檔i 和第s 個(gè)語義維度之間的強(qiáng)弱關(guān)系。矩陣S 是一個(gè)對(duì)角矩陣，對(duì)角線上的元素是A 的全體奇異值，按行遞增排序，表示了矩陣V 中的向量和矩陣U 中對(duì)應(yīng)向量的比例關(guān)系。矩陣V 是原始域的標(biāo)準(zhǔn)正交基，每一行對(duì)應(yīng)一個(gè)特定的文檔，每一列代表文檔集中不同的語義維度，（Vr）js給出的是文檔j 和第s 個(gè)語義維度之間的強(qiáng)弱關(guān)系。

由于一個(gè)矩陣的信息往往存在與較大的幾個(gè)奇異值中，因此根據(jù)式（3）可以推到出表達(dá)式（4）。

其中k=rank（A）<

U ?Rm*r的全體列向量所組成的r 維線性空間構(gòu)成文本的潛在語義表示空間，A 中的任一文檔可通過Uk映射到該空間得到其在潛在語義空間上的表示。由式（5）推導(dǎo)過程可得原始文檔集在潛在語義空間上的表示。

由于使用的TF-IDF算法計(jì)算得到的文本特征值，且結(jié)構(gòu)特征值的計(jì)算也是基于文本特征值的。所以每一份實(shí)驗(yàn)的每一位學(xué)生的代碼分別按照都可以映射到六個(gè)相同維度的向量空間上，此處以符號(hào)類別為例，按照單詞先后出現(xiàn)的順序構(gòu)造出一個(gè)M 維的向量，每一位學(xué)生的代碼可以構(gòu)成兩個(gè)向量，一個(gè)基于文本特征值的向量，一個(gè)基于結(jié)構(gòu)特征值的向量。對(duì)于這兩個(gè)特征值向量取平均作為學(xué)生代碼的特征值向量，這樣的特征值向量有六個(gè)。這樣N 位學(xué)生的代碼可以組成6 個(gè)N*M 維度的矩陣。通過奇異值分解和潛在語義空間構(gòu)造得到的代碼矩陣也會(huì)有六個(gè)。

2.3 相似度計(jì)算模塊

余弦相似性是通過計(jì)算兩個(gè)向量的夾角的余弦值來表明兩者的相似性。由于余弦相似度是通過計(jì)算兩個(gè)向量之間夾角的余弦值得到的，并以此衡量?jī)蓚€(gè)個(gè)體間的差異。在文本標(biāo)準(zhǔn)化工作中，常用編輯距離度量?jī)蓚€(gè)文本的相似度［11～12］。

在文本匹配的算法中，假設(shè)屬性向量A 和B 是文檔中的詞頻向量，即可以被看作是在比較過程中把文件長(zhǎng)度正規(guī)化的方法。設(shè)文檔A 中共有j個(gè)單詞，文檔B 中共有k個(gè)單詞，兩篇文章共有n 個(gè)不同的單詞，則有：

由于兩個(gè)向量間的余弦值可以通過歐幾里得點(diǎn)積公式求出：

則可以得到余弦相似度similarity 的計(jì)算公式如下：

在1.2 節(jié)中，一份學(xué)生代碼通過奇異值分解可以得到6份向量，記作：

其中Ci表示原學(xué)生代碼在潛在語義空間上的表示，n為該潛在語義空間的維度。

經(jīng)過在本算法中為各類別定義的權(quán)重如表2所示。由此可以得到相似度的計(jì)算公式：

表2 單詞類別權(quán)重表

其中i 為單詞分類，共有六類，ni為每一類單詞在潛在語義空間上的維度，ASi,j、BSi,j為每一份作業(yè)文件的潛在語義空間的向量表示，Pi為每一類單詞的權(quán)重分。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本設(shè)計(jì)的實(shí)驗(yàn)數(shù)據(jù)源自于江蘇大學(xué)的遠(yuǎn)程FPGA 實(shí)驗(yàn)平臺(tái)上的2019 級(jí)信息安全專業(yè)的《邏輯與CPU 設(shè)計(jì)實(shí)驗(yàn)》學(xué)生的作業(yè)。在獲取數(shù)據(jù)的時(shí)候，首先要提取出每一份作業(yè)中的程序代碼，再將其命名為“學(xué)院-專業(yè)-班級(jí)-學(xué)號(hào)-姓名.txt”的形式。之后再運(yùn)行實(shí)驗(yàn)程序進(jìn)行讀取計(jì)算學(xué)生代碼作業(yè)的相似度。在計(jì)算完成后，分別輸出任意兩個(gè)學(xué)生之間的相似度表格與相似度信息的文件。本設(shè)計(jì)共采取了三組作業(yè)文件進(jìn)行對(duì)照和比較算法效果，分別是存儲(chǔ)器實(shí)驗(yàn)、單周期控制器實(shí)驗(yàn)以及七段譯碼器實(shí)驗(yàn)，再選取七份實(shí)驗(yàn)進(jìn)行驗(yàn)證，分別是彩燈控制器、多功能運(yùn)算電路、計(jì)數(shù)器與分頻器、寄存器堆、數(shù)據(jù)通路、算術(shù)邏輯單元的實(shí)驗(yàn)。各個(gè)實(shí)驗(yàn)文件的代碼均具有一定的Verilog 語言特色，具有代表性。

3.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

學(xué)生代碼的評(píng)價(jià)結(jié)果包括存在抄襲現(xiàn)象和不存在抄襲現(xiàn)象兩種結(jié)果。本文基于召回率（Recall）和精確率（Precision）作為衡量算法準(zhǔn)確性的指標(biāo)。兩個(gè)指標(biāo)的計(jì)算公式如式（12）、（13）所示。

其中P 表示精確率，R 表示召回率，TP 表示正類預(yù)測(cè)為正類（計(jì)算得出抄襲，人工檢測(cè)也是抄襲），F(xiàn)N表示正類預(yù)測(cè)為負(fù)類（計(jì)算得出非抄襲，人工檢測(cè)是抄襲），F(xiàn)P 表示負(fù)類預(yù)測(cè)為正類（計(jì)算得出抄襲，人工檢測(cè)非抄襲），TN 表示負(fù)類預(yù)測(cè)為負(fù)類（計(jì)算得出非抄襲，人工檢測(cè)非抄襲）。

3.3 實(shí)驗(yàn)結(jié)果分析

為展示學(xué)生代碼之間的相似度情況，制作了作業(yè)相似度矩陣。以七段譯碼器實(shí)驗(yàn)為例，在表3中，展示了8名同學(xué)代碼之間的相似度情況，編號(hào)1至8 分別表示不同的學(xué)生，而矩陣中的數(shù)值則代表該作業(yè)的加權(quán)余弦相似度，其數(shù)值越高，在表中的底色越紅，表示這兩位同學(xué)代碼作業(yè)的相似性越高；而數(shù)值越低，在表中的底色越綠，表示這兩位同學(xué)代碼作業(yè)相似性越低。其中，有幾位學(xué)生的相似度較高，分別是2號(hào)和6號(hào)、6號(hào)和7號(hào)、6號(hào)和8號(hào)。

表3 七段譯碼器學(xué)生作業(yè)相似度矩陣

如圖6 所示，打開2 號(hào)與6 號(hào)的學(xué)生的代碼進(jìn)行人工核查，發(fā)現(xiàn)兩位學(xué)生代碼除了空格與大小寫，其他地方包括變量名都一模一樣，作業(yè)相似度的確較高，屬于抄襲范疇，其他幾位也與該對(duì)作業(yè)相似，但是由于實(shí)驗(yàn)完成人數(shù)較少，且該份代碼作業(yè)中的標(biāo)準(zhǔn)數(shù)均已經(jīng)由教師給出，很難有說服力，因此需要使用完成人數(shù)更多的實(shí)驗(yàn)進(jìn)行驗(yàn)證。

由于完成存儲(chǔ)器與單周期控制器的實(shí)驗(yàn)人數(shù)較多，因此此處以這兩個(gè)實(shí)驗(yàn)作為測(cè)試用例，拿存儲(chǔ)器實(shí)驗(yàn)來說，在將一個(gè)班級(jí)的學(xué)生作業(yè)放入程序中運(yùn)行后可以得到整個(gè)班級(jí)任意兩個(gè)同學(xué)之間的相似度。由于實(shí)驗(yàn)完成學(xué)生數(shù)量較多，將每個(gè)人的作業(yè)同時(shí)與其他所有人的比較后再查看其抄襲程度，不論是算法查重檢測(cè)，還是后續(xù)人工核查，其效率都較低，因此這里首先選取每個(gè)學(xué)生作業(yè)相對(duì)于其他學(xué)生作業(yè)中最高的相似度值，再選取一定的閾值，對(duì)學(xué)生作業(yè)分別進(jìn)行人工抄襲檢測(cè)，這樣對(duì)于任意一個(gè)同學(xué)，只要與其代碼作業(yè)相似度最高的作業(yè)進(jìn)行比較即可，再通過計(jì)算召回率與精確率，判斷該算法的合理性，具體結(jié)果如表4所示。

表4 余弦相似度統(tǒng)計(jì)表

在該實(shí)驗(yàn)中，共有77 個(gè)學(xué)生提交了作業(yè)，而根據(jù)表14 可以了解，如果省去教師人工查重的步驟，根據(jù)實(shí)驗(yàn)的難易程度，大約選取相似度閾值為前20%～40%的學(xué)生判定為抄襲最為合理。一定程度上證明了該算法的合理性。再選取剩下7 個(gè)實(shí)驗(yàn)作業(yè)進(jìn)行驗(yàn)證，在通過程序過后，分別得到如表5所示。

表5 驗(yàn)證程序正確率

為方便教師對(duì)教學(xué)效果的審查，制作了如圖4的堆疊條形圖，它基于學(xué)生代碼之間的相似度值總結(jié)了每個(gè)實(shí)驗(yàn)任務(wù)的小團(tuán)體，每一個(gè)團(tuán)體的人數(shù)都多余兩人，對(duì)于低相似度的學(xué)生沒有計(jì)入圖表中。根據(jù)該表的情況，教師可以了解到對(duì)于每次實(shí)驗(yàn)任務(wù)的完成情況，學(xué)生是否有大面積抄襲情況的發(fā)生。在多功能運(yùn)算電路、移位寄存器、數(shù)據(jù)通路這三個(gè)實(shí)驗(yàn)中，都存在這一個(gè)較大的團(tuán)體，該團(tuán)體成員的作業(yè)相似度較高。圖5 展示的是多功能運(yùn)算電路的相似度散點(diǎn)圖，根據(jù)改圖可以發(fā)現(xiàn)，在該實(shí)驗(yàn)中存在者兩個(gè)團(tuán)體，其中一個(gè)團(tuán)體的規(guī)模較大，該情況與圖4 反映的結(jié)果一致。教師可以根據(jù)該圖發(fā)現(xiàn)班級(jí)在該實(shí)驗(yàn)過程中的抄襲情況，從而進(jìn)行教學(xué)內(nèi)容的改進(jìn)。圖6 展示的是多功能運(yùn)算電路中某一名學(xué)生與其他學(xué)生作業(yè)的相似度折線圖，教師可以通過這張圖對(duì)某一位學(xué)生進(jìn)行詳細(xì)的觀察。通過該表發(fā)現(xiàn)，該學(xué)生與另一名同學(xué)作業(yè)的相似度高達(dá)0.7，這樣就有大概率的可能出現(xiàn)了抄襲現(xiàn)象。

圖4 學(xué)生實(shí)驗(yàn)代碼相似小組分類情況

圖5 多功能運(yùn)算電路的相似度散點(diǎn)圖

圖6 一名學(xué)生與其他學(xué)生作業(yè)的相似度折線圖

4 結(jié)語

本文提出并實(shí)現(xiàn)了一種高效的程序代碼集到特征矩陣文本特征提取算法，根據(jù)程序設(shè)計(jì)語言的特征對(duì)代碼進(jìn)行分類，基于Verilog 語言，從其詞法分析識(shí)別單詞開始，結(jié)合TF-IDF 算法獲取其文本特征值，再通過語法分析使用語法樹節(jié)點(diǎn)的哈弗曼值作為其結(jié)構(gòu)特征值，聯(lián)合使用文本特征值和結(jié)構(gòu)特征值構(gòu)成代碼向量，對(duì)代碼向量使用奇異值分解獲取其潛在語義空間，再潛在語義空間上余弦相似度獲取學(xué)生代碼之間的相似度值。該算法從編譯層的角度實(shí)現(xiàn)了抄襲檢測(cè)，效率較高，且對(duì)于學(xué)生代碼作業(yè)的抄襲檢測(cè)率效果較好，可以幫助教師更好地完成教學(xué)工作。