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

孫令成 肖鐵軍

（江蘇大學計算機科學與通信工程學院 鎮江 212000）

1 引言

隨著計算機科技的高速發展，以現代化的網絡教學手段解決傳統實驗教學的不足，學生能夠進行線上實驗，以現代化的網絡教學手段解決傳統實驗教學的不足，讓學生通過網絡遠程訪問實驗室設備完成實驗的探索勢在必行［1］。這可以實現理論教學與實踐操作一體化、虛擬仿真和真實環境一體化、教學過程與教學管理一體化［2］。而抄襲現象作為一個一直困擾學術界多個領域的問題，不論是學生作業還是實驗設計等，都或多或少存在抄襲現象［3］。

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

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

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

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

2.1 文本特征值、結構特征值提取模塊

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

表1 單詞類別表

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

圖1 詞法分析器實現流程圖

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

其中ni,j是該單詞在文件dj中出現的次數，分母則是文件dj中所有單詞出現的次數總和。

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

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

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

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

如下的if-else結構的verilog代碼：

圖2 if-then-else的語法樹結構

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

2.2 潛在語義空間獲取模塊

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

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

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

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

其中k=rank（A）<

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

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

2.3 相似度計算模塊

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

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

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

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

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

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

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

表2 單詞類別權重表

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

3 實驗與分析

3.1 實驗數據

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

3.2 實驗評價標準

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

其中P 表示精確率，R 表示召回率，TP 表示正類預測為正類（計算得出抄襲，人工檢測也是抄襲），FN表示正類預測為負類（計算得出非抄襲，人工檢測是抄襲），FP 表示負類預測為正類（計算得出抄襲，人工檢測非抄襲），TN 表示負類預測為負類（計算得出非抄襲，人工檢測非抄襲）。

3.3 實驗結果分析

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

表3 七段譯碼器學生作業相似度矩陣

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

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

表4 余弦相似度統計表

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

表5 驗證程序正確率

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

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

圖5 多功能運算電路的相似度散點圖

圖6 一名學生與其他學生作業的相似度折線圖

4 結語

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