程序代碼集到特征矩陣文本特征提取算法的研究?

孫令成 肖鐵軍

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

1 引言

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

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

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

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

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

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

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

表1 單詞類別表

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

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

TF值的計算公式如式（1）所示：

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

IDF值的計算公式如式（2）所示：

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

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

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

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

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

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

2.2 潛在語義空間獲取模塊

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

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

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

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

其中k=rank（A）<

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

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

2.3 相似度計算模塊

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

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

由于兩個向量間的余弦值可以通過歐幾里得點積公式求出：

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

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

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

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

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

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

3 實驗與分析

3.1 實驗數(shù)據(jù)

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

3.2 實驗評價標(biāo)準(zhǔn)

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

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

3.3 實驗結(jié)果分析

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

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

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

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

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

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

表5 驗證程序正確率

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

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

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

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

4 結(jié)語

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